数独终结者

这篇文章简单介绍下“数独求解器”怎么用程序实现？？
文章背景图片是一个比较难的数独问题，感兴趣的可以试着手动求解啊。
这里暂时不多解释，直接贴代码，等有时间了详细解释下具体怎么实现的。代码使用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)

结果如下，搞定