克里夫的角落:克里夫硅藻土在数学和计算
MATLAB的博客
史蒂夫与MATLAB图像处理
人在仿真软件金宝app
人工智能
开发区域
斯图尔特的MATLAB视频
在标题后面
文件交换的选择
汉斯在物联网
学生休息室
MATLAB社区
MATLABユーザーコミュニティー
创业、加速器,和企业家
自治系统用MATLAB解决数独
今天的嘉宾是条韦斯利·汉密尔顿,在MathWorks茎推广工程师。卫斯理的角色包括推广使用MATLAB和Simulink年轻的民间,特别是对数学主题,这个博客是一个伴随金宝app车间正在运行的国家博物馆的数学在纽约市。
数独是一种受欢迎的难题玩家填写数字1 - 9的9 x9网格满足这样的条件:每3 x3的次网格,行和列必须包含所有的数字。虽然数独是通常称为逻辑难题,它实际上是可能重塑这些谜题(数学)约束优化问题,在最优解被解释为输入一个完整的数独谜题。疯狂的配方是函数我们优化将是零,所以任何输入是最优的;所有的麻烦都是在满足优化问题的约束条件。感兴趣吗?往下读,学习更多!
表示和代码在这个博客是改编自一个研讨会由蒂姆•查特博士基于合作开发的代码的艾米Langville查尔斯顿学院的博士和她的学生。
表的内容
规则和历史的数独游戏
数独大多数人都熟悉的经典版本由9 x9网格划分为9个3 x3的宫。网格将开始与一些箱子填写数字1 - 9,游戏的目标是填写每个箱子的9位数的方式满足以下三个条件:
- 网格的每一行包含的每个数字1 - 9,和每个数字只出现一次,
- 每一列的网格的每个包含数字1 - 9,和每个数字只出现一次,
- 每3 x3次网格的每个包含数字1 - 9,每个数字只能出现一次。
这是一个9 x9数独谜题,从检索websudoku.com2023年5月3日。
谜题的一个变体是4 x4的版本,4 x4的网格分成四个2 x2的宫和修改三个条件,因此只有使用数字1 - 4。这个版本通常是比9 x9作为一个更简单的版本,并使可视化的计算方面更容易处理。
这里有一个例子4 x4的数独谜题,所产生的蒂姆·查特博士,MoMath 2022 - 2023的公共传播杰出客座教授数学。
数独是流行在日本在1980年代末,在2000年代初之前抓住全世界的关注。很多不知道,数独的早期版本出现在法国在1800年代末的puzzle-variations魔术方块;看到维基百科页面为更多的信息和参考。
下一节讨论解决数独谜题的基础知识。如果你已经非常熟悉数独,随意跳过的文本之后完成的4 x4的难题。
解决数独谜题,第1部分
所以如何解决数独谜题吗?在实践中,我们反复应用的三个条件去识别哪些数字框,直到所有的盒子都填写。在困难谜题,我们可能会被迫做出选择在两个同样可能的条目;在这些情况下,我们通常会尝试在其中一个选项,看其他数字可以填写在此基础上,然后遇到一个矛盾,或解决。
让我们看看这个过程与蒂姆的4 x4行动难题。为了清楚起见,我们会反复检查的三个条件是:
- 网格的每一行包含的每个数字1 - 4,每个数字只出现一次,
- 每一列的网格的每个包含数字1 - 4,每个数字只能出现一次,
- 每2 x2 1 - 4次网格包含每一个数字,每个数字只出现一次。
首先我们将重点放在右上角2 x2次网格,确定我们可以填写一个数字,在红色圆圈或蓝色的正方形。
应用条件3。,we know that the digits in these empty grid boxes have to be 2 and 3. So which digit goes where? By condition 2., each column of the grid can only contain each digit exactly once, and the fourth column (containing the blue square) already contains a 2, so it is not possible to write the digit 2 in the blue square (similarly, by condition 1. the row with the blue square already has the digit 2 somewhere in the row). Thus, the digit 2 goes in the square with the red circle.
应用条件3。同一次网格,我们得出其余网格框必须包含数字3。
以这种方式继续我们最终能够填写每箱;例如,下一步可能是写在数字4在仅存的盒子在第二行。请自己尝试解决这个4 x4,并检查您的解决方案对我们的:
太棒了!但是,如果我们想要MATLAB解决这个难题吗?最初的方法可能是代码(以某种方式)这三个约束条件和我们的电脑遍历每一行,列和次网格在数字一个接一个。如果有两个数字可能会工作在一个网格的箱子吗?还有其他可能发生在一个逻辑步骤困难难题,我们不能预测?
而不是采取这种方式,我们将非常不同,甚至更聪明、方法利用一些深度和强大的计算数学称为线性规划。
线性规划
线性规划是,简而言之,一个最优化问题的目标函数和约束条件都是线性的。让我们打破这些碎片是什么意思:
- 一个优化问题是哪一个的问题寻求目标函数的最大(或最小),即找到一个值x给定函数最大化f (x)美元;
- 一个目标函数是我们想要的功能最大化或最小化。我们可以称它为一个函数,但通常在多种功能发挥作用的优化问题,包括函数,添加约束问题,除了我们优化的函数;
- 一个线性目标函数是一个目标函数是线性的,即需要表单吗$ f (x) = a_1 x_1 + \ cdots + an x_n美元,对于一个向量$ x = \ pmatrix {x_1 \ cr \ vdots \ cr x_n} $。写作$ = \ pmatrix {a_1 \ cr \ vdots \ cr an} $,这个函数也可以表达f (x) = ^ t x美元美元,那里的t上标意味着我们把一个向量的矩阵的转置。
- 一个约束值的规则吗x是可行的,即。x必须是非负数,或者x是一个向量的所有组件x必须是非负数;
- 一个线性约束条件是一个约束,用线性方程的形式写的。例如,如果我们正在与一个向量$ x = \ pmatrix {x_1 \ cr x_2 \ cr x_3} $,然后一个线性约束的样子x_1 - x_2 + 3美元x_3 \ leq 0美元。如果我们写$ b = \ pmatrix {1 \ cr 1 \ cr 3} $,那么这个线性约束也可以写b ^ t x \ leq 0美元,那里的t上标意味着我们把一个向量的矩阵的转置。
线性约束可以有两种形式:线性不等式(Ax \ leq b美元)和线性等式(美元现代x = b_ {eq} {eq} $)。两种约束的线性计划我们将在这里工作都可以用以下形式:
找到一个向量x最大化f (x) = ^ t x美元美元受Ax \ leq b美元,美元现代x = b_ {eq} {eq} $,x \组0美元,
在哪里$ a、b b_ {eq} $给出了向量,然后呢一个美元,现代{eq} $给出了矩阵编码的线性约束。注意,如果$ x = \ pmatrix {x_1 \ cr \ vdots \ cr x_n} $,那么符号x \组0美元意味着x_i \组0美元为$ i = 1,……n美元。的组件x_i美元向量的x通常被称为决策变量,因为这些值的线性程序需要决定,或者找到的值。
在本帖里,我们将使用MATLABintlinprog功能,您可以将其视为一个黑盒线性规划求解发现整数线性规划解决方案。金宝搏官方网站这个解算器自动选择使用哪种算法,找到一个解决方案,所以我们唯一要做的就是写的工作线性规划在某种程度上可以理解。接下来我们将这样做。
记住,我们使用矩阵乘法公式表达的约束。矩阵乘法的背景和基础的线性代数的概念,看看我们的互动课件模块线性代数的矩阵方法。
数独是一个线性规划
建立数独谜题作为线性规划,我们需要确定几件事:
- 我们求解的变量是什么?
- 我们想强加的约束是什么?
- 什么是我们想要的功能最大化?
为什么不确定函数在约束呢?哦,原来我们实际上并不关心这个函数是什么,年底将明确本节。
变量应该是什么?4 x4网格我们总共有16个填写框,和最初的方法可能是使用变量x_1美元,…间,{16}$其中每个x_i美元应该价值之间1和4。虽然合理,但实际上是一个计算方法简单。
而不是使用变量来告诉我们哪位是在每一个盒子,让我们使用变量来告诉我们一个数字是否在一个盒子里。这是指使用变量美元间{ijk} $,两人(i, j)美元告诉我们哪个盒子我们看,k指定的数字我们关心。如果美元间{ijk} = 0美元,那么数字k不应该写在箱子吗(i, j)美元,而如果美元间{ijk} = 1美元,那么数字k属于盒子(i, j)美元。
作为一个例子,考虑我们之前考虑的4 x4网格(添加了一些盒子indec左上的角落清晰):
网格箱数量,(1)美元将左上的盒子,(2,1)美元将下面的盒子,(1、2)美元将右边的盒子吗(1)美元。换句话说,第一个索引我在(i, j)美元数量多少行,和索引j有多少列向右。
所以我们用这个符号,数字4在(1、4)美元盒子,数字1在(2、3)美元盒子,和数字2在(3、4)美元盒子在start ()。尤其是数字美元1、2、3美元不出现在(1、4)美元盒子。使用我们的变量编码这个信息,我们会美元间的{1 4 4}= 1美元和美元间的{1 4 1}=间{1,4,2}=间{1,4,3}= 0美元。在拼图的开始我们并不知道这数字进去(1、3)美元盒子,所以在开始美元间的{1 3 k} $没有指定的$ k = 1,……4美元。使用数独游戏的规则,我们确定的2属于那个盒子,所以我们的结论是,通过使用约束美元间的{1,3,2}= 1美元和美元间的{1,3,1}=间{1,3,3}=间{1,3,4}= 0美元。现在我们有指定的变量,我们可以指定约束。
那么我们如何编码数独的约束到这个框架?记住有三个约束从原来的难题,我们需要编码。有第四个约束我们需要编码,如上方所讨论的,在每个箱子里只能有一个数字写在里面。
箱约束
第一个约束我们需要编码是每箱只能有一个数字写在里面。所以,为(i, j)美元框,一旦数字1写在它(例如),我们得到了什么美元间{i, j, 1} = 1美元和美元间{i, j 2} =间{i, j 3} =间{i, j 4} = 0美元。这里的诀窍是,每个变量的值应该0或1(什么),所以如果我们总和并设置之和等于1,确保只有一个变量的值1。写出明确,为每个盒子(i, j)美元我们要求:
美元间{i, j, 1} +间{i, j 2} +间{i, j 3} +间{i, j 4} = 1美元。
行约束
第一个问题的约束是网格的每一行每一个数字,每个数字只能出现一次。因为我们看行,我们要关注的变量集美元间的{}我1 k,间{我2 k},间{我3 k},间{我4 k} $为$ i = 1,……4美元和$ k = 1,……4美元。上面的技巧是一样的,在每个变量应该采取的价值0或1(什么),所以如果我们总和他们在解决难题,我们应该得到1:
美元间{我1 k} +间{我2 k} +间{我3 k} +间{我4 k} = 1美元。
只要一个美元间{i, j, k} $需要的值1,其余被迫0。这将确保,我th行数字k只出现一次。为每一个可能的行这个约束应持有我和可能的数字k。
列约束
列约束建立了完全一样的行约束,除非我们对行indec而不是列indec求和:
美元间的{1 j k} +间{2 j k} +间{3 j k} +间{4 j k} = 1美元,
这对每一个可能的平等应列j和数字k。
次网格约束
最后的数独谜题约束来实现是次网格规则,每一个四位数的存在于每个2 x2的宫。作为一个具体的例子来指导我们的工作,可以考虑在左上的次网格组成的盒子美元(1,1),(1、2),(2,1),(2,2)美元。次网格约束指定每个数字k只有一次出现在这四个盒子,所以我们会有四个的次网格约束:
美元间的{1 1 k} +间{1 2 k} +间{2 1 k} +间{2 2 k} = 1美元,$ k = 1,……4美元。
有四个宫,所以我们还需要把这些约束:
美元间的{1 3 k} +间{1 4 k} +间{2 3 k} +间{2 4 k} = 1美元,$ k = 1,……4美元,
美元间{3 1 k} +间{3 2 k} +间{4 1 k} +间{4 2 k} = 1美元,$ k = 1,……4美元,
美元间{3 3 k} +间{3 4 k} +间{4 3 k} +间{4 4 k} = 1美元,$ k = 1,……4美元。
这是一个很多!好东西我们不需要手工处理这些方程,用MATLAB为我们做所有的重担!
我们需要做的最后一件事就是指定我们的目标函数是什么,我们实际上最小化。事情是这样的,不过,我们已经编码的一切我们想跟踪通过变量和约束,所以没有任何需要为一个特定的函数。这意味着,对于我们的目的,我们免费设置功能f (x) = 0美元。在这种情况下,任何向量x最大化的函数,所以所有的工作进入找到一个向量x满足约束条件。如果这仍然看起来很奇怪,你不是一个人;如果有帮助,欢迎你有信心,我们会得到一个解决方案使用这个奇怪的功能,就很好了。
总结我们的工作在这一节中,我们在解决线性规划如下:
找到一个向量$ x = \ pmatrix{间{1 1 1}\ cr间{1 1 2}\ cr \ vdots \ cr间{4,4,4}}$最大化的函数f (x) = 0美元、受约束
- 美元间{i, j, 1} +间{i, j 2} +间{i, j 3} +间{i, j 4} = 1美元为$ i = 1,……4美元和j = 1美元,…4美元(箱约束)
- 美元间{我1 k} +间{我2 k} +间{我3 k} +间{我4 k} = 1美元为$ i = 1,……4美元和$ k = 1,……4美元(行约束)
- 美元间的{1 j k} +间{2 j k} +间{3 j k} +间{4 j k} = 1美元为j = 1美元,…4美元和$ k = 1,……4美元(列约束)
- 美元间的{1 1 k} +间{1 2 k} +间{2 1 k} +间{2 2 k} = 1美元为$ k = 1,……4美元(左上的次网格约束)
- 美元间的{1 3 k} +间{1 4 k} +间{2 3 k} +间{2 4 k} = 1美元为$ k = 1,……4美元(右上的次网格约束)
- 美元间{3 1 k} +间{3 2 k} +间{4 1 k} +间{4 2 k} = 1美元为$ k = 1,……4美元(左下侧次网格约束)
- 美元间{3 3 k} +间{3 4 k} +间{4 3 k} +间{4 4 k} = 1美元为$ k = 1,……4美元。次网格约束(右下方)
请注意,所有这些工作只是数独的4 x4版本;我们如何修改一切原始9 x9版本吗?花一分钟的时间思考,然后读了一个解决方案…后来我们在MATLAB中实现一切,真正解决一些难题。
9 x9版本,简单的变化,总结应包括9项无处不在,和indec美元$ i, j, k应该每个范围从1来9无处不在。更多的参与修改,将会有九次网格的约束,而不是四个,自从9 x9网格包含9个3 x3的宫。左上的3 x3的次网格将有约束
美元间的{1 1 k} +间{1 2 k} +间{1 3 k} +间{2 1 k} +间{2 2 k} +间{2 3 k} +间{3 1 k} +间{3 2 k} +间{3 3 k} = 1美元,因为$ k = 1,……9美元。
另一次网格约束可以写出类似的(稍微麻烦)。
解决数独谜题,第2部分
在本节中,我们将编码我们上面描述的约束和实际使用线性规划解决数独谜题。
还有一个组约束,我们需要实施,独立于我们的框架和数独游戏的规则。请记住,数独谜题开始的一些网格框填写,我们可以指定一个矩阵G指定行号、列号和数字的初始条目。作为一个具体的例子,我们的4 x4示例$ G = \ pmatrix {1 & 4 & 4 \ cr 2 & 1 & 2 \ cr 2 & 3 & 1 \ cr 3 & 1 & 3 \ cr 3 & 4 & 2} $;第一行是4美元(1 \ \ 4)美元自从我们开始数字4在第一行和第四列,等等。
要做的第一件事就是指定大小的数独网格处理:
n = 4;% 4×4数独问题
% n = 9;% 9的9数独问题
决策变量的顺序
记住,变量的向量,指定的数字出现在网格中,n ^ 3美元条目:n \ n美元网格中的条目对应于每个箱子,另一个地方n为n可能的数字。我们需要注意的一件事是什么顺序决策变量出现在我们的向量。三个(+ 1)合理的选项是:
- 命令的变量递增数字指数第一,然后列索引,然后行指数:美元间的{1 1 1},间{1 1 2},…,x_{1,1,4}, x_{1,2,1}, x_{1,2,2}, ... $这个枚举将列出所有数字设计变量之前,先去一个新盒子。
- 顺序变量递增行指数第一,然后列索引,那么数字指数:美元间的{1 1 1},间{2 1 1},…,x_{4,1,1}, x_{1,2,1}, x_{2,2,1}, ... $这个枚举将遍历整个电网通过列然后横跨行,之前增加数字索引和遍历一遍。
- 命令的变量递增列指数第一,然后行索引,那么数字指数:美元间的{1 1 1},间{1、2、1},…,x_{1,4,1}, x_{2,1,1}, x_{2,2,1}, ... $这类似于前面的可能的枚举,除了我们首先遍历网格沿行,列,然后沿着位数。
- 顺序随机变量。
的第四个选项并不是合理的,因为你会有更多的记账管理(尽管从技术上讲,这是可能实现!)。这里我们将选择两个,每组n ^ 2美元组件的决策向量x对应于同一位枚举列,然后行。
即,我们的实现,x (1)告诉我们是否数字1是在(1)美元盒子,x (n ^ 2 + 1)如果数字告诉我们2是在(1)美元箱等等。同样地,x (2)如果数字告诉我们1是在(2,1)美元盒子,x (3)如果数字告诉我们1是在(1)美元盒子,x (n ^ 2 + 2)如果数字告诉我们2是在(2,1)美元箱等。
额外的挑战:使用另外两个实现这个数独(合理)下令设计变量的方法。额外的加分实现随机排序的方法。
接下来让我们编码约束矩阵美元现代{eq} $,因此在我们的线性规划美元现代{eq} $ x = b作为我们的约束。矩阵美元现代{eq} $应该是一个C \ n ^ 3美元矩阵,C的数量限制。向量b将一个向量的1年代,每个约束的右边。
是什么C在这种情况下吗?我们确定的约束条件是:
- 为每个n ^ 2美元网格框有一个约束,总计n ^ 2美元约束,
- 为每个n行,每一个n数字,我们有一个约束条件,总计n ^ 2美元约束,
- 为每个n列,每一个n数字,我们有一个约束条件,总计n ^ 2美元约束,
- 为每个n宫,我们有n约束告诉我们每个数字都必须出现在次网格,总计n ^ 2美元约束,
- 我们开始$ | | G = \ # $的行G条目已经填写,总计| $ $ | G约束。
总结这些数字,我们得到的C = 4 n ^ 2 + G美元。在我们的方法中,我们将定义美元现代{eq} $与C n ^ 2 = 4美元首先填写前四约束在上面的项目符号列表。一旦完成,我们将添加| $ $ | G更多的行美元现代{eq} $并将给予。让我们首先初始化美元现代{eq} $:
Aeq = 0 (4 * n ^ 2, n ^ 3);
这是一个矩阵的草图我们会填写在本节的其余部分:
顶部我们表示如何订购决策变量:第一个n ^ 2美元列对应数字1是否写在盒子里美元(1,1),(2,1),…,(n, n)美元,下一个n ^ 2美元列对应数字2,等等,就像我们决定使用时指定选项2上面订购。行分割基于约束我们最初的编码以及给定的条目数独谜题。
在接下来的几个部分,我们将遍历这个矩阵和补名每个约束。部分展示矩阵将会是什么样子(即0和1),之前显示的MATLAB代码(与大量的注释)来做到这一点。
箱约束
% % n ^ 2的填写Aeq约束要求每个元素
%的矩阵必须包含一个整数1:n
为i = 1: n%为每一行(数独的网格)
为j = 1: n%为每个列(数独的网格)
为k = 1: n%通过每个数字增量
% (i, j)网格框相关联的行(张)* n + j A_eq
%递增数字k带有n ^ 2沿着数组条目
%的盒子指数(i, j)我们将所有保持不变
%的数字
Aeq((张)* n + j,(张)* n + j + (k - 1) * n ^ 2) = 1;
结束
结束
结束
%如果我们下令设计变量,以便增加
%的数字,我们可以取代这段代码
%
% i = 1: n ^ 2
% Aeq(我(张)* n + 1:我* n) = (1, n)的;
%结束
行约束
% % n ^ 2的填写Aeq约束要求每一行
%只能有1的整数1:n
为k = 1: n%为每个数字
为i = 1: n%解决数独网格的行
为j = 1: n%增加列indec我们总结
%注意,我们已经添加了n ^ 2箱约束
%更新A_eq始于n ^ 2行
Aeq (n ^ 2 +我+ n (k - 1) *(1 +(张)+ (j - 1) * n + (k - 1) * n ^ 2) = 1;
结束
结束
结束
%如果我们下令设计变量,以便增加
%排第一,我们可以取代这段代码
%
% i = 1: n ^ 2
% Aeq (n ^ 2 +我,(张)* n + 1:我* n) = (1, n)的;
%结束
列约束
% % n ^ 2的填写Aeq约束要求每一列
%只能有1的整数1:n
为i = 1: n ^ 2%快速技巧相邻列约束对应行以来的1 s轨道
%我们添加了n ^ 2箱约束和约束n ^ 2行
%,所以这些约束开始行2 * n ^ 2
%因为我们变量索引沿着列第一,
%的时候把这些约束
Aeq (2 * n ^ 2 + i(张)* n + 1:我* n) = (1, n)的;
结束
次网格约束
% %填写Aeq n ^ 2的每个子矩阵约束要求
%只能有1的整数1:n
%注意,n是一个广场,所以sqrt (n)是一个整数
% m和l indec宫- m = 1, l = 1是左上角的次网格
为m = 1:√(n)
为l = 1:√(n)% (m, l)次网格
为j = 1: n
为k = 1:√(n)
%添加n ^ 2盒,n ^ 2行,n ^ 2列约束
%的次网格约束应该添加从第三行开始* n ^ 2
Aeq (3 * n ^ 2 + (m - 1) * sqrt (n) * n + n (l - 1) * + j, (j - 1) * n ^ 2 + (l - 1) * sqrt (n) +…
(m - 1) *√n * n + (k - 1) * n + 1:…
(j - 1) * n ^ 2 + (l - 1) * sqrt (n) + (m - 1) * sqrt (n) * n + (k - 1) * n + sqrt (n)) = 1;
结束
结束
结束
结束
给出的
接下来,我们需要将一些条目的信息已经填写。为此,我们将指定吉文斯矩阵的形式开始所提到的这一节中,然后写这个信息美元现代{eq} $新添加的行以下信息我们已经注册。
对于这个示例,我们将使用相同的矩阵G我们最喜欢的4 x4的例子:
%如果数独的任何值矩阵,添加这些
%的约束
%输入矩阵中的每个给定的值作为三联体(行,坳,整数)
% 4×4数独的示例
吉文斯= [1 4 4;
2 1 2;
2 3 1;
3 1 3;
3 4 2];
用这个矩阵指定,现在让我们添加行美元现代{eq} $并将这些约束指定我们的数字:
%把这些给定的元素变成自己的合适的位置在x向量
%的决策变量。
g =(吉文斯,1)大小;
为i = 1: g为每个吉文斯的%
% 4 * n ^ 2中我们添加了约束,吉文斯的第一个
%应该添加一行4 * n ^ 2 + 1,等等。
%的列条目写在给定的约束
% rowId + colId * n + digitId * n ^ 2
%根据我们如何组织的决策变量
Aeq (4 * n ^ 2 +我,吉文斯(我,1)+(吉文斯(我,2)1)* n +(吉文斯(我,3)1)* n ^ 2) = 1;
结束
这个总结写出来美元现代{eq} $。最后一个矩阵应该类似于这个草图:
注意1矩阵元素对应(2,1,2)美元。
因为所有的约束都是设置相等1,向量b在美元现代{eq} $ x = b应该是一个向量的1史:
说真的= 1 (4 * n ^ 2 + g, 1);
与变量和约束,我们几乎准备有MATLAB生成解决方案。看文档intlinprog,我们需要显式地指定一些其他作品:
- intcon或变量x这应该是整数。我们想要的所有组件x是整数,所以这应该是数组1:numVariables,
- numVariables或变量的长度x(n ^ 3美元在这种情况下),
- 磅,下界为每个变量的向量。因为每一美元间{ijk} $是0或1,磅将一个向量的0年代,
- 乌兰巴托上界的向量的每个变量。因为每一美元间{ijk} $是0或1乌兰巴托的向量1年代。
让我们继续并指定每一个变量:
% % matlab运行的“intlinprog”命令
numVariables =大小(Aeq, 2);
intcon = 1: numVariables;
磅= 0 (1、numVariables);
乌兰巴托= 1 (1、numVariables);
有了一切,让我们生成一个解决方案4 x4的难题。
[x, fval exitflag、输出]= intlinprog (0 (n ^ 3, 1), intcon, [], [], Aeq,说真的,磅,乌兰巴托);
%注意[]的两个参数
%这些输入对应于不等式约束
%因为我们没有使用不等式约束,我们离开这些输入是空的
exitflag;
输出;
x
对于我们的4 x4的例子,x是一个向量,4 ^ 3 = 64美元条目,每一个都是0或1。虽然这是线性规划的解,还不是有利于我们的目的;是什么就好了如果我们能将这个向量转换成一个网格的数字吗1来4,相应的数独的解决方案。我们现在看看结果:
matlab是输出解向量x % %变成数独
S = 0 (n, n);%初始化的网格解决方案金宝搏官方网站
为k = 1: n%为每个数字
%找到相对应的解决方案向量x中的条目数k金宝搏官方网站
有一个值为1(即%。,the digit should be written in that box)
subx =找到(x ((k - 1) * n ^ 2 + 1: k * n ^ 2));
为j = 1: n%循环
行=国防部(subx (j), n);
如果行= = 0
行= n;
结束
(行,j) = k;
结束
结束
%数独矩阵S
年代
对比我们之前手工生成的解决方案,和看到MATLAB成功地找到相同的解决方案!
接下来是尝试用自己的谜题。下面的代码已经复制在一个部分为您的方便,与样品9 x9拼图在开始编码在给定的矩阵。检查MATLAB可以解决,并试着自己!
进一步的指示
感兴趣探索一些其他有趣的问题与这篇文章有关吗?这里有一些进一步的方向开始:
- 如果我们不添加任何吉文斯线性规划,即我们从一个空的数独板吗?我们应该得到一个解决方案——这是独特的吗?我们如何解释这个解决方案吗?(解算器可能需要更长的时间来找到解决方案,但它会找到解决的办法。)
- 你怎么可能强加其他约束转换数独题变成可能更困难?两个选项可能是:(一)要求每个数独的对角线网格包含数字1 - 9的每一次,只有一次,和(b)要求中间框每一次网格形成自己的次网格要求每个数字1 - 9一次,只有一次。
- 选择数独的另一种变体和实现这些约束,比如如果各宫的形状不同。
的代码
% n = 4;% 4×4数独问题
n = 9;% 9的9数独问题
Aeq = 0 (4 * n ^ 2, n ^ 3);
% % n ^ 2的填写Aeq约束要求每个元素
%的矩阵必须包含一个整数1:n
为i = 1: n
为j = 1: n
为k = 1: n
Aeq((张)* n + j,(张)* n + j + (k - 1) * n ^ 2) = 1;
结束
结束
结束
% % n ^ 2的填写Aeq约束要求每一行
%只能有1的整数1:n
为k = 1: n
为i = 1: n
为j = 1: n
Aeq (n ^ 2 +我+ n (k - 1) *(1 +(张)+ (j - 1) * n + (k - 1) * n ^ 2) = 1;
结束
结束
结束
% % n ^ 2的填写Aeq约束要求每一列
%只能有1的整数1:n
为i = 1: n ^ 2
Aeq (2 * n ^ 2 + i(张)* n + 1:我* n) = (1, n)的;
结束
% %填写Aeq n ^ 2的每个子矩阵约束要求
%只能有1的整数1:n
为m = 1:√(n)
为l = 1:√(n)
为j = 1: n
为k = 1:√(n)
Aeq (3 * n ^ 2 + (m - 1) * sqrt (n) * n + n (l - 1) * + j, (j - 1) * n ^ 2 + (l - 1) * sqrt (n) +…
(m - 1) *√n * n + (k - 1) * n + 1:…
(j - 1) * n ^ 2 + (l - 1) * sqrt (n) + (m - 1) * sqrt (n) * n + (k - 1) * n + sqrt (n)) = 1;
结束
结束
结束
结束
%如果数独的任何值矩阵,添加这些
%的约束
%输入矩阵中的每个给定的值作为三联体(行,坳,整数)
% 9-by-9数独的示例
吉文斯= [1 1 4;
1 2 9;
1 6 5;
1 9 1;
2 2 5;
2 7 7;
2 8 2;
2 9 9;
3 3 2;
3 6 8;
3 8 4;
3 9 5;
4 1 2;
4 3 8;
4 5 4;
4 6 3;
5 2 7;
5 4 8;
5 6 6;
5 8 3;
6 4 5;
6 5 9;
6 7 1;
6 9 8;
7 1 7;
7 - 2 8;
7 4 6;
7 7 4;
8 1 3;
8 2 4;
8 3 9;
8 8 6;
9 1 5;
9 4 3;
9 8 1;
9 9 7];
%把这些给定的元素变成自己的合适的位置在x向量
%的决策变量。
g =(吉文斯,1)大小;
为i = 1: g
Aeq (4 * n ^ 2 +我,吉文斯(我,1)+(吉文斯(我,2)1)* n +(吉文斯(我,3)1)* n ^ 2) = 1;
结束
% beq = rhs向量(3 n ^ 2×1)平等的限制
说真的= 1 (4 * n ^ 2 + g, 1);
% % matlab运行的“intlinprog”命令
numVariables =大小(Aeq, 2);
intcon = 1: numVariables;
磅= 0 (1、numVariables);
乌兰巴托= 1 (1、numVariables);
[x, fval exitflag、输出]= intlinprog (0 (n ^ 3, 1), intcon, [], [], Aeq,说真的,磅,乌兰巴托);
exitflag;
输出;
matlab是输出解向量x % %变成数独
S = 0 (n, n);
为k = 1: n
subx =找到(x ((k - 1) * n ^ 2 + 1: k * n ^ 2));
为j = 1: n
行=国防部(subx (j), n);
如果行= = 0
行= n;
结束
(行,j) = k;
结束
结束
%数独矩阵S
年代
评论
留下你的评论,请点击在这里MathWorks账户登录或创建一个新的。