个人资料
正文

sudoku solver in python

(2017-01-31 15:33:53) 下一个

from copy import copy, deepcopy

def neighbors(i,j):
    a = [(k,j) for k in range(9)]
    b = [(i,k) for k in range(9)]
    ic,jc = i//3 * 3 + 1,j//3 * 3 + 1
    c = [(di+ic,dj+jc) for di in range(-1,2,1) for dj in range(-1,2,1)]
    return (a,b,c)

def find_remain(space,l):
    s = {'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}
    for key in l:
        if space[key[0]][key[1]] in s:
            s.pop(space[key[0]][key[1]])
    return s.viewkeys()

def calc_choice(space,i,j):
    nbs = neighbors(i,j)
    r = [find_remain(space,l) for l in nbs]
    return list(r[0] & r[1] & r[2])

class node:
    def __init__(self,space,change_i=-1,change_j=-1,value=-1,choices_before_change = None,final_answer=None):
        self.space = space
        if change_i != -1 and change_j != -1:
            self.space[change_i][change_j] = value
        self.choices = choices_before_change
        self.final_answer = final_answer

    def calc_choices(self,changed_i=-1,changed_j=-1):
        all_open = list(filter(lambda x:self.space[x[0]][x[1]] == '.',[(i,j) for i in range(9) for j in range(9)]))
        if changed_i == -1 and changed_j == -1:
            impacted = all_open
        else:
            impacted = list(filter(lambda x: self.space[x[0]][x[1]] == '.',[ item for sublist in neighbors(changed_i,changed_j) for item in sublist ]))

        for impact_node in impacted:
            self.choices[impact_node[0]][impact_node[1]] = calc_choice(self.space,impact_node[0],impact_node[1])

        min_choice = 9
        min_node = None
        for all_node in all_open:
            if(len(self.choices[all_node[0]][all_node[1]])<min_choice):
                min_choice = len(self.choices[all_node[0]][all_node[1]])
                min_node = all_node

        #now check if the game is complete or calc the next level.
        if min_choice == 0:
            return 0
        elif len(all_open) == 1 and min_choice == 1: # the min_choice here has to be 1
            #[print(item) for item in self.space]
            self.space[min_node[0]][min_node[1]]=self.choices[min_node[0]][min_node[1]][0]
            self.final_answer[0] = self.space
            return 1
        elif len(all_open) == 1 and min_choice != 1:
            return 0
        else:
            #print(self.choices)
            self.next = [node(deepcopy(self.space),min_node[0],min_node[1],value,deepcopy(self.choices),self.final_answer) for value in self.choices[min_node[0]][min_node[1]]]
            for node_item in self.next:
                success = node_item.calc_choices(min_node[0],min_node[1])
                if success == 1:
                    return 1
            return success

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        initial_choices = [[[] for i in range(9)] for j in range(9) ]
        final_answer = [None]
        new_board = [[c for c in item_str] for item_str in board]
        nd = node(new_board,-1,-1,-1,initial_choices,final_answer)
        nd.calc_choices()
        new_board = []
        for item in final_answer[0]:
            str = ''
            for char_i in item:
                str += char_i
            new_board += [str]
        for i in range(len(board)):
            board[i] = new_board[i]
        
        

[ 打印 ]
阅读 ()评论 (0)
评论
目前还没有任何评论
登录后才可评论.