言

数独（及其前身）已经出现了一百多年。当它第一次出现时，人们实际上只能咬着笔抓着头发来解决数独题目。但现在我们有了强大的电脑！（现在的人就能在手机和电脑上做数独题啦！）

在这篇文章中，你会学到如何摇身一变，成为一名数独大师，在几秒钟时间内就能解出一般人要花几小时才能解出的难题。当然，更重要的是，你会一步步的学习如何使用机器学习（Machine Learning）轻松解决每个数独。设想一下，如果有计算机来做数独，谁还需要思考呢，当然，多做数独还是真的可以健脑的。（我没有开挂做数独啊，不要抓我）

Peter Norvig最先使用Python开发了一个优雅的程序，通过约束网格传播和搜索以此来解出数独。Norvig的解决方案被认为是目前十分经典的一个解决数独的方案，当人们通过编程来解数独时经常被引用。在回顾数独和一些策略之后，本文将逐步分解Norvig的代码，以便你能真正了解它的工作方式。

什么是数独？

数独是源自于18世纪瑞士的一种数学游戏。是一种传统的运用纸、笔进行演算的逻辑游戏。人们需要根据9×9的盘面上的已知数字，一一推理出所有剩余空格的数字，并满足每一行、每一列、每一个九宫格（3*3）内的数字均含1-9，不重复

如图，突出显示在蓝色正方形中的数字不能在与同列同行和宫相对应的任何黄色正方形中重复

如何解数独？

其实一般做数独题的时候，只需要不断做两件事就OK了。要做的第一件事是就是排除行，列和宫中的已知数字。您要做的第二件事就是寻找一个可能填写的候选数。

在下面给出的示例中，每个正方形中的可能填写的数字以较小的字体标注。通过排除出现在同一列，行或宫中的已经重复的数字来确定剩下可能的数字。大多数人仅仅只会一次确定一个宫的可能数量，而不是直接确定整个网格中所有能填写的数字（暗数、候选数）。

进行排除操作后，你可以寻找仅剩余一种情况的格子。在下面的示例中，两个黄色突出显示的正方形必须包含1和8，因为其他所有的可能性已被排除，它们填在别的格子中会出现重复。

现在已知以黄色突出显示的两个格子，这又排除了其他格子的更多可能性。现在我们可以知道以蓝色突出显示的格子必须填7。

如果你继续不断的按照此法进行排除和确定，最终可能会达到能够完全确定某个3*3的格子或行或列的情况。

在下面的示例中，我们可以确定以蓝色突出显示的格子的解必须为6，因为数字6不可能出现在黄色宫中的其他任何的格子中。

有时，我们在求解的时候可能会遇到这种情况，似乎每个未解决的3*3的格子中有多个可能的值。这意味着我们可以选择多种路径，但至于哪条路才能最终得到结果就不知道了。

在这个选择上，我们必须尝试每个选项。选择一条路并继续求解，直到按这条路走下去最后只能得到“此路不通”的答案。然后，将不得不回溯到分歧点并尝试其它的路。

但是我们可以使用二叉搜索树在计算机上轻松完成此类检索。当有两个不同的数字都可以作为一个3*3的格子的答案时，我们可以尝试引入两种不同的可能性。二叉搜索树将使算法沿选择的一个分支下降，然后尝试不同的选择。

现在，我们将了解用上述方法相似的思路来编写的Python代码，以此用来处理数独问题。

Peter Norvig的解数独代码

Peter Norvig在他的解决数独难题的文章中解释了做数独题的方法与他所使用的代码。

www.norvig.com/sudoku.html

有些人可能理解他的解释有些困难，尤其是初学者。本文将分解这些内容，以便让你更轻松地了解Peter Norvig的代码是如何工作的。

在本文中，Peter Norvig的代码已经更新为Python3，以方便的在目前的环境下运行

首先，我们将介绍基本的设置和表示法。Norvig描述了他在代码中所使用的基本符号：

数独拼图是一个由81个方格组成网格；广大爱好者把列1-9、行a-i记为行列标记，把9个方格（列、行或宫）的集合称为一个单位，把共享一个单位的方格称为对等方

