最初的难题

这是一个数据矩阵b线索。第一行，b（1,2,2），表示第1行，第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难题以及许多程序化方法。此示例显示了使用二进制整数编程的直接方法。

这种方法特别简单，因为您不提供解决方案算法。只需表达Sudoku的规则，将线索表示为解决方案的约束，然后MATLAB产生解决方案。

二进制整数编程方法

关键的想法是将拼图从正方形的9 x-9网格转换为二进制值（0或1）的立方体9 x 9 x-9阵列。将立方阵列视为9平方网彼此堆叠的9平方网1.第二层在解决方案或线索中具有1个。2。第九层在解决方案或线索中具有9个。

该公式非常适合二进制整数编程。

这里不需要目标函数，也可能是一个恒定的项。问题实际上只是为了找到可行的解决方案，这意味着满足所有约束的解决方案。但是，要在整数编程求解器的内部中打破领带，从而提高了解决方案速度，请使用非稳定目标函数。

将Sudoku的规则表示为约束

假设一个解决方案 $$X$$在9 x 9 x-9二进制阵列中表示。属性有什么作用 $$X$$有？首先，2-D网格（I，J）中的每个正方形都有一个值，因此3-D数组条目中恰好有一个非零元素 $$X（（\mathrm{一世}，，，，j，，，，1），，，，。。。，，，，X（（\mathrm{一世}，，，，j，，，，9）$$。换句话说，每一个 $$\mathrm{一世}$$和 $$j$$，，，，

同样，每行 $$\mathrm{一世}$$在2-D网格中，每个数字从1到9中都有一个值。换句话说，每个数字 $$\mathrm{一世}$$和 $$k$$，，，，

和每一列 $$j$$在2-D网格中具有相同的属性：每个 $$j$$和 $$k$$，，，，

主要的3乘3个网格具有相似的约束。对于网格元素 $$1\le \mathrm{一世}\le 3$$和 $$1\le j\le 3$$，每个 $$1\le k\le 9$$，，，，

要代表所有九个主要网格，只需向每个添加3或6个 $$\mathrm{一世}$$和 $$j$$指数：

$$\underset{\mathrm{一世}=1}{\overset{3}{\sum }}\underset{j=1}{\overset{3}{\sum }}X（（\mathrm{一世}+你，，，，j+v，，，，k）=1，，，，$$在哪里 $$你，，，，vϵ\{0，，，，3，，，，6\}。$$

明确线索

每个初始值（线索）可以表示为约束。假设那个 $$（（\mathrm{一世}，，，，j）$$线索是 $$m$$对于一些 $$1\le m\le 9$$。然后 $$X（（\mathrm{一世}，，，，j，，，，m）=1$$。约束 $$\underset{k=1}{\overset{9}{\sum }}X（（\mathrm{一世}，，，，j，，，，k）=1$$确保所有其他 $$X（（\mathrm{一世}，，，，j，，，，k）=0$$为了 $$k\ne m$$。

Sudoku在优化问题上

创建优化变量X那是二进制的，大小为9乘9 x-9。

x = optimvar（'X'，9,9,9，'类型'，，，，'整数'，，，，“下界”，0，“上行”，1）;

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

sudpuzzle = optimproblem;mul =一个（1,1,9）;mul =暨（mul，3）;sudpuzzle.Objective = sum（sum（sum（x，1），2）。*mul）;

表示约束的总和X在每个坐标方向上是一个。

sudpuzzle.constraints.consx = sum（x，1）== 1;sudpuzzle.constraints.consy = sum（x，2）== 1;sudpuzzle.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）==一个（1,1,9）;结尾结尾sudpuzzle.constraints.majorg = majorg;

通过在线索条目下设置1个下限来包括初始线索。此设置将相应条目的值修复为1，因此将解决方案设置为每个线索值为线索条目。

为了u = 1：size（b，1）x.LowerBound（b（u，1），b（u，2），b（u，3））= 1;结尾

解决Sudoku难题。

sudsoln = solve（sudpuzzle）

使用IntlinProg解决问题。LP：最佳目标值为405.000000。找到最佳解决方案。IntlinProg停止在根节点上，因为目标值在最佳值的间隙公差之内。INTCON变量是公差，options.integertolerance = 1E-05（默认值）的整数。

sudsoln =带有字段的结构：X：[9x9x9 double]

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

sudsoln.x = round（sudsoln.x）;y =一个（size（sudsoln.x））;为了k = 2：9 y（：，：，：，k）= k;每个深度k的乘数％结尾s = sudsoln.x。*y;％将每个条目乘以其深度s = sum（s，3）;％s是9 x-9，并保留解决的难题绘制

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

功能绘制Sudoku难题

类型画

功能绘制用于绘制Sudoku Board％版权2014 Mathworks，Inc。的函数（B）％函数。，3，“剪辑”，“ off”）％在边界矩形外（“位置”，[3,0,3,9]，“线宽”，2）％重的垂直线矩形（“位置”，[0,3，，，，9，，，，3],'LineWidth',2) % heavy horizontal lines rectangle('Position',[0,1,9,1],'LineWidth',1) % minor horizontal lines rectangle('Position',[0,4,9,1],'LineWidth',1) rectangle('Position',[0,7,9,1],'LineWidth',1) rectangle('Position',[1,0,1,9],'LineWidth',1) % minor vertical lines rectangle('Position',[4,0,1,9],'LineWidth',1) rectangle('Position',[7,0,1,9],'LineWidth',1) % Fill in the clues % % The rows of B are of the form (i,j,k) where i is the row counting from % the top, j is the column, and k is the clue. To place the entries in the % boxes, j is the horizontal distance, 10-i is the vertical distance, and % we subtract 0.5 to center the clue in the box. % % If B is a 9-by-9 matrix, convert it to 3 columns first if size(B,2) == 9 % 9 columns [SM,SN] = meshgrid(1:9); % make i,j entries B = [SN(:),SM(:),B(:)]; % i,j,k rows end for ii = 1:size(B,1) text(B(ii,2)-0.5,9.5-B(ii,1),num2str(B(ii,3))) end hold off end