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]
