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

作者:

最近做一些 优化问题 ,找到了 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.

类似文章:
编程 » Matlab, 优化
最近做了些东西,用到了 Matlab 的优化工具箱, optimization toolbox。因为以前没用过这东西,今天把这个工具箱的帮助文档基本上翻了一遍。
现在相机的像素实在是太高了,上次 去泰山玩 ,朋友的 1200 万像素的 D90 照出来的照片分辨率高达 4288×2848 ,即使转为 jpg 格式,每张都在 5M 以上。而现在电脑屏幕的分辨率最高也在 1920 以下吧,超高分辨率的照片除了打印大照片之外没什么用处,反而不方便传输、流通、保存。
基于将工作文件在家里电脑和公司电脑上的转移、Kindle 上电子书的管理的需求,我用 Matlab 写了几个函数,用来实现这些需求。
编程 » Matlab
在写 Matlab 程序时,函数的命名方式让人头疼,很难保证刚写的一个函数名在很久以前被用过,成为隐藏的一颗炸弹。
编程 » Matlab
Matlab 在启动时会自动运行脚本 startup.m。在这个脚本里可以自动修改当前目录,修改显示方式等等。比如
上次大规模使用 Matlab 还是本科的时候,当时还是 5.3 版,现在重新尝试它,已经是 7.8 ( R2009a ),而且 R2010b 版都已经发售。而这些版本引入的一个新玩意儿便是面向对象化编程( object-oriented programming , OOP )。
现在相机的像素实在是太高了,上次 去泰山玩 ,朋友的 1200 万像素的 D90 照出来的照片分辨率高达 4288×2848 ,即使转为 jpg 格式,每张都在 5M 以上。而现在电脑屏幕的分辨率最高也在 1920 以下吧,超高分辨率的照片除了打印大照片之外没什么用处,反而不方便传输、流通、保存。