9x9数独算法

下面给出了源代码
sdks文件里面含有120个数独
请各位大大纠正

这个算法也可以用来做生成数独，然后取出几个
比如你给定数独为

000000000000000000000000000000000000000000000000000000000000000000000000000000001
# 嘿嘿，这解可多了，机器别跑死了。

# -*- coding:utf-8 -*-
'''
首先生成9x9x9的三维数组，每个值为[1,2,3,4,5,6,7,8,9]
1，然后确定有独一的值，清除行，列，块当中的值 clean(data)函数
继续1
然后找到唯一值，即行、列或块当中只出现一次的值，设置当前值，然后执行1，clean_help(data)函数
最后如果没有唯一值那就找最少候选的那个格子先尝试这个格子的其中一个候选，再尝试剩余的候选数字
'''

#1. 先遍历一遍，找出所有“只有一个候选数字”的格子, 清除行，列，块数据
#2. 填满这些数字，重复第一步
#3. 如果没有“只有一个候选数字”的格子，那就找最少候选的那个格子
#　　先尝试这个格子的其中一个候选，再尝试剩余的候选数字
from copy import deepcopy
# 移除数组中指定的值
def rm(s, n):
    i = 0
    try:
        s.remove(n)
        i = i + 1
    except:
        pass
    return i
# 根据行，列坐标，返回行，列，块数组
def find(fbs, i, j):
    block = [] 
    br = i / 3 * 3
    bc = j / 3 * 3
    for l in range(0, 3):
        r = br + l
        for k in range(0, 3):
            c = bc + k
            block.append(fbs[r][c])
    return {"row":fbs[i], "column":[fbs[a][j] for a in range(0, 9)], "block":block}
# 打印
def pnt(dbss):
    print "============"
    for i in range(0, 9):
        print dbss[i], "\n" 
# 生成9×9×9的三维数组
base = [[[i for i in range(1, 10)] for a in range(1, 10)] for b in range(1, 10)]
sudo1 = [
        [0,8,1, 0,9,0, 0,0,0], 
        [0,0,0, 1,0,7, 0,5,0],
        [0,7,5, 0,4,0, 0,0,1],
        [0,0,0, 0,3,4, 2,0,0],
        [5,0,0, 7,0,1, 0,0,0],
        [0,0,0, 0,0,2, 1,0,9],
        [0,0,6, 0,8,0, 0,0,4],
        [8,0,7, 6,0,0, 5,0,0],
        [0,0,3, 0,0,0, 6,0,8]
        ]
# 此数独没有解出来。
sudo2 = [ 
                [ 8, 0, 0, 0, 0, 0, 0, 0, 0 ], 
                [ 0, 0, 3, 6, 0, 0, 0, 0, 0 ], 
                [ 0, 7, 0, 0, 9, 0, 2, 0, 0 ], 
                [ 0, 5, 0, 0, 0, 7, 0, 0, 0 ], 
                [ 0, 0, 0, 0, 4, 5, 7, 0, 0 ], 
                [ 0, 0, 0, 1, 0, 6, 0, 3, 0 ], 
                [ 0, 0, 1, 0, 0, 0, 0, 6, 8 ],  
                [ 0, 0, 8, 5, 0, 0, 0, 1, 0 ], 
                [ 0, 9, 0, 0, 0, 0, 4, 0, 0 ]  
                   ]
                   
# 此数独有解，但死循环                   
sudo3 = [
         [0, 0, 0, 0, 1, 0, 0, 0, 0],
         [0, 0, 0, 2, 0, 3, 0, 0, 0],
         [0, 0, 4, 0, 0, 0, 5, 0, 0],
         [0, 6, 0, 0, 0, 0, 0, 7, 0],
         [8, 0, 0, 0, 5, 0, 0, 0, 9],
         [0, 7, 0, 0, 0, 0, 0, 6, 0],
         [0, 0, 5, 0, 0, 0, 4, 0, 0],
         [0, 0, 0, 3, 0, 2, 0, 0, 0],
         [0, 0, 0, 0, 9, 0, 0, 0, 0]
         ]
sudo4 = [
         [0, 0, 0, 0, 1, 0, 8, 7, 0],
         [0, 2, 0, 0, 9, 0, 0, 0, 0],
         [0, 0, 0, 5, 0, 0, 0, 0, 0],
         [2, 0, 0, 0, 6, 8, 0, 9, 0],
         [0, 0, 8, 0, 7, 0, 3, 0, 0],
         [0, 9, 7, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 4, 6, 3, 0],
         [0, 8, 0, 0, 5, 0, 0, 0, 0],
         [0, 7, 1, 3, 0, 0, 9, 0, 0]
         ]

