最初的难题

这是一个数据矩阵B.线索。第一行，B（1,2,2），表示第1行，第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年。

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

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

二进制整数编程方法

关键的想法是将一个拼图从正方形的9×9网格转换为立方9-×9的二进制值（0或1）。将立方体阵列识别为9个平方网格彼此堆叠，其中每个层对应于1到9的整数。顶部网格，阵列的方形层，无论何处都有1个吗？在溶液或线索的情况下，第二层具有1。第九层的溶液或线索具有9。

该配方恰恰适用于二进制整数编程。

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

向Sudoku的规则表达为约束

假设一个解决方案 $$X$$以9×9×9二进制阵列表示。什么属性有什么关系 $$X$$有什么?首先，二维网格(i,j)中的每个正方形都只有一个值，因此在三维数组项中只有一个非零元素 $$X（\mathrm{一世}那j那1的）那。。。那X（\mathrm{一世}那j那9.的）$$。换句话说，为每一个 $$\mathrm{一世}$$和 $$j$$那

同样，在每一行中 $$\mathrm{一世}$$在二维网格中，从1到9的每个数字都有一个值。换句话说，对于每一个 $$\mathrm{一世}$$和 $$\mathrm{K.}$$那

和每个列 $$j$$在2-D网格中具有相同的财产：每个 $$j$$和 $$\mathrm{K.}$$那

主要的3 × 3网格也有类似的限制。对于网格元素 $$1\le .\mathrm{一世}\le .3.$$和 $$1\le .j\le .3.$$，以及每个人 $$1\le .\mathrm{K.}\le .9.$$那

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

$$\underset{\mathrm{一世}=1}{\overset{3.}{\sigma .}}\underset{j=1}{\overset{3.}{\sigma .}}X（\mathrm{一世}+你那j+\mathrm{V.}那\mathrm{K.}的）=1那$$在哪里 $$你那\mathrm{V.}ϵ\{0.那3.那6.\}。$$

表达的线索

每个初值(线索)都可以表示为一个约束。假设 $$（\mathrm{一世}那j的）$$线索是 $$\mathrm{M.}$$对于一些 $$1\le .\mathrm{M.}\le .9.$$。然后 $$X（\mathrm{一世}那j那\mathrm{M.}的）=1$$。约束 $$\underset{\mathrm{K.}=1}{\overset{9.}{\sigma .}}X（\mathrm{一世}那j那\mathrm{K.}的）=1$$确保所有其他 $$X（\mathrm{一世}那j那\mathrm{K.}的）=0.$$为了 $$\mathrm{K.}\ne \mathrm{M.}$$。

Sudoku优化问题形式

创建优化变量X这是二进制和大小9-×9-9。

x = Optimvar（“x”9日,9日,9日“类型”那“整数”那'indowbound'0,'上行'1);

使用相当任意的目标函数创建优化问题。目标函数可以通过销毁问题的固有对称来帮助解决方案。

sudpuzzle = OptimProblem;mul = sone（1,1,9）;mul = cumsum（mul，3）;sudpuzzle.objective = sum（sum（sum（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;

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

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

解决sudoku拼图。

sudsoln =解决（sudpuzzle）

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

sudsoln =结构体字段:X：[9x9x9双]

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

sudsoln.x = round（sudsoln.x）;y = y =（size（sudsoln.x））;为了y(:，:， K) = K;每个深度k％乘数k结尾s = sudsoln.x。* y;％乘以其深度的每个条目S =(年代,3)总和;％s是9×9并保持求助的拼图drawSudoku (S)

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

函数绘制数独拼图

类型drawsudoku.

函数drawsudoku（b）％函数用于绘制Sumoku Board％2014 The Mathworks，Inc。图;保持ON;轴关闭;轴等％准备绘制矩形（'位置'，[0 0 9 9]，'LIEWWIDTH'3，'剪切'，'关闭'）％边框矩形（'位置'，[3,0,3,9]，'LineWidth'，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