-------------------------------翻译的分割线---------------------------------------
解决所有的数独难题
在这篇文章中我会讲解如何处理解决所有数独难题的问题。答案非常简单(主要思想大概一页代码，两页进行解释)，就是用了两种思想：约束传播（constraint propagation)和搜索。数独规则和初步概念
首先，我们应该了解一些规则。数独是由81宫格(Square)组成的格网(Grid)；主要的单元由1-9列，A-I行组成，9个格子(行，列或box)称为一个单元(Unit)，在同一个单元内的格子称为友邻(peers)。一个数独难题会有一些格子空着，其他填上数字，意思是：
一个数独难题是否解决就是看每个单元是否都被填上了1-9的数字
也就是说，在一个单元中一个数字不能出现两次，而且每个数字必须出现一次。这意味着每个格子必须与其友邻不同。以下就是这些格子的名称，以及一个典型的数独题目和解答。
确切的讲每个格子有3个单元(units)和20个友邻(peers)。例如，以下就是C2所属的单元和友邻。
我们可以使用python语言通过如下的方式实现单元(units),友邻(peers)以及格子(squares)
def cross(A, B): "Cross product of elements in A and elements in B." return [a+b for a in A for b in B] digits = '123456789' rows = 'ABCDEFGHI' cols = digits squares = cross(rows, cols) unitlist= ([cross(rows, c) for c in cols] + [cross(r, cols) for r in rows] + [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')]) units= dict((s, [u for u in unitlist if s in u]) for s in squares) peers= dict((s, set(sum(units[s],[]))-set([s])) for s in squares)
如果你对python细节不熟悉，注意dict或者dictionary 是Python中哈希表的名称，每个关键字(key)对应一个值(value)；被定义成一组(键值，值）的元组
(tuple)；dict((s, [...]) for s in squares)创建字典使得每个格子s其值对应列表[...]；[u for u in unitlist if s in u]表达式的意思是该值为单元u，并且格子s为单元u的成员。所以可以这么理解这个赋值语句“units是一个字典，每个格子对应一组包含这个格子的单元列表”。同样地，下个赋值语句可以这么理解“peers是一个字典，每个格子s对应的是units s 中所包含的格子的集合，但是不包括s本身"。
在以下的测试应该不会出错(It can't hurt to throw in some tests)（它们全部通过）：
def test(): "A set of unit tests." assert len(squares) == 81 assert len(unitlist) == 27 assert all(len(units[s]) == 3 for s in squares) assert all(len(peers[s]) == 20 for s in squares) assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2','H2','I2'], ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'], ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']] assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2', 'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'A1', 'A3', 'B1', 'B3']) print 'All tests pass.'
现在我们有了格子(squares)，单元(units),和友邻(peers)，下一步就是定义数独格网。实际上我们需要两种描述格式：第一种是用来定义数独难题初始状态的文本格式；仍称其为格网(grid)。第二种是表示数独难题任一状态的内部格式，如部分解决或全部解决；我们称其为值集合(values collection)，因为它表示每个格子所有可能的取值。文本格式（格网）由字符串组成，1-9表示一个数字，0或点号表示空白的格子。其他的字符都将忽略（包括空格，换行，破折号，和bars).以下三个网格字符串表示的其实是同一个数独难题。
现在来讲讲values。可能有人会认为9x9的数组是显而易见的数据结构。但是格子的名字是‘A1’，不是（0,0）。因此，values将是一个以格子作为键值的字典。每个键值的值是该格子所有可能的数字：唯一的数字，如果已经在难题的定义中给出或者可以确切的指出该值；多个数字的集合，如果我们仍未能确定该值。该数字集合能用python中的set或list表示，但是我选择使用数字字符串代替（下面会看到为什么这样做）。所以一个网格中A1是7而C7为空可以表示为{'A1':'7', 'C7':'123456789',...}.
下面是解析grid字符串到values字典的代码
def parse_grid(grid): """Convert grid to a dict of possible values, {square: digits}, or return False if a contradiction is detected.""" ## To start, every square can be any digit; then assign values from the grid. values= dict((s, digits) for s in squares) for s, d in grid_values(grid).items(): if d in digits and not assign(values, s, d): return False ## (Fail if we can't assign d to square s.) return values def grid_values(grid): "Convert grid into a dict of {square: char} with '0' or '.' for empties." chars = [c for c in grid if c in digits or c in '0.'] assert len(chars) == 81 return dict(zip(squares, chars))
约束传播（Constraint Propagation）
parse_grid调用了assign(values, s, d)函数。我们能够这样实现他：values[s]=d,但是我们可以做得更多一点。有过解决数独谜题的经验的人都知道有两个重要的策略可以帮助填满所有的格子：1)如果一个格子只有一个值，从该格子的友邻(peers)中去除这个值
2)如果一个单元（unit）只有一个地方能填上某个值，就在那填上那个值举例来说，策略（1）就是如果我们假设A1为7，{‘A1’：7，‘A2’：‘123456789’，...}，我们看到A1只有唯一的值，因此7能够从它的友邻A2中移除（以及其他友邻），产生{‘A1’：'7'，‘A2’：‘12345689’，...}。策略2的意思就是说，如果A3到A9都没有3这个值，那3肯定属于A2，所有我们可以更新上面的例子为{‘A1'：'7'，’A2‘：’3‘,...}。对A2的更新将引起在其友邻更多的更新，以及友邻的友邻的更新，以此类推。这个过程被称为约束传播。
函数assign(values, s, d)将返回更新后的values(包括约束传播的更新)，但是如果有冲突--如果赋值不能往下进行--赋值将返回失败。举例来说，如果我们的格网(grid)以数字'77...'开始，然后我们尝试将7赋给A2，assign函数会意识到A2不可能为7，因为它已在A1的友邻(peer)中被消除。
可以看到本质操作不是分配一个值，而是消除一个格子可能的值，可以通过eliminate(values, s, d)实现。一旦我们有了eliminate函数，就可以将assign(values, s, d)定义为"消除s中除了d的所有值"。
def assign(values, s, d): """Eliminate all the other values (except d) from values[s] and propagate. Return values, except return False if a contradiction is detected.""" other_values= values[s].replace(d, '') if all(eliminate(values, s, d2) for d2in other_values): return values else: return False def eliminate(values, s, d): """Eliminate d from values[s]; propagate when values or places <= 2. Return values, except return False if a contradiction is detected.""" if d not in values[s]: return values## Already eliminated values[s] = values[s].replace(d,'') ## (1) If a square s is reduced to _disibledevent=>
在我们进行下一步之前，我们需要显示这个难题：
def display(values): "Display these values as a 2-D grid." width= 1+max(len(values[s]) for sin squares) line= '+'.join(['-'*(width*3)]*3) for r in rows: print ''.join(values[r+c].center(width)+('|' if cin '36' else '') for c in cols) if rin 'CF': print line print
现在一切就绪。我从Project Euler Sudoku problem 中找到数独列表easy puzzles,并从中挑选了第一个例子试了下：
在这个例子里，通过策略1）和2）的机械应用我们完全解决了这个谜题！不幸的是，不都是这样的情况。下面就是从hard puzzles中取出的第一个例子。
在这个例子里，我们距离解决这个puzzle还有很远的距离---61个格子还是未确定。下一步怎么办？我们可以尝试更复杂的策略.举例来说，我们可以对同一单元(unit)的具有相同2个数字的2个格子采用naked twins策略。给定{'A5':'26','A6':'26',...}，我们可以推导出2和6一定在A5和A6中（尽管我们不知道具体在哪一个），因此我们可以在A行其它格子中消除2和6.我可以通过增加elif len(values[s]) == 2这样几行代码来试着消除2和6.
像这样编码实现这个策略看起来是个可行的方法，但是这将需要成百行代码(有几十种这样的策略)，而且我们永远也不能保证解决每个谜题。
最新评论