# Sudoku 9x9 solver
# Nicolas RAPIN @ 2015 12 02
def to_be_tested(grid, i, j):
# Remember that grid contains 0 to 9 digits
# and that 0 holds for "free cell".
# We fill a list pres (for "present") such that
# pres[k] == 0 iff k is not present in "line i", "column j" and "block of (i,j)"
pres = [0]*10
for w in range(9):
# line i
pres[grid[i][w]] += 1
# column j
pres[grid[w][j]] += 1
# (i,j) block
origine_bloc_i = i - i%3
origine_bloc_j = j - j%3
for ii in range(origine_bloc_i,origine_bloc_i+3):
for jj in range (origine_bloc_j,origine_bloc_j+3):
pres[grid[ii][jj]] += 1
return pres
def isValid(grid, position):
if (position == 81):
for l in grid:
print(l)
print()
return False
i = position // 9
j = position % 9
if grid[i][j] != 0:
return isValid(grid,position+1)
k = 1
# first element is not considered (number of free cells in line/column/block)
for n in to_be_tested(grid, i, j)[1:]:
# if n not present in line/column/block we try it
if n == 0:
grid[i][j] = k
if isValid(grid,position+1):
return True
k += 1
# No convenient digit in to_be_tested at this recursive call
# we reset grid[i][j] to 0 and return False for
# parent calls ... = backtracking
grid[i][j] = 0
return False
def sudoku_solver():
grid = [[9,7,0,1,0,0,0,0,5],
[0,0,5,0,9,0,2,0,1],
[8,0,2,6,4,0,0,9,0],
[0,0,0,0,8,0,0,0,0],
[0,0,0,7,0,0,0,0,0],
[0,0,0,0,2,6,0,0,9],
[2,0,0,3,0,0,0,0,6],
[7,0,0,2,0,0,9,0,8],
[0,0,1,9,0,4,5,7,0]];
for l in grid:
print(l)
print("\nSolution(s):\n")
isValid(grid,0)
sudoku_solver()