解数独代码,Python代码库,德仔网

代码语言
代码分类
【Python】解数独
作者:耀阳 / 发布于2016/4/6/ 1089
解数独的一个小程序，采用暴力破解的方法求解，没有什么优化，因此解16x16的数独有点吃力，耗时基本达到1分钟以上，9x9和12x12的数独能够很快解出
#!/usr/bin/python3
import sys
 
#数独的题目
A = 10
B = 11
C = 12
D = 13
E = 14
F = 15
G = 16
 
array_9 = [
    1,0,0, 3,0,6, 9,0,5, #0
    0,0,0, 9,0,0, 1,0,0, #1
    0,0,3, 0,0,0, 0,8,6, #2
 
    3,7,0, 0,5,0, 0,0,9, #3
    0,0,0, 1,3,9, 0,0,0, #4
    5,0,0, 0,6,0, 0,1,8, #5
 
    8,9,0, 0,0,0, 7,0,0, #6
    0,0,2, 0,0,8, 0,0,0, #7
    7,0,6, 4,0,5, 0,0,1  #8
            ]
 
array_12 = [
    0,C,0,0, 0,0,0,0, 0,0,0,0, #0
    3,0,0,1, 0,7,C,0, B,0,0,4, #1
    8,0,0,B, 0,3,0,0, 0,0,7,5, #2
 
    0,0,3,0, 0,1,0,C, A,4,0,0, #3
    0,0,C,2, A,0,0,0, 7,0,9,0, #4
    0,0,0,0, 0,5,9,0, 3,C,0,1, #5
 
    1,0,8,3, 0,9,7,0, 0,0,0,0, #6
    0,2,0,6, 0,0,0,A, 4,5,0,0, #7
    0,0,A,C, 2,0,6,0, 0,1,0,0, #8
 
    9,6,0,0, 0,0,4,0, 2,0,0,C, #9
    A,0,0,5, 0,2,8,0, 9,0,0,6, #10
    0,0,0,0, 0,0,0,0, 0,0,A,0, #11
            ]
 
array_16 = [
    0,0,0,3, 0,7,9,0, 0,C,0,B, 0,0,5,1, #0
    0,0,B,0, 0,2,0,0, E,1,G,0, 4,6,0,0, #1
    0,7,5,0, 0,0,B,G, F,A,3,0, 2,0,0,0, #2
    A,0,0,0, 0,6,4,F, 0,0,5,0, 0,B,9,7, #3
 
    0,6,9,0, 0,0,0,0, 5,B,0,0, E,0,7,0, #4
    8,0,7,0, 0,A,C,0, 0,0,4,0, 0,D,0,2, #5
    0,D,A,0, 0,0,0,0, 0,F,0,0, 0,0,4,0, #6
    4,3,0,2, 0,0,0,0, G,0,0,0, 6,0,8,0, #7
 
    0,E,0,8, 0,0,0,9, 0,0,0,0, 1,0,D,4, #8
    0,G,0,0, 0,0,D,0, 0,0,0,0, 0,5,6,0, #9
    7,0,D,0, 0,5,0,0, 0,E,1,0, 0,8,0,9, #10
    0,B,0,9, 0,0,1,8, 0,0,0,0, 0,G,3,0, #11
 
    C,9,1,0, 0,3,0,0, 6,5,8,0, 0,0,0,A, #12
    0,0,0,A, 0,4,7,D, 2,3,0,0, 0,9,1,0, #13
    0,0,6,B, 0,1,G,C, 0,0,A,0, 0,2,0,0, #14
    3,4,0,0, A,0,E,0, 0,G,9,0, D,0,0,0, #15
]
 
#要解决的题目
array = array_16
 
#计算数独的边长,然后得出每个宫格的边长
length = len(array)
 
if length == 9*9 :
    side_length = 9
    room_width = 3
    room_height = 3
elif length == 12*12 :
    side_length = 12
    room_width = 4
    room_height = 3
elif length == 16*16 :
    side_length = 16
    room_width = 4
    room_height = 4
else:
    print("Incorrect array!")
    sys.exit()
 