这是数独中每个格子的名称：

Norvig将数字，行和列定义为字符串：

digits='123456789'
rows='ABCDEFGHI'
cols=digits

你可能会注意到将cols其设置为与digits相等。尽管它们具有相同的值，但它们表示不同的事物。该digits变量表示走在数独上解决这一难题的数字。而cols变量代表网格的列名。

整个数独盘也被定义为字符串，但是这些字符串是通过以下函数创建的：

def cross(A, B):
 "a中元素与b中元素的叉积。"
 return [a+b for a in A for b in B]
squares=cross(rows, cols)

cross函数（[a+b for a in A for b in B]）的返回部分只是编写这个代码的一种优秀解决方案：

squares=[]
for a in rows:
 for b in cols:
 squares.append(a+b)

运行此函数后，变量等于所有小方格名称的列表。

['A1', 'A2', 'A3', 'A4', 'A5', 'A6', 'A7', 'A8', 'A9', 'B1', 'B2', 'B3', 'B4', 'B5', 'B6', 'B7', 'B8', 'B9', 'C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'D1', 'D2', 'D3', 'D4', 'D5', 'D6', 'D7', 'D8', 'D9', 'E1', 'E2', 'E3', 'E4', 'E5', 'E6', 'E7', 'E8', 'E9', 'F1', 'F2', 'F3', 'F4', 'F5', 'F6', 'F7', 'F8', 'F9', 'G1', 'G2', 'G3', 'G4', 'G5', 'G6', 'G7', 'G8', 'G9', 'H1', 'H2', 'H3', 'H4', 'H5', 'H6', 'H7', 'H8', 'H9', 'I1', 'I2', 'I3', 'I4', 'I5', 'I6', 'I7', 'I8', 'I9']

而网格中的每个小格子都有3个单位和20个对等方。小格子的单位是显示在其中的行，列和九宫格。小格子的对等方是单位中的所有其他小格子。例如，以下是小格子C2中的单位和对等方：

使用cross函数创建每个小格子的所有单位：

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')])

在Python中，字典是键值对的集合。使用以下代码行创建字典，字典使用小格子的名称作为键，并使用三个单位或20个对等体作为值。

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)

现在，可以使用来访问“ C2”的所有3个单位，units['C2']并将得到以下结果：

接下来，我们需要完整的数独网格的两种表示形式。名为grid的文本将是数独的初始状态。

还需要网格的另一种表示形式来描述数独解题的当前状态。它将跟踪每个格子的所有剩余可能值并命名为values。

与units和peers类似，values将是一个以小格子为键的字典。每个键的值将是一串数字，该串数字是该小格子内的所有可能数字。如果数字是在拼图中给出的或已被找出，则vaules中将只有一位数字。例如，如果存在一个网格，其中A1为6而A2为空，则values的值可能是这样{'A1': '6', 'A2': '123456789', ...}。

解析网格和网格值函数

该parse_grid函数（下面的代码）可将网格转换为可能值的字典。grid是给定的数独题目。grid_values函数用来提取数字，0和“.”的重要值。在values字典中，正方形是键，而网格中的给定数字是值。

对于具有给定值的每个格，assign函数用于将值分配给方框并从对等方排除该值。assign函数将在下文介绍。如果发生任何错误，该函数将返回False。

这是parse_grid与grid_values函数的代码。

def parse_grid(grid):
 """将网格转换为可能值的dict，{square:digits}，如果检测到错误，则返回false"""
 ## 首先，每个小格子可以是任意数字；然后从网格中赋值。
 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 ## (如果我们不能把d赋给格子s，则失败。)
 return values
def grid_values(grid):
 "将网格转换为{square:char}的dict，并用'0'或'.'表示清空。"
 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）

每个方格的初始值将是特定数字（1-9）或为空值。我们可以将约束应用于每个小格子并排除不可能的值。

Norvig使用以下两种策略来帮助确定平方的正确值（与上述策略相对应）：

