整数规划思想求解数独游戏

作者:, 发表于

生活中的Matlab

查看该系列所有文章

最近做一些优化问题,找到了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 % 输出结果

或者直接下载源代码文件:

sudoku.m 1.0 KiB
调用Matlab的整数规划函数求解数独,程序只有20行。

程序中的例子S是我在网上搜「最难 数独」找到的一个例子,程序在几秒钟内便能找出答案。

我以前有段时间特别喜欢玩数独,曾经把PSP上的一个数独游戏玩穿(大概有150关)。现在发现,人所谓的那点逻辑推理能力,在强大的计算能力前面不堪一击。

Q.E.D.


上一篇:Matlab中用类封装函数2010年9月24日
上次大规模使用Matlab还是本科的时候,当时还是5.3版,现在重新尝试它,已经是7.8(R2009a),而且R2010b版都已经发售。而这些版本引入的一个新玩意儿

下一篇:批量修改图片大小的Matlab脚本2010年10月1日
现在相机的像素实在是太高了,上次去泰山玩,朋友的1200万像素的D90照出来的照片分辨率高达4288×2848,即使转为jpg格式,每张都在5M以上。而现在电脑


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。