#储存数独当前状态的数据结构
class Status(object):
    #将数独题目读入
    def __init__(self,array):
        self.__record = dict() #key=>坐标，value=>这个坐标中储存的值
        self.__known_coord = list() #储存已知坐标(即已经写入值的坐标)
        self.__unknown_coord = list() #储存未知坐标(即没有写入值的坐标)
 
        for i in range(len(array)):
            if array[i] != 0 :
                self.__known_coord.append((i//side_length,i%side_length))
                self.write_record(self.__known_coord[-1],array[i])
            else:
                self.__unknown_coord.append((i//side_length,i%side_length))
 
    def write_record(self,coord,val):
        self.__record[coord] = val
 
    def read_record(self,coord):
        if coord in self.__record:
            return self.__record[coord]
        else:
            return 0
 
    def read_known(self):
        return self.__known_coord
 
    def read_unknown(self):
        return self.__unknown_coord
 
    def delete_record(self,coord):
        self.__record.pop(coord)
 
    def debug(self,sth):
        if sth == "record_dict":
            for i in range(side_length):
                for j in range(side_length):
                    print("(%d,%d) => %d"%(i,j,self.read_record((i,j))),end="\t")
            print()
        elif sth == "coord_list":
            known_coord = self.read_known()
            print("known_coord: total %d :"%(len(known_coord)))
            for i in known_coord:
                print(i,end="\t")
            print()
 
            unknown_coord = self.read_unknown()
            print("unknown_coord: total %d :"%(len(unknown_coord)))
            for i in unknown_coord:
                print(i,end="\t")
            print()
 
#生成一个数独的状态
status = Status(array)
 
#按照数独的格式打印当前状态
def show():
    MAP_TABLE = "0123456789ABCDEFG"
    for i in range(side_length):
        for j in range(side_length):
            index = status.read_record((i,j))
            print(MAP_TABLE[index],end=" ")
            if (j+1)%room_width == 0:
                print("",end=" ")
        print()
        if (i+1)%room_height == 0:
            print()
    print("--------------------")
 
 
#输入一个坐标，输出这个坐标可以填入的数的list列表
def possible_list(coord):
 
    #返回给定坐标所在行的已存在的数的list列表
    def curr_row():
        exist_val = list()
        for col in range(side_length):
            pos = (coord[0],col)
            exist_val.append(status.read_record(pos))
        return exist_val
 
    #返回给定坐标所在列的已存在的数的list列表
    def curr_col():
        exist_val = list()
        for row in range(side_length):
            pos = (row,coord[1])
            exist_val.append(status.read_record(pos))
        return exist_val
 
    #返回给定坐标所在宫格的已存在的数的list列表
    def curr_room():
        exist_val = list()
        weight = coord[0] // room_height
        ver_span = (weight*room_height, (weight+1)*room_height)
 
        weight = coord[1] // room_width
        hor_span = (weight*room_width, (weight+1)*room_width)
 
        for row in range(ver_span[0], ver_span[1]):
            for col in range(hor_span[0], hor_span[1]):
                exist_val.append(status.read_record((row,col)))
        return exist_val
 
    exist_val = set(curr_row() + curr_col() + curr_room())
    avail_val = set([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16][0:side_length])
 
    possible_val = list(avail_val - exist_val)
    return possible_val
 
 
#获取当前坐标可能数的个数(可能数 即 可以填入的数字)
def possible_num(coord):
    possible = possible_list(coord)
    return len(possible)
 
 
#求解数独
def eval():
    #读取未知坐标的列表
    unknown_list = status.read_unknown() # such as[(0,0),(0,1),...]
 
    def eval_iter(unknown):
        #如果全部坐标都已经填入数字
        if len(unknown) == 0:
            show()
            return
        else:
            #否则将未知坐标按照该坐标的可能值的多少排序，即
            #坐标的可填入数字越少，这个坐标越优先处理
            unknown = sorted(unknown, key=possible_num)
            curr_coord = unknown[0]
            possible_val = possible_list(curr_coord)
 
            #如果当前处理的坐标可能值的个数为0,则说明当前数独的填法有误，直接返回
            if len(possible_val) == 0:
                return
            else:
                #遍历当前坐标的所有可能值，然后将其写入数独状态，再递归调用，处理下一个坐标
                for val in possible_val:
                    status.write_record(curr_coord,val)
                    eval_iter(unknown[1:])
                #当前坐标的所有状态都被遍历完以后，要删除掉当前坐标的记录
                status.delete_record(curr_coord)
 
    eval_iter(unknown_list)
 
eval()
试试其它关键字
　数独　
同语言下
可能有用的
耀阳贡献的其它代码(13)