网站LOGO
洗子的生活志
页面加载中
2月22日
网站LOGO 洗子的生活志
分享洗子的日常
菜单
  • 洗子的生活志
    分享洗子的日常
    用户的头像
    首次访问
    上次留言
    累计留言
    我的等级
    我的角色
    打赏二维码
    打赏博主
    0-1整数规划破解数独谜题
    点击复制本页地址
    微信扫一扫
    文章二维码
    文章图片 文章标题
    创建时间
  • 一 言
    确认删除此评论么? 确认
  • 本弹窗介绍内容来自,本网站不对其中内容负责。

    0-1整数规划破解数独谜题

    洗子 · 原创 ·
    趣味数模 · 趣味数模
    共 4360 字 · 约 3 分钟 · 233

    0-1整数规划破解数独谜题

    爱数学的uu们都爱玩的数独游戏,你知道还有其他解法吗?我们试试用0-1整数规划的方法,建立一个简单的数学模型,做一个程序来解答的数独吧!

    数独简介

    数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻游戏。玩家需要根据9x9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫3∗3内的数字均含1-9,不重复。
    数独数独
    那么我们怎么建立0-1整数规划模型来求解呢?再往下看看吧!

    问题分析

    本题关键思路是将谜题从 9×9 正方形网格转换为一个由0 或 1组成的 9×9×9 立方数组。将这个立方数组想象成由 9 个正方形网络上下堆叠在一起,其中每一层对应于 1 到 9 中的一个整数。如下图所示:

    顶部网格是数组的第一个正方形层,只要解或提示包含整数 1,则该层对应位置就为 1。只要解或提示包含整数 2,第二层对应位置就为 1。只要解或提示包含整数 9,第九层对应位置就为 1。这样我们就可以用坐标来表示出对应格子所填入的数字了,再加上符合规则的约束就可以求解数独了。

    模型建立

    基本思路确定了,接下来我们建立01规划模型啦!

    1. 定义决策变量
      设数据的位置坐标为:$x(i,j,k)$
      $x$的取值满足:

      $$ x(i,j,k)= \begin{cases} 0\text{,无提示且无解}\\ 1\text{,有提示或有解} \end{cases}\\ \text{其中,}i,k,k=1,2,3,...,9 $$

    2. 设置目标函数
      此处不需要目标函数,目标函数也可能是常数项 0。问题实际上只是求可行解,也就是满足所有约束的解,这里设置目标函数如下:

      $$ \min Z=\sum\limits_{i=1}^9\sum\limits_{j=1}^9\sum\limits_{k=1}^9 x(i,j,k). $$

    3. 确定约束条件
    • 由于二维网格$(i,j)$的每一个方格中都有且只有一个值,因此三维数组项中有且仅有一个非零元素,即:

      $$ \sum\limits_{k=1}^9x(i,j,k)=1. $$

    • 同理,每一行$i$中,1到9的数字都只能出现一次。即:

    $$ \sum\limits_{j=1}^9x(i,j,k)=1. $$

    • 每一列$j$中也同样存在这样的性质,即:

    $$ \sum\limits_{i=1}^9x(i,j,k)=1. $$

    • 3×3的网格内也有类似的约束,即:

    $$ \sum\limits_{i=1}^3\sum\limits_{j=1}^3 x(i+U,j+V,k)=1, $$

    其中,$U,V\in(0,3,6)$。

    模型求解

    1. 初始化数独谜题
      首先,我们先构建一个数独矩阵,并用MATLAB自带的drawSudoku绘制出数独图像。构建矩阵B来记录数独中已填写的数字。第一行 B(1,2,2) 表示第 1 行第 2 列的填入的数字为 2。第二行 B(1,5,3) 表示第 1 行第 5 列填入的数字为 3。
    matlab 代码:
    B = [1,2,2;1,5,3;1,8,4;    %第一行提示
        2,1,6;2,9,3;        %第二行提示
        3,3,4;3,7,5;        %第三行提示
        4,4,8;4,6,6;        %第四行提示
        5,1,8;5,5,1;5,9,6;    %第五行提示
        6,4,7;6,6,5;        %第六行提示
        7,3,7;7,7,6;        %第七行提示
        8,1,4;8,9,8;        %第八行提示
        9,2,3;9,5,4;9,8,2];    %第九行提示
    drawSudoku(B)
    1. 定义决策变量
    matlab 代码:
    % 定义变量x为9×9×9的矩阵,数据类型为整数,下界为0,上界为1
    x = optimvar('x',9,9,9,'Type','integer','LowerBound',0,'UpperBound',1); 
    
    1. 设置目标函数
    matlab 代码:
    sudpuzzle = optimproblem;
    mul = ones(1,1,9);
    mul = cumsum(mul,3);
    sudpuzzle.Objective = sum(sum(sum(x,1),2).*mul);
    1. 每行、每列、每层都只能填一个1的约束条件
    matlab 代码:
    sudpuzzle.Constraints.consx = sum(x,1) == 1;
    sudpuzzle.Constraints.consy = sum(x,2) == 1;
    sudpuzzle.Constraints.consz = sum(x,3) == 1;
    1. 每一个3×3的格子里填写数据不重复的约束条件
    matlab 代码:
    majorg = optimconstr(3,3,9);
    for u = 1:3
        for v = 1:3
            arr = x(3*(u-1)+1:3*(u-1)+3,3*(v-1)+1:3*(v-1)+3,:);
            majorg(u,v,:) = sum(sum(arr,1),2) == ones(1,1,9);
        end
    end
    sudpuzzle.Constraints.majorg = majorg;
    1. 将提示处的解设置为1
    matalb 代码:
    for u = 1:size(B,1)
        x.LowerBound(B(u,1),B(u,2),B(u,3)) = 1;
    end
    1. 进行求解
    matlab 代码:
    sudsoln = solve(sudpuzzle)
    1. 将求解结果填入数独表中
    matlab 代码:
    sudsoln.x = round(sudsoln.x);
    
    y = ones(size(sudsoln.x));
    for k = 2:9
        y(:,:,k) = k; 
    end
    S = sudsoln.x.*y; 
    S = sum(S,3); 
    drawSudoku(S)

    求解结果如下:

    完整代码如下:

    matlab 代码:
    clc;clear
    %% 初始化数独谜题
    B = [1,2,2;1,5,3;1,8,4;    %第一行提示
        2,1,6;2,9,3;        %第二行提示
        3,3,4;3,7,5;        %第三行提示
        4,4,8;4,6,6;        %第四行提示
        5,1,8;5,5,1;5,9,6;    %第五行提示
        6,4,7;6,6,5;        %第六行提示
        7,3,7;7,7,6;        %第七行提示
        8,1,4;8,9,8;        %第八行提示
        9,2,3;9,5,4;9,8,2];    %第九行提示
    drawSudoku(B)
    
    %% 定义决策变量
    % 定义变量x为9×9×9的矩阵,数据类型为整数,下界为0,上界为1
    x = optimvar('x',9,9,9,'Type','integer','LowerBound',0,'UpperBound',1); 
    
    %% 设置目标函数
    sudpuzzle = optimproblem;
    mul = ones(1,1,9);
    mul = cumsum(mul,3);
    sudpuzzle.Objective = sum(sum(sum(x,1),2).*mul);
    
    %% 每行、每列、每层都只能填一个1的约束条件
    sudpuzzle.Constraints.consx = sum(x,1) == 1;
    sudpuzzle.Constraints.consy = sum(x,2) == 1;
    sudpuzzle.Constraints.consz = sum(x,3) == 1;
    
    %% 每一个3×3的格子里填写数据不重复的约束条件
    majorg = optimconstr(3,3,9);
    for u = 1:3
        for v = 1:3
            arr = x(3*(u-1)+1:3*(u-1)+3,3*(v-1)+1:3*(v-1)+3,:);
            majorg(u,v,:) = sum(sum(arr,1),2) == ones(1,1,9);
        end
    end
    sudpuzzle.Constraints.majorg = majorg;
    
    %% 将提示处的解设置为1
    for u = 1:size(B,1)
        x.LowerBound(B(u,1),B(u,2),B(u,3)) = 1;
    end
    
    %% 进行求解
    sudsoln = solve(sudpuzzle)
    
    %%  将求解结果填入数独表中
    sudsoln.x = round(sudsoln.x);
    
    y = ones(size(sudsoln.x));
    for k = 2:9
        y(:,:,k) = k; 
    end
    S = sudsoln.x.*y; 
    S = sum(S,3); 
    drawSudoku(S)
    声明:本文由 洗子(博主)原创,依据 CC-BY-NC-SA 4.0 许可协议 授权,转载请注明出处。

    还没有人喜爱这篇文章呢

    发一条! 发一条!
    博客logo 洗子的生活志 分享洗子的日常 百度统计
    ICP 粵ICP备2022146502号

    🕛

    本站已运行 95 天 4 小时 49 分

    🌳

    自豪地使用 Typecho 建站,并搭配 MyLife 主题
    洗子的生活志. © 2023 ~ 2024.
    网站logo

    洗子的生活志 分享洗子的日常
     
     
     
     
    壁纸
     
     
     
     

    2