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] |