In [32]:
# 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]])
In [33]:
s = SudokuSolver(puzzle="003020600\n900305001\n001806400\n008102900\n700000008\n006708200\n002609500\n800203009\n005010300")
s.solveRecurse()
s.showSudoku()
In [10]:
p = """200080300
060070084
030500209
000105408
000000000
402706000
301007040
720040060
004010003"""
s = SudokuSolver(puzzle=p)
s.solve()
In [13]:
print "Done"
In [29]:
# Another implementation taken from: http://pythontips.com/2013/09/01/sudoku-solver-in-python/
import sys
def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
def r(a):
i = a.find('0')
if i == -1:
print a
print "\n".join([a[k*9:k*9+9] for k in range(9)])
excluded_numbers = set()
for j in range(81):
if same_row(i,j) or same_col(i,j) or same_block(i,j):
excluded_numbers.add(a[j])
#print i, i/9, i%9, excluded_numbers
for m in '123456789':
if m not in excluded_numbers:
#print "Puttin %s at %s, %s, %s" % (m, i, i/9, i%9)
r(a[:i]+m+a[i+1:])
In [30]:
r("200080300060070084030500209000105408000000000402706000301007040720040060004010003")
In [31]:
r("003020600900305001001806400008102900700000008006708200002609500800203009005010300")
In [ ]: