[程序分享] [转] 用Matlab解数独游 [推广有奖]

原文：整数规划思想求解数独游戏
最近做一些优化问题，找到了YALMIP工具包。在其帮助文件里看到如何使用该工具包求解sudoku，整个思路是将问题转化为整数规划问题。这样的思路以前也想到过，但总觉得整数规划问题的求解会更复杂。但是下面的Matlab代码，显示它可以非常简洁，思路见程序的注释（程序运行需要安装YALMIP工具包）：

1. % 初始状态，0表示没填的格子
   
2. S=[ 9 0 0 0 0 0 0 0 5
   
3.     0 4 0 3 0 0 0 2 0
   
4.     0 0 8 0 0 0 1 0 0
   
5.     0 7 0 6 0 3 0 0 0
   
6.     0 0 0 0 8 0 0 0 0
   
7.     0 0 0 7 0 9 0 6 0
   
8.     0 0 1 0 0 0 9 0 0
   
9.     0 3 0 0 0 6 0 4 0
   
10.     5 0 0 0 0 0 0 0 8];
    
11. 
    
12. % 定义0、1数组 A(i, j, k) = 1，如果方格(i, j)里的数为k；否则为0。
    
13. % 求解sudoku问题即求一定假设条件下的解。
    
14. p = 3;
    
15. A = binvar(p^2,p^2,p^2,'full');
    
16. 
    
17. % 以下为限制条件
    
18. F = [sum(A,1) == 1]; % 限制每行每个数恰好一个
    
19. F = [F, sum(A,2) == 1]; % 限制每列每个数恰好一个
    
20. F = [F, sum(A,3) == 1]; % 限制每个单元格子里恰好一个数
    
21. 
    
22. for m = 1:p
    
23.     for n = 1:p
    
24.         for k = 1:p^2
    
25.             s = sum(sum(A((m-1)*p+(1:p),(n-1)*p+(1:p),k)));
    
26.             F = [F, s == 1];  % 限制每个3×3的方框里每个数恰好出现一次
    
27.         end
    
28.     end
    
29. end
    
30. 
    
31. for i = 1:p^2
    
32.     for j = 1:p^2
    
33.         if S(i,j)
    
34.             F = [F, A(i,j,S(i,j)) == 1]; % 初始给定的数要一直
    
35.         end
    
36.     end
    
37. end
    
38. 
    
39. % 直接求解
    
40. sol = solvesdp(F);
    
41. 
    
42. Z = 0;
    
43. for i = 1:p^2
    
44.       Z = Z  + i*double(A(:,:,i)); % 简单相加即可
    
45. end
    
46. Z % 输出结果

复制代码

或者直接下载源代码文件：
sudoku.m1.0 KiB
调用Matlab的整数规划函数求解数独，程序只有20行。
程序中的例子S是我在网上搜「最难 数独」找到的一个例子，程序在几秒钟内便能找出答案。
我以前有段时间特别喜欢玩数独，曾经把PSP上的一个数独游戏玩穿（大概有150关）。现在发现，人所谓的那点逻辑推理能力，在强大的计算能力前面不堪一击。