sudo5 = [
             [0,0,2,4,5,0,7,0,0]
            ,[0,4,0,0,0,8,0,3,0]
            ,[8,0,1,0,0,3,5,0,6]
            ,[0,5,3,0,0,0,0,0,4]
            ,[7,0,0,0,0,0,0,0,2]
            ,[2,0,0,0,0,0,6,7,0]
            ,[3,0,6,5,0,0,1,0,7]
            ,[0,2,0,1,0,0,0,5,0]
            ,[0,0,7,0,2,9,4,0,0]
         ]

# 初始化填充base
def inits(b, s):
    for i in range(0, 9):
        sudo = s[i]
        for j in range(0, 9):
            num = sudo[j]
            if num != 0:
                b[i][j] = [num]
                finds = find(b, i, j)
                for f in finds:
                    ff = finds[f]
                    for fff in ff:
                        if len(fff) > 1:
                            rm(fff, num)
    return b
            
# 根据独一值，清除行，列，块值                            
def clean(clean_data):
    flag = True
    while flag:
        # 退出条件
        rms = 0
        for i in range(0, 9):
            for j in range(0, 9):
                num = clean_data[i][j]
                if len(num) == 1:
                    # 根据独一值清除行，列，块
                    finds = find(clean_data, i, j)
                    for f1 in finds:
                        f2 = finds[f1]
                        for f3 in f2:
                            if len(f3) > 1:
                                rms += rm(f3, num[0])
        if rms == 0:
            flag = False
    return clean_data
# 找到唯一值，并清除行列块
def clean_help(data):
    while True:
        # 退出条件
        flag = True
        for i in range(0, 9):
            for j in range(0, 9):
                brk = 0
                cur = data[i][j]
                if len(cur) > 1:
                    finds = find(data, i, j)
                    for f in finds:
                        a = [0] * 9
                        f1 = finds[f]
                        for f2 in f1:
                            for f3 in f2:
                                a[f3 - 1] += 1
                        for m in cur:
                            # 找到了唯一值，并进行设置，清除数独，退出当前循环
                            if a[m - 1] == 1:
                                flag = False
                                brk = 1
                                data[i][j] = [m]
                                clean(data)
                                break
                        if brk == 1:
                            break
        # 当没有唯一值是退出循环
        if flag:
            break
    return data

# 读取数独源
def readSdks(i):
    sudokus = open("sdks", "r")
    if i < 0 or i > 125:
        print "Not found sudoku data"
        return
    sdk = sudokus.readlines()[i].replace("\n","")
    sdks = [sdk[j:j + 9] for j in range(0, 81, 9)]
    #print sdks
    ret = [[int(sk[l]) for l in range(0, 9)] for sk in sdks]
    sudokus.close()
    
    return ret
    
# 验证数独    
def isOk(data):
    for i in range(0, 9):
        for j in range(0, 9):
            finds = find(data, i, j)
            for f in finds:
                a = [0] * 9
                ff = finds[f]
                for fff in ff:
                    if len(fff) > 1:
                        return False
                    a[fff[0] - 1] += 1
                for ia in a:
                    if ia > 1 or ia == 0:
                        return False
    print  "ok"
    return True

# 找到数独当中最小候选对象元祖
#([], x, y) 数组为候选可能值，x为行坐标，y为列坐标
def small(data):
    ret_sm = ([0] * 9, -1, -1)
    for i in range(0, 9):
        for j in range(0, 9):
            if len(data[i][j]) > 1 and len(data[i][j]) < len(ret_sm[0]):
                ret_sm = (data[i][j], i, j)
    return ret_sm

# 最后数独完成操作 设置候选值
def done(data):
    if isOk(data):
        pnt(data)
        return
    sm_tuple = small(data)
    #print sm_tuple
    if sm_tuple[1] == -1:
        #print "no solve"
        return
    # 设置候选值
    for sm in sm_tuple[0]:
        #pnt(data)
        # 复制数独源，上次的结果不然还存在，就不能求多解了
        copy_data = deepcopy(data)
        # 设置候选值
        copy_data[sm_tuple[1]][sm_tuple[2]] = [sm]
        # 然后执行清除操作
        copy_data = clean_help(clean(copy_data))
        if isOk(copy_data):
            #print "in done"
            pnt(copy_data)
            return
        # 如果没有完成，继续设置候选值
        done(copy_data)


def main():
    for i in range(0, 120):
        print "The %d index" % i
        #readSdks(1)
        sudokuData = readSdks(i)
        base = [[[j for j in range(1, 10)] for a in range(1, 10)] for b in range(1, 10)]
        init_data = inits(base, sudokuData)
        #print "init:"
        #pnt(init_data)
        clean_data = clean(init_data)
        #print "clean:"
        #pnt(clean_data)
        only_data = clean_help(clean_data)
        #print "only:"
        #pnt(only_data)
        done(only_data)
        
if __name__ == "__main__":
    main()