仍旧是我五岁小外甥女的九宫格数学题,要求把填在空格里,横列和数列的数字不能有重复.题如下..第一横列:3*1*6*4**第二横列: *47* 第九横列:**4*9*6*8 谢谢大家.
第一横列第二横列:第三横列:第四横列第五横列:第六横列第七横列:第八横列 第九横列
为您推荐：
其他类似问题
九宫格 自己慢慢填 一会儿就出来了
只要不重复就可以了
扫描下载二维码仍然是我五岁小外甥女的九宫格数学题,要求把填在空格里,横列和数列的数字不能有重复.题如下.第一横列:**18*73** 第二横列:*7**2**9* 第三横列:4***1***5第四横列:3**4*5**2 第五横列:*56***13* 第六横列：9**6*1**7 第七横列：2***5***8 第八横列：*8**6**4**第九横列:**91*25**
稍等,我给你贴图.&第八行你多输了个符号.五岁孩子做这种题?太难点了吧?,看图
恩恩，第八行4后面是一个空格。我小外甥女现在上的是类似学前班。每周老师都给一道这样的九宫格，我也不会写。唉~谢谢您啊。要不，您教教我怎么写的吧。
为您推荐：
其他类似问题
第八横列10位数啦！
话说这就是现在流行的数独了,找本数独的书研究,学会方法才重要,现在题库一大堆,
扫描下载二维码高考数学：重点解决综合性问题
(1)()(2)(3)
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。(如何)解决任意的数独谜题 - 开源中国社区
当前访客身份：游客 [
(如何)解决任意的数独谜题
英文原文：
In this essay I tackle the problem of solving every Sudoku puzzle. It turns out to be quite easy (about
of code for the main idea and two pages for embellishments) using two ideas:
Sudoku Notation and Preliminary Notions
First we have to agree on some notation. A Sudoku puzzle is a
grid of 81 the majority of enthusiasts label the columns 1-9, the rows A-I, and call a collection of nine squares (column, row, or box) a
unit and the squares that share a unit the
peers. A puzzle leaves some squares blank and fills others with digits, and the whole idea is:
A puzzle is solved if the squares in each unit are filled with a permutation of the digits 1 to 9.
That is, no digit can appear twice in a unit, and every digit must appear once. This implies that each square must have a different value from any of its peers. Here are the names of the squares, a typical puzzle, and the solution to the puzzle:
A1 A2 A3| A4 A5 A6| A7 A8 A9
4 . . |. . . |8 . 5
4 1 7 |3 6 9 |8 2 5
B1 B2 B3| B4 B5 B6| B7 B8 B9
. 3 . |. . . |. . .
6 3 2 |1 5 8 |9 4 7
C1 C2 C3| C4 C5 C6| C7 C8 C9
. . . |7 . . |. . .
9 5 8 |7 2 4 |3 1 6
---------+---------+---------
------+------+------
------+------+------
D1 D2 D3| D4 D5 D6| D7 D8 D9
. 2 . |. . . |. 6 .
8 2 5 |4 3 7 |1 6 9
E1 E2 E3| E4 E5 E6| E7 E8 E9
. . . |. 8 . |4 . .
7 9 1 |5 8 6 |4 3 2
F1 F2 F3| F4 F5 F6| F7 F8 F9
. . . |. 1 . |. . .
3 4 6 |9 1 2 |7 5 8
---------+---------+---------
------+------+------
------+------+------
G1 G2 G3| G4 G5 G6| G7 G8 G9
. . . |6 . 3 |. 7 .
2 8 9 |6 4 3 |5 7 1
H1 H2 H3| H4 H5 H6| H7 H8 H9
5 . . |2 . . |. . .
5 7 3 |2 9 1 |6 8 4
I1 I2 I3| I4 I5 I6| I7 I8 I9
1 . 4 |. . . |. . .
1 6 4 |8 7 5 |2 9 3
Every square has exactly 3 units and 20 peers. For example, here are the units and peers for the squareC2:
C1 C2 C3| C4 C5 C6| C7 C8 C9
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
We can implement the notions of units, peers, and squares in the programming language
(2.5 or later) as follows:
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]
= 'ABCDEFGHI'
= 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)
本文中我将解决任意的数独谜题的求解问题。利用两个想法:&和，求解将是很容易（大约一页的代码完成主要想法，两页代码完成其他的辅助功能）能够实现的。
数独符号和初步概念
首先，我们要对一些标记符号有共识。数独谜题是一个9*9的表格，大多数数独爱好者把列标记为1-9，把行标记为A-I，并且称每9个小方格（一行，一列，或者3*3的格子）组成的一个局部区域为一个单元(unit)，共享同一个unit的小方格称为节点(peer)。游戏中，有的小方格留空，其他的填上一些数字，问题是：
若每个unit中的数字都是一个1-9的排列，则问题得到解决。
也就是说，每个unit中的数字都只能出现一次，不能出现两次。这等价于每个方格的数字都和它的peer的数字不同。下面是每一个小方格的名字，一个典型的数独问题，以及问题的解。
A1 A2 A3| A4 A5 A6| A7 A8 A9
4 . . |. . . |8 . 5
4 1 7 |3 6 9 |8 2 5
B1 B2 B3| B4 B5 B6| B7 B8 B9
. 3 . |. . . |. . .
6 3 2 |1 5 8 |9 4 7
C1 C2 C3| C4 C5 C6| C7 C8 C9
. . . |7 . . |. . .
9 5 8 |7 2 4 |3 1 6
---------+---------+---------
------+------+------
------+------+------
D1 D2 D3| D4 D5 D6| D7 D8 D9
. 2 . |. . . |. 6 .
8 2 5 |4 3 7 |1 6 9
E1 E2 E3| E4 E5 E6| E7 E8 E9
. . . |. 8 . |4 . .
7 9 1 |5 8 6 |4 3 2
F1 F2 F3| F4 F5 F6| F7 F8 F9
. . . |. 1 . |. . .
3 4 6 |9 1 2 |7 5 8
---------+---------+---------
------+------+------
------+------+------
G1 G2 G3| G4 G5 G6| G7 G8 G9
. . . |6 . 3 |. 7 .
2 8 9 |6 4 3 |5 7 1
H1 H2 H3| H4 H5 H6| H7 H8 H9
5 . . |2 . . |. . .
5 7 3 |2 9 1 |6 8 4
I1 I2 I3| I4 I5 I6| I7 I8 I9
1 . 4 |. . . |. . .
1 6 4 |8 7 5 |2 9 3
每一个小方格都有三个unit，并且拥有20个peer，下面就是C2的节点的units和peers:
C1 C2 C3| C4 C5 C6| C7 C8 C9
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
---------+---------+---------
我们可以用Python实现units，peers，以及小方格的标记，如下所示：
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]
= 'ABCDEFGHI'
= 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)
If you are not familiar with some of the features of Python, note that adictor dictionary is Python's name for a hash table that maps that these are specified as a sequence of (key, value) thatdict((s, [...]) for s in squares)creates a dictionary which maps each squaresto a value that is the list[...]; and that the expression[u for u in unitlist if s in u]means that this value is the list of unitsusuch that the squaresis a member ofu. So read this assignment statement as &unitsis a dictionary where each square maps to the list of units that contain the square&. Similarly, read the next assignment statement as &peersis a dictionary where each squaresmaps to the set of squares formed by the union of the squares in the units ofs, but notsitself&.
It can't hurt to throw in some tests (they all pass):
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.'
如果你不熟悉Python的一些特性的话，记住字典是Python中哈希表的名字，用来映射键-值对；键-值对是用(键, 值)元组表示；dict((s, [...]) for s in squares)创建一个字典，其中每个小方格对应list[...]中的一个值；表达式[u for u in unitlist if s in u]的意思是如果小方块s是u的一个成员，那么结果是units u的列表。所以这条赋值语句可以理解为“units是一个字典，将各个小方块映射到包含小方块的units的一个列表”。下一条赋值语句可以相似的理解为“peers是一个字典，将各个小方块映射到由units中的小方块联合组成的集合，其中不包括小方块自身。”
用几个测试试试看（它们都通过了）：
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.'
Now that we have squares, units, and peers, the next step is to define the Sudoku playing grid. Actually we need two representations: First, a textual format used to specify the initi we will reserve the name
grid for this. Second, an internal representation of any state of a puzzle, partiall this we will call a
values collection because it will give all the remaining possible values for each square. For the textual format (
grid) we'll allow a string of characters with 1-9 indicating a digit, and a 0 or period specifying an empty square. All other characters are ignored (including spaces, newlines, dashes, and bars). So each of the following three grid strings represent the same puzzle:
&4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......&
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
既然我们有了方块(squares)、单位(units)和节点(peers)，下一步就是定义玩数独的网格。实际上我们需要两个表示：第一，用来指定数独谜题初始状态的文本格式；我们将使用grid命名。第二，用来表示数独谜题的任何内部状态，部分解决或者全部解决；我们把它叫做values集合，因为它将给出各个方块内的所有剩余的可能值。对于文本格式（grid），我们允许用1-9中的字符表示数字，0或者句号表示一个空方块。其它字符被忽略（包括空格、换行、破折号和竖线）。所以，下面三个grid字符串表示的是同一个数独谜题：
&4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......&
4 . . |. . . |8 . 5
. 3 . |. . . |. . .
. . . |7 . . |. . .
------+------+------
. 2 . |. . . |. 6 .
. . . |. 8 . |4 . .
. . . |. 1 . |. . .
------+------+------
. . . |6 . 3 |. 7 .
5 . . |2 . . |. . .
1 . 4 |. . . |. . .
values. One might think that a 9 x 9 array would be the obvious data structure. But squares have names like'A1', not(0,0). Therefore,
values will be a dict with squares as keys. The value of each key will be the possible digits for that square: a single digit if it was given as part of the puzzle definition or if we have figured out what it must be, and a collection of several digits if we are still uncertain. This collection of digits could be represented by a Pythonsetorlist, but I chose instead to use a string of digits (we'll see why later). So a grid whereA1is7andC7is empty would be represented as{'A1': '7', 'C7': '', ...}.
Here is the code to parse a grid into a values dict:
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 squ 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))
现在处理值。也许有人觉得9 x 9阵列是很显然的数据结构。但方块的名字是类似‘A1’的形式，不是（0,0）。因此，值将是个以方块为键的字典。每个键的值是其所在方块中的可能数字：可能是数独谜题已给定部分的一个单独的数字，或者是我们算出它一定是某个数字，也可以是我们暂时不确定的一些数的集合。数字集合可以用Python中的set或者list表示，但我选择使用数字字符串（一会我们将看到原因）。这样，A1是7、C7为空的网格可以表示为{'A1':'7'，'C7':'',...}。
下面是把一个网格表示为值的字典的代码：
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 squ 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
The functionparse_gridcallsassign(values, s, d). We could implement this asvalues[s] = d, but we can do more than just that. Those with experience solving Sudoku puzzles know that there are two important strategies that we can use to make progress towards filling in all the squares:
(1) If a square has only one possible value, then eliminate that value from the square's peers.
(2) If a unit has only one possible place for a value, then put the value there.
As an example of strategy (1) if we assign 7 toA1, yielding{'A1': '7', 'A2':'', ...}, we see thatA1has only one value, and thus the 7 can be removed from its peerA2(and all other peers), giving us{'A1': '7', 'A2': '', ...}. As an example of strategy (2), if it turns out that none ofA3throughA9has a 3 as a possible value, then the 3 must belong inA2, and we can update to{'A1': '7', 'A2':'3', ...}. These updates toA2may in turn cause further updates to its peers, and the peers of those peers, and so on. This process is called
constraint propagation.
The functionassign(values, s, d)will return the updated values (including the updates from constraint propagation), but if there is a contradiction--if the assignment cannot be made consistently--thenassignreturnsFalse. For example, if a grid starts with the digits'77...'then when we try to assign the 7 toA2,assignwould notice that 7 is not a possibility forA2, because it was eliminated by the peer,A1.
parse_grid函数中会调用assign(values, s, d)。我们可以仅仅做到values[s] = d，但显然可以做得更多。有经验的读者应当清楚以下两条重要的策略：
(1) 如果一个空格仅有一个可能的值，则与该空格相关的（同行、同列、同一个３*３的区域）空格就不可能取这个值； (2) 如果一个区域（同行、同列、同一个３*３区域）仅有一个空格能够填入值x，则该空格应该填入这个值x。
举例来说：
(1) 若我们在A1中填入7，{'A1': 7, 'A2': '', ...}，此时，7可以从A1的相关格子A2的列表中移除，即{'A1': 7, 'A2': '', ...}。
(2) 若从A3至A9没有一个空格能够填入3，那么3必定填在2中，即 {'A1': 7, 'A2': 3, ...}
当A2被填入３之后，继而会影响与A2相关的格子的约束，与更新约束相关的格子就可能找到正确的答案，以此类推，这种传递的过程称为约束传递。
函数 assign(values, s, d)　将返回被更新后的所有81个格子的值，但如果其中发生冲突，就将返回False. 例如，如果A1中填入了７，而最后传递的结果将在A２中填入７，这种情况显然不符合数独的规则。
It turns out that the fundamental operation is not assigning a value, but rather eliminating one of the possible values for a square, which we implement witheliminate(values, s, d). Once we haveeliminate, thenassign(values, s, d)can be defined as &eliminate all the values fromsexceptd&.
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 d2 in other_values):
return values
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 one value d2, then eliminate d2 from the peers.
if len(values[s]) == 0:
return False ## Contradiction: removed last value
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## (2) If a unit u is reduced to only one place for a value d, then put it there.
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False ## Contradiction: no place for this value
elif len(dplaces) == 1:
# d can only be
assign it there
if not assign(values, dplaces[0], d):
return False
return values Now before we can go much further, we will need to display a puzzle:
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 Now we're ready to go. I picked the first example from a list of
from the fine
and tried it:
&&& grid1 = ''
&&& display(parse_grid(grid1))
4 8 3 |9 2 1 |6 5 7
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2
In this case, the puzzle was completely solved by rote application of strategies (1) and (2)! Unfortunately, that will not always be the case. Here is the first example from a list of
&&& grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
&&& display(parse_grid(grid2))
1256789 | 14589
245689 | 12679
5689 | 12369
------------------------+------------------------+------------------------
------------------------+------------------------+------------------------
因此，最基本的操作并不是填入一个数字，而是迭代地淘汰掉每个格子不可能的数字，具体实际参见 eliminate(values, s, d)。在有了eliminate函数之后，assign函数就更容易地定义为，对于某一格子，去除所有不可能的数字，而留下数字d。
def assign(values, s, d):
&&&去除所有在values[s]中不可能的数字，除了数字d，继而进行约束传递
Return values, 若return False表示发生冲突。&&&
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
return False
def eliminate(values, s, d):
&&&从values[s]中去除d，继而进行约束传递。
Return values, 若return False表示发生冲突。&&&
if d not in values[s]:
return values ## d表不在values[s]中
values[s] = values[s].replace(d,'')
## (1) 如果一个格子中只有一个值d2，则将d2从其相关的格子中去除。（同行、同列、同3*3区域）
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) 如果同行、同列、同３*３区域中发现只有一个格子填入d，则将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 display(values):
&2-D的显示数独的结果&
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
到这里，我想我们可以试一下了！我从&上选择了简单任务中的第一个列子：
&&& grid1 = ''
&&& display(parse_grid(grid1))
4 8 3 |9 2 1 |6 5 7
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2
对于这个样例，完全可以用第(1)与(2)个策略解决！但不幸的是，并不是所有的数独都如此的简单，如困难任务中的第一个样例：
&&& grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
&&& display(parse_grid(grid2))
1256789 | 14589
245689 | 12679
5689 | 12369
------------------------+------------------------+------------------------
------------------------+------------------------+------------------------
In this case, we are still a long way from solving the puzzle--61 squares remain uncertain. What next? We could try to code
. For example, the
naked twins strategy looks for two squares in the same unit that both have the same two possible digits. Given{'A5': '26', 'A6':'26', ...}, we can conclude that 2 and 6 must be inA5andA6(although we don't know which is where), and we can therefore eliminate 2 and 6 from every other square in theArow unit. We could code that strategy in a few lines by adding anelif len(values[s]) == 2test toeliminate.
Coding up strategies like this is a possible route, but would require hundreds of lines of code (there are dozens of these strategies), and we'd never be sure if we could solve every puzzle.
这种情况下，我们仍然没有解决上述数独问题，因为还有61个位置没有填写数字。接下来要怎样做呢？也许我们应该编写一些更复杂的策略，例如naked twins策略，该策略查找同一个单元的两个不同位置(这两个位置要有着相同的待填写数字)，如{'A5': '26', 'A6':'26', ...}，从以上可知，2和6一定会出现在A5和A6这两个位置（虽然我们不能确定具体是哪个位置），因此我们可以从A列单元中的其他位置中删除2和6这两个数字。我们可以通过编写if len(values[s]) == 2的测试语句来消除待定数字。
编写这些策略是可行的，但需要好多的代码量（因为有很多类似的策略），而且我们不敢肯定这就一定能解决所有的数独问题。
The other route is to search for a solution: to systematically try all possibilities until we hit one that works. The code for this is less than a dozen lines, but we run another risk: that it might take forever to run. Consider that in thegrid2above,A2has 4 possibilities (1679) andA3has 5 possibilities (12679); together that's 20, and if we keep , we get 4. & 1038 possibilities for the whole puzzle. How can we cope with that? There are two choices.
First, we could try a brute force approach. Suppose we have a very efficient program that takes only one instruction to evaluate a position, and that we have access to the next-generation computing technology, let's say a 10GHz processor with 1024 cores, and let's say we could afford a million of them, and while we're shopping, let's say we also pick up a time machine and go back 13 billion years to the origin of the universe and start our program running. We can then
that we'd be almost 1% done with this one puzzle by now.
解决数独的另一种方法是搜索，即遍历所有的可能性，直到有一个合适的数字填写方法为止。这种方法不需要编写大量的代码，但是需要花费很长的计算时间，有可能是永远。以上述grid2为例，A2有4种可能性（即数字“1679”）,A3有5种可能性（即数字“12679”）,如此乘下去，整个数独会有4. & 1038种可能性。我们该如何处理呢？以下介绍2种方法。
第一种方法是使用蛮力法。假设我们设计了一种非常高效的程序，该程序使用一条指令就可以计算一个位置，该程序运行在1024核的10GHz CPU，那么从13亿年前就运行该程序，那么到现在为止，仅完成1%的计算量。
The second choice is to somehow process much more than one possibility per machine instruction. That seems impossible, but fortunately it is exactly what constraint propagation does for us. We don't have to try all 4 & 1038 possibilities because as soon as we try one we immediately eliminate many other possibilities. For example, square H7 of this puzzle has two possibilities, 6 and 9. We can try 9 and quickly see that there is a contradiction. That means we've eliminated not just one possibility, but fully half of the 4 & 1038 choices.
In fact, it turns out that to solve this particular puzzle we need to look at only 25 possibilities and we only have to explicitly search through 9 of the 61 constraint propagation does the rest. For the list of 95 , on average we need to consider 64 possibilities per puzzle, and in no case do we have to search more than 16 squares.
第二个选择是用某种方式是一条机器指令处理超过一种可能性.这似乎不可能, 但是幸运的是我们可以严谨的限制他的增长速度. 我们不必尝试全部的 4 & 1038 种可能性因为我们尝试了一个就排除了其他的可能. 例如,&这道谜题中的方格有两个可能性, 6 和 9. 我们可以尝试 9&很快就能看出有矛盾.&这就意味着,我们并不是指排除了一种可能性， 而是 4 & 1038&种选择的整整一半.
事实上,这表明我们要解决特定的谜题我们只需要查看25种可能性 而我们明确的知道直至需要遍历9-61个待填充方格;增长约束做了其他的工作.&在95道 的列表中 我们平均每道谜题需要考虑64种可能性,&并且至少需要遍历16个方格.
What is the search algorithm? Simple: first make sure we haven't already found a solution or a contradiction, and if not, choose one unfilled square and consider all its possible values. One at a time, try assigning the square each value, and searching from the resulting position. In other words, we search for a valuedsuch that we can successfully search for a solution from the result of assigning squarestod. If the search leads to an failed position, go back and consider another value ofd. This is a recursive search, and we call it a
search because we (recursively) consider all possibilities undervalues[s] = dbefore we consider a different value fors.
查找算法是什么? 简单来说: 首先确认我们还没有找到一种正确或错误的解法, 如果找到了,&就选择一个未填充的方格和所有可能的数值.&每次尝试一个组合,在方格中分配每个数值, 从这基础上继续查找.&换句话说, 我们查找一个能够使我们在将d分配给某个方格的时候成功地找到解法的d值.如果查找失败就回退，并尝试另一个d值. 这是一种递归搜索, 我们称之为
因为在我们赋给s另一个值之前我们要 (遍历地) 尝试values[s] = d的全部可能性.