用MATLAB解决数独

人类猜谜和计算机程序使用不同的这种“解决数独谜题技巧。对解决数独用手来自无数的微妙组合的发现和掌握和模式提供线索最终的解决方案。是不容易的程序计算机复制这些人类模式识别能力。出于这个原因,大多数这种“解决数独谜题程序采取一个非常不同的方法,依靠计算机的执行能力几乎是无限的蛮力试验和错误。这就是我的方法用于MATLAB^®程序。

数独的挑战

正如你可能知道的,解决数独涉及填写9-by-9网格,每一行,列,3×3的块和主要包含所有的数字1到9。初始填充网格是几位数,被称为线索。与魔术方块和其他数字谜题,不涉及算术;数独游戏中的元素网格一样可以字母表的字母或其他符号。

图1显示了初始网格。我特别喜欢对称在这个例子中,这是由于戈登•罗伊尔西澳大利亚大学的。图2显示了解决方案。

用递归回溯法解决数独

我们的MATLAB程序只使用一个pattern-singletons-together基本计算机科学技术,递归回溯。

看到这个程序是如何工作的,我们可以使用一个简单的用2×2块4×4的网格。这样的游戏被称为Shidoku代替数独,因为“史”是日本的“四”。

图3显示了我们的第一个Shidoku难题。图4到6显示其解决方案。在图4中,可能的条目,或候选人,表示为小数字。例如,第二行包含一个“3”和列一个包含一个“1”,所以候选人的位置(2,1)是“2”和“4。“四细胞只包含一个候选人。这些细胞是单例。第一个例子可以解决单件容易被填充。在图5中,插入一个单例对象,重新计算的候选人。在图6中,我们插入了剩下的单次出现的完整的解决方案。

一个简单的拼图可以被定义为一个可以解决的只是插入单例。在这个定义中,我们的第一个例子是很容易的,但下一个示例不是。

谜图7所示的输入数组是由MATLAB语句

X =诊断接头(1:4)

因为没有单件在这个难题(图8),我们将使用递归回溯。我们选择一个空的细胞和初步插入其候选人之一。我们选择的顺序考虑细胞暗示了MATLAB维加下标,X(:),并尝试流水号的候选人。所以我们插入一个“3”在细胞(2,1),创建一个新的难题(图9),然后递归地调用程序。

新的谜题很容易;结果如图10所示。然而,这种解决方案取决于我们做出的选择,在递归调用之前。其他的选择可能会产生不同的解决方案。金宝搏官方网站对于这个简单的对角初始条件,有两种可能的解决方案,这恰好是矩阵转置。金宝搏官方网站网格自解不是唯一的,在图7中不是一个有效的难题。

存在性和唯一性

作为数学家,我们试图证明,解决一个问题存在,而且它是独一无二的。数独,既不存在也不唯一性可以很容易地确定从最初的线索。例如,图1所示的难题,如果我们要插入一个“1”,“5”或“7”(1,1)细胞,行,列,并阻止条件满意但是生成的难题没有解决方案。这将是非常令人沮丧如果这样一个难题出现在你的报纸。

回溯产生许多不可能的配置。我们的程序终止递归的时候遇到一个细胞没有候选人。这样的难题没有解决方案。

独特性是一个难以捉摸的财产。大多数数独的描述并不指定必须只有一个解决方案。再一次,这将是令人沮丧的发现不同的解决方案。一些puzzle-generating节目MATLAB中央不检查的独特性。唯一的方法,我知道检查独特性是详尽列举所有可能的解决方案。金宝搏官方网站

这种“解决数独谜题的算法

我们的MATLAB程序包括四个步骤:
1。填写所有的单例。
2。如果一个细胞没有候选人退出。
3所示。填写初步值为空细胞。
4所示。递归地调用程序。

内部函数的关键候选人。每个空单元开始z = 1:9并使用数值在相关的行,列和块零元素z。依然存在的非零的候选人。例如,考虑图1中(1,1)的细胞。我们开始

z = 1 2 3 4 5 6 7 8 9

第一行中的值改变z

z = 1 0 0 0 5 6 7 8 9

然后第一列z变化

z = 1 0 0 0 5 0 7 0 9

(1,1)块不做任何进一步的变化,所以这个细胞的候选人

C {1} = [1 5 7 9]

一个困难的谜题

图1所示的难题其实是很难解决,通过手或电脑。图11和12是计算的快照。最初,没有单件,所以会立即递归的第一步。我们试着一个“1”(1,1)细胞。图11显示了如何将第一列是由22步。但是我们还有很长的路从解决方案。3114步后,递归将“5”(1,1)细胞,8172步之后,尝试一个“7”。

图12显示了14781步后的情况。我们似乎接近解决因为73 81个细胞的分配值。但第一行和最后一列,综上所述,包含所有从1到9的数字,所以没有价值了(9)细胞在右上角。这个单元格是空的,候选人名单和递归终止。最后,19229步之后,我们尝试一个“9”在第一个单元格。这个“9”是一个好主意,因为不到200步之后,19422年之后的步骤,程序达到解决方案如图2所示。这是比多数谜题需要更多的步骤。