初始拼图

这是一个数据矩阵B的线索。第一行,B(1、2、2)，表示第一行，第二列有一个线索2。第二行,B（1,5,3），表示第1行，第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年。

有许多方法可以手动解决数独谜题，以及许多程序化方法。此示例显示使用二进制整数编程的直接方法。

这种方法尤其简单，因为您没有提供解决方案算法。只需表达Sudoku的规则，将线索表达为解决方案的约束，然后Matlab产生解决方案。

二进制整数规划方法

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

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

这里不需要目标函数，也可能是恒定的术语0.问题实际上只是为了找到一个可行的解决方案，这意味着一个满足所有约束的解决方案。但是，对于在整数编程求解器的内部构建中断，引起溶液速度增加，请使用不合作的目标函数。

将数独规则表示为约束

假设一个解决方案 $$x$$用9 × 9 × 9的二进制数组表示。什么属性 $$x$$有？首先，2-D网格（i，j）中的每个方块都具有一个值，因此三个阵列条目中的一个非零元素恰好 $$x（我，j，1），．．．，x（我，j，9）$$．换句话说，每一个 $$我$$和 $$j$$，

同样，在每一行中 $$我$$在2-D网格中，从1到9的每个数字中的每个值恰好换句话说 $$我$$和 $$k$$，

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

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

代表所有九个主要网格，只需添加3或6个 $$我$$和 $$j$$指数:

$$\underset{我＝1}{\overset{3.}{\sum }}\underset{j＝1}{\overset{3.}{\sum }}x（我+U，j+V，k）＝1，$$在哪里 $$U，V\mathrm{\epsilon .}｛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在每个坐标方向上是一个。

sudpuzzle.constraints.consx = sum（x，1）== 1;sudpuzzle.constraints.consy = sum（x，2）== 1;sudpulzle.constraints.consz = sum（x，3）== 1;

创建大网格和一个也是一个约束的约束。

majorg = optimconstr(3、3、9);为u = 1:3为v = 1：3 arr = x（3 *（u-1）+1：3 *（u-1）+ 3,3 *（v-1）+1：3 *（v-1）+3 ,:）;majorg（u，v，:) = sum（sum（arr，1），2）== a（1,1,9）;结束结束sudpulzle.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.absolutegolerance = 0（默认值）。INTCON变量在公差中是整数，Options.integertolerance = 1E-05（默认值）。

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

围绕解决方案，以确保所有条目都是整数，并显示解决方案。

sudsoln。x＝round(sudsoln.x); y = ones(size(sudsoln.x));为k = 2：9 y（：，：，k）= k;每个深度k的%乘数结束S = sudsoln.x。* y;%将每个条目乘以其深度s =总和（s，3）;% S是9 * 9的，保存着已解决的谜题drawsudoku

您可以轻松检查解决方案是否正确。

绘制sudoku拼图的功能

类型drawSudoku

函数drawSudoku(B) %用于绘制Sudoku板的函数%公司图;坚持;轴,轴平等%准备画矩形(“位置”,[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的矩阵，首先将其转换为3列，如果size(B,2) == 9% 9列[SM,SN] =网格(1:9);% make i,j entries B = [SN(:)，SM(:)，B(:)];% i,j,k行结束为ii = 1:size(B,1) text(B(ii,2)-0.5,9 -B(ii,1)，num2str(B(ii,3))) end hold off end