# 通过整数规划求解数独谜题：基于问题

### 初始谜题

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) % For the listing of this program, see the end of this example.

2009 年发布的 Cleve's Corner 中介绍了此谜题以及一种备选的 MATLAB® 求解方法。

### 将数独规则表示为约束

$\sum _{k=1}^{9}x\left(i,j,k\right)=1.$

$\sum _{j=1}^{9}x\left(i,j,k\right)=1.$

$\sum _{i=1}^{9}x\left(i,j,k\right)=1.$

3×3 粗线网格具有类似的约束。对于 $1\le i\le 3$$1\le j\le 3$ 的网格元素，对于每层 $1\le k\le 9$ 都满足：

$\sum _{i=1}^{3}\sum _{j=1}^{3}x\left(i,j,k\right)=1.$

$\sum _{i=1}^{3}\sum _{j=1}^{3}x\left(i+U,j+V,k\right)=1,$ 其中 $U,V\phantom{\rule{0.5em}{0ex}}ϵ\phantom{\rule{0.5em}{0ex}}\left\{0,3,6\right\}.$

### 以优化问题的形式求解数独

x = optimvar('x',9,9,9,'Type','integer','LowerBound',0,'UpperBound',1);

sudpuzzle = optimproblem;
mul = ones(1,1,9);
mul = cumsum(mul,3);
sudpuzzle.Objective = sum(sum(sum(x,1),2).*mul);

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);

for u = 1:3
for 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) == ones(1,1,9);
end
end
sudpuzzle.Constraints.majorg = majorg;

for u = 1:size(B,1)
x.LowerBound(B(u,1),B(u,2),B(u,3)) = 1;
end

sudsoln = solve(sudpuzzle)
Solving problem using intlinprog.
LP:                Optimal objective value is 405.000000.

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
sudsoln = struct with fields:
x: [9x9x9 double]

sudsoln.x = round(sudsoln.x);

y = ones(size(sudsoln.x));
for k = 2:9
y(:,:,k) = k; % multiplier for each depth k
end
S = sudsoln.x.*y; % multiply each entry by its depth
S = sum(S,3); % S is 9-by-9 and holds the solved puzzle
drawSudoku(S)

### 用于绘制数独谜题的函数

type drawSudoku
function drawSudoku(B)
% Function for drawing the Sudoku board

%   Copyright 2014 The MathWorks, Inc.

figure;hold on;axis off;axis equal % prepare to draw
rectangle('Position',[0 0 9 9],'LineWidth',3,'Clipping','off') % outside border
rectangle('Position',[3,0,3,9],'LineWidth',2) % heavy vertical lines
rectangle('Position',[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