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

作者: , 共 1180 字

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

类似文章:
现在相机的像素实在是太高了,上次去泰山玩,朋友的 1200 万像素的 D90 照出来的照片分辨率高达 4288×2848 ,即使转为 jpg 格式,每张都在 5M 以上。而现在电脑屏幕的分辨率最高也在 1920 以下吧,超高分辨率的照片除了打印大照片之外没什么用处,反而不方便传输、流通、保存。
编程 » Matlab, 优化
最近做了些东西,用到了 Matlab 的优化工具箱, optimization toolbox。因为以前没用过这东西,今天把这个工具箱的帮助文档基本上翻了一遍。
最近看了几个风险管理和组合管理系统,有几个系统里附带了组合优化模块,也了解到这一方面工业界的最新成果。最新的组合优化模块被称为第二代最优化模型,主要成果就是二阶锥优化算法的应用,其中一个重要的改进为对 alpha 估计的不准确性考虑在内。
基于将工作文件在家里电脑和公司电脑上的转移、Kindle 上电子书的管理的需求,我用 Matlab 写了几个函数,用来实现这些需求。
在 MIT BBS 上看到一个有趣的题目
递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
编程 » Matlab
第一步,which函数可用来获取 Matlab 函数的全路径(包含路径和文件名)。
相似度: 0.050
编程 » Matlab
写了一个统计代码量的函数,函数已上传到 Matlab Central File Exchange下载地址,使用方法:
上次大规模使用 Matlab 还是本科的时候,当时还是 5.3 版,现在重新尝试它,已经是 7.8 ( R2009a ),而且 R2010b 版都已经发售。而这些版本引入的一个新玩意儿便是面向对象化编程( object-oriented programming , OOP )。
现在相机的像素实在是太高了,上次去泰山玩,朋友的 1200 万像素的 D90 照出来的照片分辨率高达 4288×2848 ,即使转为 jpg 格式,每张都在 5M 以上。而现在电脑屏幕的分辨率最高也在 1920 以下吧,超高分辨率的照片除了打印大照片之外没什么用处,反而不方便传输、流通、保存。