Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Sudoku Solver by Amachua
from copy import deepcopy
def getColumnNumber(column, grid):
return [grid[i][column] for i in range(9)]
def getSquarreNumber(row, column, grid):
xo, yo = (row//3)*3,(column//3)*3
return [grid[xo+i//3][yo+i%3] for i in range(9)]
# Check if all number of the grid have been found.
def isNotFinished(grid):
for i in range(9):
for j in range(9):
if not grid[i][j]:
return True
return False
# Check if the grid is possible. For that purpose, we check the lenght of the probability of each case.
# If there is no possibility and the value hasn't been set on the grid it means that the grid is not possible.
def isPossible(grid, prob):
for i in range(9):
for j in range(9):
if not grid[i][j] and not len(prob[i][j]):
return False
return True
def checkio(grid):
# Create a grid with all the possible values in each case.
prob = [[[] if grid[j][i] else [1, 2, 3, 4, 5, 6, 7, 8, 9] for i in range(9)] for j in range(9)]
hasChanged = True
# Removes the possibility number from prob (if a number is on a case, it can't be in another case on the same row/column/square).
while hasChanged:
hasChanged=False
for i in range(9):
for j in range(9):
# If the lengh of prob == 1 it means that it can only be this value on the case. So we add it on the grid.
if len(prob[i][j]) == 1:
grid[i][j]=prob[i][j].pop(0)
haschanged = True
continue
nb = set(getColumnNumber(j, grid) + grid[i] + getSquarreNumber(i,j, grid))
for k in range(len(prob[i][j])):
c=prob[i][j].pop(0)
if c in nb:
haschanged = True
continue
prob[i][j].append(c)
# Check if the grid is still possible.
if not isPossible(grid, prob):
return grid
# If the grid is still possible and is not finished. A choice have to be made.
if isNotFinished(grid):
best, bi, bj = 9, 0, 0
# Select the case with the less possibilities. If two possibilities we break the loop (because we cannot found a case under two).
for i in range(9):
for j in range(9):
if 0 < len(prob[i][j]) < best:
bi, bj, best = i, j, len(prob[i][j])
if best == 2: break
# Test the possibility and if the test found the answer return it.
for i in range(best):
gridbis = deepcopy(grid)
gridbis[bi][bj]=prob[bi][bj].pop(0)
gridbis = checkio(gridbis)
if not isNotFinished(gridbis):
return gridbis
return grid
Nov. 11, 2013
Comments:
