最初的难题

这是一个数据矩阵B的线索。第一行,B(1、2、2)，表示第一行，第二列有线索2。第二行,B(1、5、3)，表示第一行，第5列有线索3。这是整个矩阵B．

B =[1、2、2;1、5、3;1、8、4;2、1、6;2、9、3;3、3、4;3、7、5;4、4、8;4、6、6;5 1 8; 5,5,1; 5,9,6; 6,4,7; 6,6,5; 7,3,7; 7,7,6; 8,1,4; 8,9,8; 9,2,3; 9,5,4; 9,8,2]; drawSudoku(B)有关这个程序的列表，请参阅本例的结尾部分。

这个难题，和替代的MATLAB®解决技术，是特色克里夫的角落在2009年。

有许多方法可以手工解决数独谜题，也有许多编程方法。这个例子展示了一种使用二进制整数编程的简单方法。

这种方法特别简单，因为您没有给出解决算法。只需将数独规则表示出来，将线索表示为解的约束条件，然后用MATLAB进行求解。

二进制整数规划方法

关键思想是把一个难题从正方形网格9-by-9立方9-by-9-by-9数组的二进制值(0或1)。认为立方阵列是9平方网格堆叠在彼此之上,在每一层都对应于一个从1到9的整数。顶部的网格，数组的正方形层，只要解或线索为1，它就为1。第二层是1，只要解或线索是2。第九层是1，只要答案或线索是9。

这个公式非常适合于二进制整数规划。

这里不需要目标函数，它也可以是常数项0。问题就是要找到一个可行的解，也就是满足所有约束条件的解。然而，对于整数规划求解器内部的打结，为了提高求解速度，使用非常数目标函数。

将数独规则表达为约束条件

假设一个解决方案 $$x$$用一个9 × 9 × 9的二进制数组表示。什么属性 $$x$$有什么?首先，二维网格(i,j)中的每个正方形都只有一个值，因此在三维数组项中只有一个非零元素 $$x（我，j，1），．．．，x（我，j，9）$$．换句话说，对于每一个 $$我$$和 $$j$$，

同样，在每一行 $$我$$在二维网格中，从1到9的每个数字都有一个值。换句话说，对于每一个 $$我$$和 $$k$$，

和每一列 $$j$$在二维网格中有相同的属性:对于每个 $$j$$和 $$k$$，

主要的3 × 3网格也有类似的限制。对于网格元素 $$1\le 我\le 3.$$和 $$1\le j\le 3.$$，对于每一个 $$1\le k\le 9$$，

要表示所有9个主要网格，只需在每个网格上添加3或6个 $$我$$和 $$j$$指数:

$$\underset{我＝1}{\overset{3.}{\sum }}\underset{j＝1}{\overset{3.}{\sum }}x（我+U，j+V，k）＝1，$$在哪里 $$U，Vϵ｛0，3.，6｝．$$

表达的线索

每个初值(线索)都可以表示为一个约束。假设 $$（我，j）$$线索是 $$米$$对于一些 $$1\le 米\le 9$$．然后 $$x（我，j，米）＝1$$．约束 $$\underset{k＝1}{\overset{9}{\sum }}x（我，j，k）＝1$$确保所有其他 $$x（我，j，k）＝0$$为 $$k\ne 米$$．

最优化问题形式中的数独

创建优化变量x它是二进制的，大小是9乘9乘9。

x = optimvar (“x”9日,9日,9日“类型”，“整数”，下界的，0，“UpperBound”1);

用一个相当任意的目标函数创建一个优化问题。目标函数可以通过破坏问题的固有对称性来帮助求解者。

sudpuzzle = optimproblem;mul = 1 (1, 1, 9);mul = cumsum (mul 3);sudpuzzle。目标=总和(金额(金额(x, 1), 2)。* mul);

表示求和的约束条件x每个坐标方向都是1。

sudpuzzle. constraints . conx = sum(x,1) == 1;sudpuzzle.Constraints.consy = sum(x,2) == 1;sudpuzzle. constraints . conz = sum(x,3) == 1;

创建约束条件，使主要网格的总和也为1。

majorg = optimconstr(3、3、9);为u = 1:3为v = 1:3 arr = x (3 * (u-1) + 1:3 * (u-1) + 3, 3 *(它们)+ 1:3 *(它们)+ 3:);maj (u,v，:) = sum(sum(arr,1)，2) == ones(1,1,9);结束结束sudpuzzle.Constraints.majorg = majorg;

通过在线索入口设置1的下界来包含初始线索。这个设置将对应条目的值固定为1，因此将每个线索值处的解设置为线索条目。

为u = 1:尺寸(B, 1) x.LowerBound (B (u, 1), B (u, 2), B (u, 3)) = 1;结束

解决数独谜题。

sudsoln =解决(sudpuzzle)

使用intlinprog解决问题。LP:最佳目标值为405.000000。找到最优解。Intlinprog在根节点停止，因为客观值在最优值options的间隙公差范围内。AbsoluteGapTolerance = 0(默认值)。intcon变量是在公差选项内的整数。IntegerTolerance = 1e-05(默认值)。

sudsoln =结构体字段:x (9 x9x9双):

对解决方案进行四舍五入，以确保所有条目都是整数，并显示解决方案。

sudsoln。x＝round(sudsoln.x); y = ones(size(sudsoln.x));为y(:，:， K) = K;每个深度k的%乘数结束S = sudsoln.x。* y;%乘以每个条目的深度S =(年代,3)总和;% S是9乘9的，并持有已解决的谜题drawSudoku (S)

你可以很容易地检查解决方案是否正确。

函数绘制数独拼图

类型drawSudoku

function drawSudoku(B) % function for drawing the Sudoku board %公司图;坚持;轴,轴平等%准备画矩形(“位置”,[0 0 9 9],“线宽”,3,“剪裁”,“关闭”)%外边界矩形(“位置”,[3 0 3 9],“线宽”,2)%沉重的竖线矩形(“位置”,[3]0、3、9日,“线宽”,2)%沉重的水平线矩形(“位置”,[1]0 1 9日,“线宽”,1)%小横线矩形(“位置”,[1]0、4、9日,“线宽”,1)矩形(“位置”,[1]0、7、9日,“线宽”,1)矩形(“位置”,[1,0,1,9],“线宽”,1)%小竖线矩形(“位置”,[4 0 1 9],“线宽”,1)矩形(“位置”,[7,0,1,9],“线宽”,1)% % % B的行填写线索的形式(i, j, k),我是%的行数上面，j是列，k是线索。要将条目放入%框中，j是水平距离，10-i是垂直距离，%减去0.5使线索在框中居中。% %如果B是一个9 × 9的矩阵，如果size(B,2) == 9 % 9 columns [SM,SN] = meshgrid(1:9);% make i,j entries B = [SN(:)，SM(:)，B(:)];% i,j,k row end for ii = 1:size(B,1) text(B(ii,2)-0.5, 3.5 -B(ii,1)，num2str(B(ii,3)) end hold off end .(如果你的操作失败，你的操作会失败。