这篇文章简单介绍下“数独求解器”怎么用程序实现？？
文章背景图片是一个比较难的数独问题，感兴趣的可以试着手动求解啊。
这里暂时不多解释，直接贴代码，等有时间了详细解释下具体怎么实现的。代码使用python写的，总共大概一页纸。
import collections
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]
def parse_Grid(values):
'''Convert grid to a dicf of values {square:digits},
and a dict of possible values {square:digits},
or return False if a contradiction is detected. That is, no possible value
'''
# Input is a string of with length of 81
digits = '123456789'
if not values:
return False,False
if isinstance(values, str):
chars = [c for c in values if c in digits or c in '0.']
values = dict(zip(squares, chars))
elif isinstance(values, dict):
values = values
values_Possible = dict((s,'') for s in squares)
for s,d in values.items():
if d in '0.':
#Also, this line will implement the contradiction check!!!
values_Possible[s] = ''.join(set(digits)-set(values[s2] for s2 in peers[s] if values[s2] in digits))
if len(values_Possible[s]) == 0:
return False,False
return values, values_Possible
def display(values):
"Display these values as a 2-D grid"
digits = '123456789'
if isinstance(values, str):
chars = [c for c in values if c in digits or c in '0.']
values = dict(zip(squares, chars))
for s,d in values.items():
if d in '0.':
values[s] = ''
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)
#return values
def solver(values):
# This is the solver!!!
values, values_Possible = parse_Grid(values)
if not values_Possible:
return False
display(values)
print('-'*30)
if not all(len(d) == 0 for s,d in values_Possible.items()):
n,s = min((len(d),s) for s,d in values_Possible.items() if len(d)!=0)
print(n,s,values_Possible[s])
return some(solver(assign(values.copy(),s, d)) for d in values_Possible[s]) # This is a generator!!!
return values
def some (seq):
if isinstance(seq, collections.Iterable):
for e in seq:
print(e)
if e:
return e
else:
if seq:
return seq
return False
def assign(values, s, d):
values[s] = d
return values
# some constants
digits = '123456789'
cols = '123456789'
rows = 'ABCDEFGHI'
squares = cross(rows,cols)
unitlist = ([cross(a,cols) for a in rows] +
[cross(rows,b) for b in cols] +
[cross(rb,cb) for rb in ('ABC','DEF','GHI') for cb 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)
然后输入要求解的问题，
puzzle = '''005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700'''
求解
a = solver(values)
然后输出
display(a)
结果如下，搞定
