用MATLAB求解数独
作者:Cleve Moler, MathWorks
人类解谜者和计算机程序使用非常不同的数独解决技术。手工解决数独的魅力源于对无数微妙组合和模式的发现和掌握，这些组合和模式为最终解决方案提供了线索。要让计算机编程来复制人类的模式识别能力并不容易。出于这个原因，大多数数独解决程序采用了一种非常不同的方法，依靠计算机几乎无限的能力来进行暴力尝试和错误。这就是我在MATLAB中使用的方法®程序。
数独挑战
您可能知道，解决数独需要填充一个9乘9的网格，以便每行，列和主要的3乘3块包含所有数字1到9。初始网格由几个数字填充，称为线索。与魔方和其他数字谜题相比，它不涉及算术;数独网格中的元素也可以是字母表中的字母或任何其他符号。
图1显示了一个初始网格。我特别喜欢这个例子中的对称，这是由西澳大利亚大学的Gordon Royle设计的。图2显示了解决方案。
用递归回溯法求解数独
我们的MATLAB程序只使用一种模式——单例模式——以及基本的计算机科学技术——递归回溯。
为了了解程序是如何工作的，我们可以使用一个更简单的4乘4的网格，其中包含2乘2的块。这样的谜题被称为数独而不是数独，因为“史”是日语中“四”的意思。
图3显示了我们的第一个Shidoku谜题。图4到图6显示了它的解决方案。在图4中，可能的条目或候选人，用小数字表示。例如，第二行包含一个“3”，第一列包含一个“1”，因此位置(2,1)上的候选元素是“2”和“4”。其中四个单元格只包含一个候选单元。这些细胞是单例。第一个示例可以通过填充单例轻松解决。在图5中，我们插入了一个单例并重新计算了候选对象。在图6中，我们插入了剩余的单例，以完成解决方案。
一个简单的谜题可以定义为只需插入单例即可解决的谜题。在这个定义中，我们的第一个示例很简单，但下一个示例则不然。
图7所示的谜题输入数组是由MATLAB语句生成的
X = diag(1:4)
因为这个谜题中没有单例(图8)，所以我们将使用递归回溯。我们选择一个空单元格，并试探性地插入它的一个候选单元格。我们选择按MATLAB一维下标X(:)所隐含的顺序考虑单元格，并按数字顺序尝试候选单元格。因此，我们在单元格(2,1)中插入一个“3”，创建一个新的谜题(图9)。然后，我们递归地调用程序。
新的谜题很简单;结果如图10所示。然而，这个解决方案依赖于我们在递归调用之前所做的选择。其他选择可能产生不同的解决方案。金宝搏官方网站对于这个简单的对角初始条件，有两种可能的解，它们恰好是矩阵彼此的转置。金宝搏官方网站由于解决方案不是唯一的，所以图7中的网格不是有效的谜题。
存在与唯一性
作为数学家，我们试图证明一个问题的解是存在的，而且是唯一的。在数独游戏中，从最初的线索中无法轻易确定存在性或唯一性。例如，对于图1所示的谜题，如果我们要在(1,1)单元格中插入“1”、“5”或“7”，则行、列和块条件将得到满足，但最终的谜题没有解决方案。如果这样的谜题出现在你的报纸上，你会很沮丧的。
回溯会产生许多不可能的配置。我们的程序在遇到没有候选者的单元格时终止递归。这样的谜题没有答案。
唯一性是一种难以捉摸的属性。大多数数独游戏的描述都没有规定必须只有一个解。再一次，发现一个不同于给定的解决方案会令人沮丧。MATLAB Central上的一些解谜生成程序不检查唯一性。我所知道的唯一检查唯一性的方法是详尽地列举所有可能的解。金宝搏官方网站
数独解决算法
我们的MATLAB程序只涉及四个步骤:
1.填写所有单例。
2.如果单元格没有候选单元，则退出。
3.填写空单元格的暂定值。
4.递归地调用程序。
关键的内部功能是候选人。每个空单元格从Z = 1:9并使用关联的行、列和块中的数字值来为中的零元素z。剩下的非零就是候选项。例如，考虑图1中的(1,1)单元格。我们从
Z = 1 2 3 4 5 6 7 8 9
第一行的值改变为
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} = [1 5 7 9]
难题
图1所示的谜题实际上很难解决，无论是用手还是用计算机。图11和图12是计算的快照。最初，没有单例，所以第一个递归步骤立即发生。我们尝试在(1,1)单元格中输入“1”。图11显示了第22步如何填充第一列。但我们离解决方案还有很长的路要走。在3,114步之后，递归在(1,1)单元格中放入一个“5”，在8,172步之后，它尝试一个“7”。
图12显示了14,781个步骤后的情况。我们似乎快要找到答案了因为81个单元格中有73个已经赋值了。但是第一行和最后一列加在一起包含从1到9的所有数字，因此右上角的(1,9)单元格没有任何值。此单元格的候选列表为空，递归终止。最后，在19,229步之后，我们尝试在第一个单元格中输入“9”。这个“9”是个好主意，因为在不到200步之后，也就是19,422步之后，程序得到了图2所示的解决方案。这比大多数谜题需要的步骤要多得多。
用递归回溯法求解数独
使用递归回溯解决数独。% sudoku(X)，期望一个9 × 9的数组X。%填写所有“单例”。% C是每个单元格的候选向量的单元格数组。% 5是第一个单元格(如果有的话)，只有一个候选单元格。% e是第一个没有候选者的单元格(如果有的话)。[C,s,e] =候选人(X);while ~isempty(s) && isempty(e) X(s) = C{s};[C,s,e] =候选人(X);完成不可能的谜题返回。if ~isempty(e)返回end %递归回溯。 if any(X(:) == 0) Y = X; z = find(X(:) == 0,1); % The first unfilled cell. for r = [C{z}] % Iterate over candidates. X = Y; X(z) = r; % Insert a tentative value. X = sudoku(X); % Recursive call. if all(X(:) > 0) % Found a solution. return end end end % ------------------------------ function [C,s,e] = candidates(X) C = cell(9,9); tri = @(k) 3*ceil(k/3-1) + (1:3); for j = 1:9 for i = 1:9 if X(i,j)==0 z = 1:9; z(nonzeros(X(i,:))) = 0; z(nonzeros(X(:,j))) = 0; z(nonzeros(X(tri(i),tri(j)))) = 0; C{i,j} = nonzeros(z)’; end end end L = cellfun(@length,C); % Number of candidates. s = find(X==0 & L==1,1); e = find(X==0 & L==0,1); end % candidates end % sudoku
数独的起源
大多数人认为数独起源于日本。事实上，它是美国人的发明。它第一次出现是在1979年的戴尔拼图杂志上，当时的名字是Number Place。1984年，日本出版商Nikoli将这一谜题带到了日本，并将其命名为“数独”(Sudoku)，这是一个汉字首字母缩略词，意思是“数字应该是单身，未婚”。伦敦《泰晤士报》于2004年开始刊登这个谜题，不久它就传播到了美国和世界各地。
出版2009 - 91789v00