（1）如果一个方格只有一个可能的值，则从该正方形的对等方中排除该值。

（2）如果一个单位只有一个可能的位置放一个值，则将值放在那里。

第一种策略的示例是：如果我们知道A1的值为5，则可以从其所有20个对等方中删除5个。

第二种策略的示例是：如果可以确定A1到A8都不包含9作为可能的值，那么我们可以确定A9的值为9，因为9必须出现在单位中的某个位置。

每次更新网格时，都会导致其所有对等方的可能更新。此过程将连续不断的进行，称为约束传播。

分配功能

该assign(values, s, d)函数在parse_grid函数内部被调用。它返回更新的值。它接受三个参数：values，s和d。

请记住，values是一个字典，它将每个格子与该格子的所有可能的数字值相关联。s是我们要为其分配值的格子，d是需要分配给该格子的值。D才是我们首先要解决的给定的难题。

它调用函数eliminate(values, s, d)以排除S中除D之外的所有值。

如果存在矛盾，例如两个正方形被分配了相同的数字，则排除函数将返回False。

def assign(values, s, d):
 """从值[s]中排除所有其他值（d除外）并传播。如果存在矛盾，则本函数将返回False。"""
 other_values=values[s].replace(d, '')
 if all(eliminate(values, s, d2) for d2 in other_values):
 return values
 else:
 return False

消除功能

我们看到assign函数调用了eliminate函数。消除函数的调用如下：eliminate(values, s, d2) for d2 in other_values)

eliminate函数将排除使用上述两种策略无法解决的值。第一种策略是，当仅存在一个潜在值s时，该值将从s的对等方中删除。第二种策略是，当值只能存在一个位置时，该值d将从所有对等方中删除。

这是它的全部功能：

def eliminate(values, s, d):
 """从值[s]中删除d；当值或位置<=2时传播。如果存在矛盾，则本函数将返回False。"""
 if d not in values[s]:
 return values ## 已被排除
 values[s]=values[s].replace(d,'')
 ## （1）如果方格s减去一个值d2，则从对等点中消除d2。
 if len(values[s])==0:
 return False ## 矛盾：去掉最后一个值
 elif len(values[s])==1:
 d2=values[s]
 if not all(eliminate(values, s2, d2) for s2 in peers[s]):
 return False
 ##（2）如果一个单位u的值d减少到只剩一个地方，那么就不动它。
 for u in units[s]:
 dplaces=[s for s in u if d in values[s]]
 if len(dplaces)==0:
 return False ## 矛盾：没有这个值的地方
 elif len(dplaces)==1:
 #d只能在一个单元中的其中一个位置；将它分配到那里
 if not assign(values, dplaces[0], d):
 return False
 return values

显示功能

本display函数将在调用后显示结果parse_grid。

def display(values):
 "将这些值显示为二维网格。"
 width=1+max(len(values[s]) for s in squares)
 line='+'.join(['-'*(width*3)]*3)
 for r in rows:
 print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
 if r in 'CF': 
 print(line)
 print()

这是一个示例，它在解析一个网格之后调用显示函数后，显示的网格依然是个候选数的集合

您会注意到，许多格具有多个候选数，而有些则完全解决了。上面的网格是上面两种策略死记硬背应用的结果。但是正如你所看到的，仅凭这些策略还不足以完全解决数独。

搜索（Search）

解决数独问题的??方法有很多，但有些方法效率更高。Norvig建议使用一种特定类型的搜索算法。

搜索算法可以做这些事情。首先，它可以确保还没有找到解决方案。然后，它选择一个未填充的正方形，并考虑所有可能的值。最后，它一次一次尝试为格子分配每个值，然后从结果位置再次进行搜索。

可变顺序用于选择要开始搜索的格子。这是Norvig的描述方式：

我们将使用一种称为最小剩余值的通用启发式方法，这意味着我们将选择具有最小可能值数量的格子（或其中之一）。为什么？考虑上面的grid。假设我们首先选择了B3。它有7种可能性（1256789），因此我们期望以6/7的概率猜测错误。如果取而代之，我们选择G2，它只有2种可能性（89），那么我们期望错的概率只有1/2。因此，我们选择可能性最小，直接得到正确答案的期望也就越大。

