# Enter your code here. Read input from STDIN. Print output to STDOUT
class SudokuSolver(object):
def __init__(self, N=3, puzzle=None):
self.N = N
self.SIZE = self.N*self.N
self.puzzle = [[set([1])]*(self.SIZE)]*(self.SIZE)
if puzzle is None:
for i in range(self.SIZE):
self.puzzle[i] = [int(k) for k in raw_input()]
else:
self.puzzle = [[int(k) for k in line] for line in puzzle.splitlines()]
self._empty_cells = 0
self._solutions = [[set([]) for i in range(self.SIZE)] for k in range(self.SIZE)]
#print self.puzzle
#print self._solutions
for i in range(self.SIZE):
for j in range(self.SIZE):
if self.puzzle[i][j] < 1:
self._solutions[i][j] = set(range(1,self.SIZE+1))
self._empty_cells += 1
#print "puzzle[%s][%s] = %s\tsolutions[%s][%s] = %s" % (i,j, self.puzzle[i][j], i, j, self._solutions[i][j])
else:
self._solutions[i][j] = set([])
#print self._solutions
def get_remove_sets(self, i, j):
remove_items = []
remove_items.extend(self.puzzle[i]) # Row items
remove_items.extend([self.puzzle[k][j] for k in range(self.SIZE)]) # Col items
x, y = i/self.N, j/self.N
remove_items.extend([self.puzzle[x*self.N + (k/3)][y*self.N + (k%3)] \
for k in range(self.SIZE)]) # Square items
remove_set = set(remove_items) - set([0])
#print "Remove_Set[%s][%s] = %s" % (i, j, remove_set)
return remove_set
def solve(self):
run_times = self.SIZE*self.SIZE
print "Original with Empty Cells = %s" % self._empty_cells
self.showSudoku()
changed_cell = True
#print "Original Solution Table"
#print self._solutions
#self.showSudoku(arr=self._solutions, sep="\t")
while(self._empty_cells > 0 and changed_cell):
# Row wise selection of solutions
#print "Filling row wise"
changed_cell = False
for i in range(self.SIZE):
for j in range(self.SIZE):
if self.puzzle[i][j] != 0:
continue
remove_set = self.get_remove_sets(i, j)
#print "Before solutions[%s][%s] = %s, Remaining: %s" % (i, j, self._solutions[i][j], self._empty_cells)
self._solutions[i][j] -= remove_set
#print "After solutions[%s][%s] = %s, Remaining: %s" % (i, j, self._solutions[i][j], self._empty_cells)
if len(self._solutions[i][j]) == 1:
self.puzzle[i][j] = self._solutions[i][j].pop()
self._empty_cells -= 1
changed_cell = True
#print "Adding puzzle[%s][%s] = %s, Remaining: %s" % (i, j, puzzle[i][j], empty_cells)
continue
run_times -= 1
print "Solved with Empty Cells = %s" % self._empty_cells
self.showSudoku()
def solveRecurse(self, puzzle=None):
if puzzle is None:
puzzle = self.puzzle
found = False
for i in range(self.SIZE):
for j in range(self.SIZE):
if puzzle[i][j] == 0:
found = True
break
if found:
break
found_pos = (i, j)
if not found:
self.showSudoku(arr=puzzle)
remove_set = self.get_remove_sets(i, j)
#print found_pos, remove_set
for m in range(1, self.SIZE+1):
if m not in remove_set:
#print "Puttin %s at %s" % (m, found_pos)
puzzle[found_pos[0]][found_pos[1]] = m
self.solveRecurse(puzzle=puzzle)
def showSudoku(self, arr = None, sep=""):
if arr is None:
arr = self.puzzle
# Print final matrix
for i in range(self.SIZE):
print sep.join([str(k) for k in arr[i]])