谈谈数独(Sudoku)

曾经终败给现在 2022-08-25 14:43 144阅读 0赞

# 谈谈 Sudoku (数独) #

除特别说明外，本文提到的Sudoku是指9x9的经典Sudoku。本文大量参考了维基百科的相关条目。

# Sudoku 介绍 #

Sudoku 是一种数学游戏，把一个9行9列的棋盘分为9个3x3的方块，在棋盘上填入1~9这九个数字，使得每行(row)每列(column)每块(block)的9个格子内数字不重复。  
  
例如下面是一个填好的Sudoku。  
  
 123|456|789  
 456|789|123  
 789|123|456  
 \---+---+---  
 231|564|897  
 564|897|231  
 897|231|564  
 \---+---+---  
 312|645|978  
 645|978|312  
 978|312|645  
  
用n个符号（通常是1~n的整数）排成n行n列的方阵，如果每一行和每一列都没有重复的符号，就称为一个n阶拉丁方（http: //baike.baidu.com/view/1128476.htm）。Sudoku 是特殊的9阶拉丁方。9阶拉丁方约有5.52E+27种可能，而Sudoku增加了“block内数字不重复”这一约束，其数目要远少于此。  
  
Sudoku 游戏通常会给一些提示（约束），在某些格子上事先填好数字，然后让游戏者填完其余的格子。如果一个提示都没有，任由游戏者发挥，那么一共有大约6.67E+21种不同的答案（http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf）。  
  
虽然没有严格的证明，但似乎至少要有17个提示（事先填好17个数）才能确保答案是唯一的。有人列出了四万多个这种17-hint的Sudoku题目（http://people.csse.uwa.edu.au/gordon/sudokumin.php）。  
另外借助通过计算机搜索，目前还没有找到只要16个提示就能保证答案唯一的Sudoku题目（http://www.math.ie/checker.html）。  
  
一个 Sudoku 问题可以通过以下变换转换为等价的Sudoku问题：

1.  数字排列，例如1换为2，2换为4，4换为1等等。共有9! = 362880种排列方式。
2.  排列同一块中的行，例如第1行与第2行互换，第4行与第6行互换。（但第3行不能与第4行互换。）每块有3!=6种行排列方式，而且块内的行排列是独立的，与其他块无关，因此共有6^3=216种。
3.  排列同一块中的列，例如第1列与第3列互换等等。每块有3!=6种列排列方式，而且块内的列排列是独立的，与其他块无关，因此共有6^3=216种。
4.  整块的行排列，例如第1~3行整体与4~6行互换。一共有3!=6种排列方式。
5.  整块的列排列，例如第1~3列整体与7~9列互换。一共有3!=6种排列方式。
6.  转置（行列互换），有2种可能。

这并不意味着每个Sudoku问题可变出9! x 6^8 x 2个等价问题。因为某些变换不一定能产生新的问题，而某些变换会产生重复的新问题。例如考虑只有对角线上有数字的Sudoku问题，那么转置就不能变出新 问题；再考虑只有第一行有数字的sudoku问题，用第3、5变换产生的新问题都能由第1变换得到。

# Sudoku 程序求解    #

## 回溯算法 ##

Sudoku 问题很像八皇后问题，都可以用回溯算法解决。一个Sudoku问题可以表示为一个棋盘，已经填了一些数，余下n个空格待填。思路是：如果n==0，说明填 满了，程序结束。否则找到一个空格，试着填一个数（依次从1~9中选），然后看能不能求解这个子问题（原问题是填n个空格，子问题是填n-1个空格），如 果子问题不能求解（求解子问题这一步通常用递归），就试着填下一个数 （例如第一次试着填1，第二次试试2），如果试到9都不能满足，说明当前问题无解。这个算法是相当直接的，对付大多数问题也能迅速解决。有一处明显的改 进：在找待填空格时选择可用数字最少的空格，也就是说选择可能数目最少的分支，这样能大大减少试探的次数。以下是程序所用的数据结构，全部为数组，基本用 C语言实现：  
  
// 基本数据：  
const int N = 81; // 棋盘上有9x9=81个格子  
const int NEIGHBOR = 20; // 每个格子有20个相邻的格子（同一行，同一列，同一块）  
int board\[N\]; // 棋盘，值表示所填的数字  
int neighbors\[N\]\[NEIGHBOR\]; // 邻居数组，值表示在棋盘中的下标，例如 neighbors\[2\]\[3\] 表示第2个格子的第3个邻居的下标。  
int spaces\[N\]; // 待填的空格，至多N个，值表示在棋盘中的下标  
int nspaces; // 棋盘上最初的空格总数  
  
// 以上数据已经足够写出回溯程序（甚至不用neighbors数组也行），不过为了加快运行速度，我使用了以下补充数据，用作cache  
int arities\[N\]; // 格子的“自由度”，arities\[x\]表示x这个格子目前的候选数字的个数，选待填格子时应选arity最小的格子。  
bool available\[N\]\[10\]; // 格子有哪些数字可用，例如available\[3\]\[2\]==true说明第3号格子能填入数字2。  
  
在回溯过程中，会频繁更新board、arities、available等数组。而neighbors数组的内容在程序运行中不会变化。在判断能否填数 时，不用检查board中的多个相邻元素，只需访问一次available就行，这是以空间换时间的做法。用这种方法写的程序求解一个Sudoku问题的 用时大约在毫秒级别。

## 精确覆盖算法（Exact Cover） ##

另一种求解Sudoku的办法是把它转换为 [Exact Cover][] 问题。Exact Cover问题是指对于一个稀疏的0/1矩阵，选出一些行，使得由这些行构成的新矩阵中每一列有且仅有一个1。（注：Exact Cover是NPC问题，一般化的Sudoku（棋盘大小不限于9x9，而是n^2 x n^2，分为n x n块）也是NPC问题。）  
  
Knuth 描述了用于解决 Exact Cover 问题的 [Algorithm X][] （一个递归的、非确定的、深度优先蛮力搜索算法），并给出了一个巧妙利用指针和双向链表的高效实现技术，称为 [Dancing Links][]。 (ps: http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz , pdf: http://lanl.arxiv.org/PS\_cache/cs/pdf/0011/0011047v1.pdf)  
  
Knuth 自己还写了 Dancing Links 程序(http://www-cs-faculty.stanford.edu/~knuth/programs/dance.w)和 Sudoku 求解程序(http://www-cs-faculty.stanford.edu/~knuth/programs/sudoku.w)。这个程序不仅能求解Sudoku，还能枚举出所有满足条件的解法。  
  
Apache的Hadoop项目是开源的Java语言MapReduce实现，它附带的示例中有使用Dancing Links技术的Sudoku求解程序(http: //svn.apache.org/viewvc/hadoop/core/trunk/src/examples/org/apache/hadoop/examples/dancing/)。 由于Sudoku问题的规模比较小，求解一个问题的用时通常少于一秒钟，所以这个程序其实没有用到分布式计算。  
  
  
Sudoku 是个很有意思的问题，不难解决，而且有很多好玩的地方。

[Exact Cover]: http://en.wikipedia.org/wiki/Exact_cover
[Algorithm X]: http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
[Dancing Links]: http://www-cs-faculty.stanford.edu/%7Eknuth/papers/dancing-color.ps.gz