这些数值按自然数顺序排列。

这是本search函数以及solve解析初始网格并调用的函数search。

def solve(grid): return search(parse_grid(grid))
def search(values):
 "使用深度优先搜索和传播，尝试所有可能的值。"
 if values is False:
 return False ## 失败了
 if all(len(values[s])==1 for s in squares): 
 return values ## 解出来辣!
 ## 选择可能性最小的未填充正方形
 n,s=min((len(values[s]), s) for s in squares if len(values[s]) > 1)
 return some(search(assign(values.copy(), s, d)) 
 for d in values[s])

根据数独的规则，当每个格子只有一个值时， 问 题 就解决了。该search函数将递归调用，直到解决难题为止。它通过values复制以避免复杂。

some是用于检查尝试是否成功解决难题的函数。

def some(seq):
 "返回seq的某个元素，该元素为true。"
 for e in seq:
 if e: return e
 return False

完整代码（在Python3.x下测试通过）

这些代码组合起来将会让你变成数独大师，以下给出完整代码。

def cross(A, B):
 "a中元素与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)
def parse_grid(grid):
 """将网格转换为可能值的dict，{square:digits}，如果检测到错误，则返回false"""
 ## 首先，每个小格子可以是任意数字；然后从网格中赋值。
 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 ## (如果我们不能把d赋给格子s，则失败。)
 return values
def grid_values(grid):
 "将网格转换为{square:char}的dict，并用'0'或'.'表示清空。"
 chars=[c for c in grid if c in digits or c in '0.']
 assert len(chars)==81
 return dict(zip(squares, chars))
def assign(values, s, d):
 """从值[s]中排除所有其他值（d除外）并传播。如果存在矛盾，则本函数将返回False。"""
 other_values=values[s].replace(d, '')
 if all(eliminate(values, s, d2) for d2 in other_values):
 return values
 else:
 return False
def eliminate(values, s, d):
 """从值[s]中删除d；当值或位置<=2时传播。如果存在矛盾，则本函数将返回False。"""
 if d not in values[s]:
 return values ## ## 已被排除
 values[s]=values[s].replace(d,'')
## （1）如果方格s减去一个值d2，则从对等点中消除d2。
 if len(values[s])==0:
 return False ## 矛盾：去掉最后一个值
 elif len(values[s])==1:
 d2=values[s]
 if not all(eliminate(values, s2, d2) for s2 in peers[s]):
 return False
 ##（2）如果一个单位u的值d减少到只剩一个地方，那么就不动它。
 for u in units[s]:
 dplaces=[s for s in u if d in values[s]]
 if len(dplaces)==0:
 return False ## 矛盾：没有这个值的地方
 elif len(dplaces)==1:
 #d只能在一个单元中的其中一个位置；将它分配到那里
 if not assign(values, dplaces[0], d):
 return False
 return values
def solve(grid): return search(parse_grid(grid))
def search(values):
 "使用深度优先搜索和传播，尝试所有可能的值。"
 if values is False:
 return False ## 已False
 if all(len(values[s])==1 for s in squares):
 return values ## 解出来拉!
 ## 以最少的可能性选择未填充的正方形
 n,s=min((len(values[s]), s) for s in squares if len(values[s]) > 1)
 return some(search(assign(values.copy(), s, d))
 for d in values[s])
def display(values):
 "Display these values as a 2-D grid."
 width=1+max(len(values[s]) for s in squares)
 line='+'.join(['-'*(width*3)]*3)
 for r in rows:
 print(''.join(values[r+c].center(width)+('|' if c in '36' else '') for c in cols))
 if r in 'CF':
 print(line)
 print()
def some(seq):
 "返回seq的某个元素，该元素为true。"
 for e in seq:
 if e: return e
 return False

调试

测试用Grid数独题,同时它也是一个最小数独（供读者自己测试python时调试用）：

grid='4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'

苦逼作者码字不易，各位看官老爷们给个关注吧！