4
整数规划思想求解数独游戏
source link: https://zhiqiang.org/coding/integer-programming-solving-sudoku.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
整数规划思想求解数独游戏
最近做一些优化问题，找到了 YALMIP 工具包。在其帮助文件里看到如何使用该工具包求解 sudoku，整个思路是将问题转化为整数规划问题。这样的思路以前也想到过，但总觉得整数规划问题的求解会更复杂。但是下面的 Matlab 代码，显示它可以非常简洁，思路见程序的注释（程序运行需要安装 YALMIP 工具包）：
% 初始状态，0表示没填的格子
S=[ 9 0 0 0 0 0 0 0 5
0 4 0 3 0 0 0 2 0
0 0 8 0 0 0 1 0 0
0 7 0 6 0 3 0 0 0
0 0 0 0 8 0 0 0 0
0 0 0 7 0 9 0 6 0
0 0 1 0 0 0 9 0 0
0 3 0 0 0 6 0 4 0
5 0 0 0 0 0 0 0 8];
% 定义0、1数组 A(i, j, k) = 1，如果方格(i, j)里的数为k；否则为0。
% 求解sudoku问题即求一定假设条件下的解。
p = 3;
A = binvar(p^2,p^2,p^2,'full');
% 以下为限制条件
F = [sum(A,1) == 1]; % 限制每行每个数恰好一个
F = [F, sum(A,2) == 1]; % 限制每列每个数恰好一个
F = [F, sum(A,3) == 1]; % 限制每个单元格子里恰好一个数
for m = 1:p
for n = 1:p
for k = 1:p^2
s = sum(sum(A((m-1)*p+(1:p),(n-1)*p+(1:p),k)));
F = [F, s == 1]; % 限制每个3×3的方框里每个数恰好出现一次
end
end
end
for i = 1:p^2
for j = 1:p^2
if S(i,j)
F = [F, A(i,j,S(i,j)) == 1]; % 初始给定的数要一直
end
end
end
% 直接求解
sol = solvesdp(F);
Z = 0;
for i = 1:p^2
Z = Z + i*double(A(:,:,i)); % 简单相加即可
end
Z % 输出结果
或者直接下载源代码文件：
程序中的例子 S 是我在网上搜「最难 数独」找到的一个例子，程序在几秒钟内便能找出答案。
我以前有段时间特别喜欢玩数独，曾经把 PSP 上的一个数独游戏玩穿（大概有 150 关）。现在发现，人所谓的那点逻辑推理能力，在强大的计算能力前面不堪一击。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK