• 2012-10-07

长假无聊，玩数独，写了个解的程序，还有改进的余地，请大家拍砖... 第二个脚本优化了数独解法的算法 第三个脚本再一次优化了数独解法的算法并修复某行没有提示时导致的一个bug [2012-12-15 16:45] 后续会陆续给出如何制作一个数独，并配合解法一起，有设有解。

• 2016-10-06

无意中看到4年前的这段代码，使用起来不怎么方便。增加了命令行输入残缺数独的功能。

# -*- coding: utf-8 -*-'''Created on 2012-10-5[@author](https://my.oschina.net/arthor): Administrator'''from collections import defaultdictimport itertoolsimport timeimport gcimport operatorimport profile gc.disable()a = [[ 0, 3, 9, 0, 0, 0, 6, 1, 0 ], [ 7, 0, 0, 3, 0, 8, 0, 0, 4 ], [ 1, 0, 0, 0, 9, 0, 0, 0, 8 ], [ 0, 1, 0, 9, 0, 7, 0, 4, 0 ], [ 0, 0, 3, 0, 2, 0, 9, 0, 0 ], [ 0, 4, 0, 8, 0, 5, 0, 2, 0 ], [ 6, 0, 0, 0, 4, 0, 0, 0, 2 ],  [ 3, 0, 0, 6, 0, 1, 0, 0, 9 ], [ 0, 9, 7, 0, 0, 0, 8, 6, 0 ]  # 0, 1, 2, 3,|4, 5, 6,|7, 8     ]h_d = {} def filter_by_column(y, resource_dict):    '''[@summary](https://my.oschina.net/u/203623): 纵向过滤重复的值    [@param](https://my.oschina.net/u/2303379) y: 待检测的一行排列    [@param](https://my.oschina.net/u/2303379) resource_dict: 列序号及组合在对应列号的值列表    '''    if not resource_dict:        return 1    return all((y[k] not in  v for k, v in resource_dict.iteritems())) sudokus = [] def check_3_lines(f, s, t):    '''[@summary](https://my.oschina.net/u/203623): 检测3行的每三列是不是符合条件    @param f: first line    '''    if len(set((f[0], f[1], f[2], s[0], s[1], s[2], t[0], t[1], t[2]))) != 9:        return 1    if len(set((f[3], f[4], f[5], s[3], s[4], s[5], t[3], t[4], t[5]))) != 9:        return 1    if len(set((f[6], f[7], f[8], s[6], s[7], s[8], t[6], t[7], t[8]))) != 9:        return 1    return 0 def check_2_lines(f, s):    '''@summary: 检测两行数据的每三列是不是有重复值，提前淘汰有重复值的组合    @param f: first line    '''    if len(set((f[0], f[1], f[2], s[0], s[1], s[2]))) != 6:        return 1    if len(set((f[3], f[4], f[5], s[3], s[4], s[5]))) != 6:        return 1    if len(set((f[6], f[7], f[8], s[6], s[7], s[8]))) != 6:        return 1    return 0 def solve_sudoku(h_d, h_idx=None, reserves=None                 , solves=None, resource_dict=None):    '''    @param reserves: 已经验证过符合条件的排列    @param solves: 最终的解决方案集合    @param resource_dict: dict key in range(1,10),values 是每行同一列的数字的列表    '''    if solves is None:        solves = []         if h_idx is None :        h_idx = 0    for l0 in h_d[h_idx]:        if reserves == None:            _reserves = [l0, ]            solve_sudoku(h_d, h_idx + 1, _reserves, solves)        else:            if not filter_by_column(l0, resource_dict):                continue            if h_idx in (1 , 4, 7):                if check_2_lines(reserves[h_idx - 1], l0):                    continue            elif h_idx in (2, 5, 8) :                if check_3_lines(reserves[h_idx - 2], reserves[h_idx - 1], l0):                    continue                                 _reserves = list(reserves)            _reserves.append(l0)            if h_idx < 8:                solve_sudoku(h_d, h_idx + 1, _reserves, solves                             , dict((idx, set([i[idx] for i in _reserves]))                                     for idx in range(0, 9)))            if h_idx == 8:                solves.append(_reserves)                print u"calc No. {num} result".format(num=len(solves))                print u"*" * 50                for i in solves[-1]:                    print i                     else:        if h_idx == 0:            return solves                 if __name__ == '__main__':    print "input incomplete sudoku matrix, blank is 0,split row spearated by comma "    s = raw_input(">")    print s    input_rows = s.split(",")    a = map(lambda x:list(map(lambda y:int(y),x)),input_rows)        #===============================================================================    # 得到坐标点和值，相当于稀疏矩阵:(X,Y):value    #===============================================================================    exists_d = dict(((h_idx, y_idx), v)                     for h_idx, y in enumerate(a)                     for y_idx , v in enumerate(y)  if v)              h_exist = defaultdict(dict)    v_exist = defaultdict(dict)         #===============================================================================    # 二维数组    #===============================================================================    for k, v in exists_d.iteritems():        h_exist[k[0]][k[1]] = v        v_exist[k[1]][k[0]] = v         #===============================================================================    # 生成所有的组合    #===============================================================================    permutations = tuple(itertools.permutations(range(1, 10), 9))              #===============================================================================    # 取得行号与该行符合条件的组合    #===============================================================================    for hk, hv in h_exist.iteritems():                 #===========================================================================        # 过滤横向，x轴与同行已知的点的值重复的组合        #===========================================================================        q = filter(lambda x:all((x[k] == v                                  for k, v in hv.iteritems())), permutations)                 #===========================================================================        # 过滤纵向，Y轴与同列已知的点的值重复的组合        #===========================================================================        q = filter(lambda x:all((x[vk] != v                                  for vk , vv in v_exist.iteritems()                                  for k, v in vv.iteritems()                                  if k != hk)), q)                 h_d[hk] = q         #===============================================================================    # 不全某行没有任何提示    #===============================================================================    for line_idx in range(0, 9):        if line_idx not in h_d:            h_d[line_idx] = permutations    now = time.time()    print time.time() - now     now = time.time()    x = solve_sudoku(h_d)    print time.time() - now    print x

增加了手动录入缺失矩阵的功能。