Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Worst solution in Clear category for Sudoku Solver by rfonseca
NUM_SET = set((x for x in range(1, 10))) # Just for convenience
# Coordinates for each enclosing square given its coordinate ((0,0) ... (3, 3))
SQUARE_DIRS = {
(x, y): [(i, j) for i in range(x*3, x*3 + 3) for j in range(3*y, 3*y + 3)] \
for x in range(3) for y in range(3)
}
def get_possibilites(grid, pos):
"""
Following the rules of the Sudoku game, return all the possible numbers
for a particular position in the game board. Return an empty set if there are
no possibilities any more.
"""
used_numbers = get_line(grid, pos) | get_column(grid, pos) | get_square(grid, pos)
return NUM_SET - used_numbers
def get_line(grid, pos):
""" Return the used numbers in the line of grid[pos] """
return set(grid[pos[0]][j] for j in range(9) if grid[pos[0]][j] != 0)
def get_column(grid, pos):
""" Return the used numbers in the column of grid[pos] """
return set(grid[i][pos[1]] for i in range(9) if grid[i][pos[1]] != 0)
def get_square(grid, pos):
""" Return the used numbers in the enclosing square of grid[pos] """
sp = (pos[0] // 3, pos[1] // 3) # Enclosing square position in the grid
return set(grid[i][j] for i, j in SQUARE_DIRS[sp] if grid[i][j] != 0)
def backtrack(grid):
"""
Simple backtrack solution for the Sudoku problem.
"""
complete = True
for i, line in enumerate(grid):
for j, num in enumerate(line):
# Nothing to do when there already is an assigned number
if num != 0:
continue
# If there is a '0' in any position, the board is not complete yet
complete = False
possibilities = get_possibilites(grid, (i, j))
# Something went wrong at some point since there are no more
# possibilities available for the current position
if len(possibilities) == 0:
return None
for attempt_num in possibilities:
grid[i][j] = attempt_num
if backtrack(grid) != None: # Found a valid solution
return grid
grid[i][j] = 0
return None
return grid if complete is True else None
# Return the solution of the sudoku.
def checkio(grid):
return backtrack(grid)
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([[0, 7, 1, 6, 8, 4, 0, 0, 0],
[0, 4, 9, 7, 0, 0, 0, 0, 0],
[5, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 0, 0, 0, 0, 5, 0, 4],
[0, 0, 0, 3, 0, 7, 0, 0, 0],
[2, 0, 3, 0, 0, 0, 0, 9, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 9],
[0, 0, 0, 0, 0, 3, 7, 2, 0],
[0, 0, 0, 4, 9, 8, 6, 1, 0]]) == [[3, 7, 1, 6, 8, 4, 9, 5, 2],
[8, 4, 9, 7, 2, 5, 3, 6, 1],
[5, 6, 2, 9, 3, 1, 4, 7, 8],
[6, 8, 7, 2, 1, 9, 5, 3, 4],
[9, 1, 4, 3, 5, 7, 2, 8, 6],
[2, 5, 3, 8, 4, 6, 1, 9, 7],
[1, 3, 6, 5, 7, 2, 8, 4, 9],
[4, 9, 8, 1, 6, 3, 7, 2, 5],
[7, 2, 5, 4, 9, 8, 6, 1, 3]], "first"
assert checkio([[5, 0, 0, 7, 1, 9, 0, 0, 4],
[0, 0, 1, 0, 3, 0, 5, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 5, 9, 7, 2, 6, 4, 0],
[0, 0, 0, 6, 0, 1, 0, 0, 0],
[0, 2, 6, 3, 8, 5, 9, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 0, 5, 0, 2, 0, 0],
[8, 0, 0, 4, 9, 7, 0, 0, 6]]) == [[5, 6, 8, 7, 1, 9, 3, 2, 4],
[9, 7, 1, 2, 3, 4, 5, 6, 8],
[2, 3, 4, 5, 6, 8, 7, 9, 1],
[1, 8, 5, 9, 7, 2, 6, 4, 3],
[3, 9, 7, 6, 4, 1, 8, 5, 2],
[4, 2, 6, 3, 8, 5, 9, 1, 7],
[6, 1, 9, 8, 2, 3, 4, 7, 5],
[7, 4, 3, 1, 5, 6, 2, 8, 9],
[8, 5, 2, 4, 9, 7, 1, 3, 6]], "second"
print('Done')
Feb. 25, 2014
Comments:
