A brute-force sudoku solver, using iteration and backtracking.
By using iteration, we can avoid any need for tail-call optimisation in a recursive solution.
Written for and tested on Python 3.7.5
usage: py_sudoku_solver.py [-h] GRID
Backtracking iterative solver for a sudoku grid.
Prints the solved grid, if successful. Otherwise states not solvable.
positional arguments:
GRID String representing unsolved grid of len(81). Empties must be
given as 0's. Spaces, commas and brackets will be ignored.
ie. '[1,2,0,5...3,5]' or '1205...35'
>python py_sudoku_solver.py "[2, 0, 9, 0, 8, 0, 5, 0, 0, 0, 0, 4, 7, 6, 9, 0, 0, 0, 3, 0, 0, 0, 1, 2, 0, 4, 0, 0, 0, 3, 6, 0, 0, 0, 5,
4, 0, 4, 0, 0, 0, 0, 0, 8, 0, 8, 5, 0, 0, 0, 7, 6, 0, 0, 0, 2, 0, 8, 7, 0, 0, 0, 9, 0, 0, 0, 1, 9, 6, 2, 0, 0, 0, 0, 5, 0, 4, 0, 1, 0, 8]"
Input read as:
[2, 0, 9, 0, 8, 0, 5, 0, 0]
[0, 0, 4, 7, 6, 9, 0, 0, 0]
[3, 0, 0, 0, 1, 2, 0, 4, 0]
[0, 0, 3, 6, 0, 0, 0, 5, 4]
[0, 4, 0, 0, 0, 0, 0, 8, 0]
[8, 5, 0, 0, 0, 7, 6, 0, 0]
[0, 2, 0, 8, 7, 0, 0, 0, 9]
[0, 0, 0, 1, 9, 6, 2, 0, 0]
[0, 0, 5, 0, 4, 0, 1, 0, 8]
Solution required 2479 iterations
Solved!
[2, 6, 9, 3, 8, 4, 5, 1, 7]
[5, 1, 4, 7, 6, 9, 8, 2, 3]
[3, 8, 7, 5, 1, 2, 9, 4, 6]
[1, 9, 3, 6, 2, 8, 7, 5, 4]
[7, 4, 6, 9, 5, 1, 3, 8, 2]
[8, 5, 2, 4, 3, 7, 6, 9, 1]
[6, 2, 1, 8, 7, 5, 4, 3, 9]
[4, 3, 8, 1, 9, 6, 2, 7, 5]
[9, 7, 5, 2, 4, 3, 1, 6, 8]
The main function in the script is solve() which takes an iterable of the sudoku elements as an input, and returns a completed list.
py_soduku_solver.solve(grid: iter) -> solved_grid: list
The input should be of len 81 to represent a sudoku board, in the order [[r0,c0], [r0,c1] ...[r8,c8]].
Empty items in the input must be None or empty strings / lists.
Any element outside of the 1-9 range will also be replaced with None by the function.
The printable_grid() function can generate the list in a more viewable form:
py_soduku_solver.printable_grid(grid: iter) -> list[lists]
Useable as:
print(*printable_grid(grid), sep='\n')
Which outputs:
[3, 5, 9, 6, 7, 8, 1, 4, 2]
[1, 7, 8, 2, 9, 4, 5, 3, 6]
[6, 4, 2, 1, 5, 3, 7, 8, 9]
[4, 2, 3, 7, 8, 5, 9, 6, 1]
[8, 1, 5, 9, 4, 6, 3, 2, 7]
[9, 6, 7, 3, 1, 2, 4, 5, 8]
[2, 9, 4, 8, 3, 1, 6, 7, 5]
[5, 8, 1, 4, 6, 7, 2, 9, 3]
[7, 3, 6, 5, 2, 9, 8, 1, 4]
Items which are None are replaced with 0 for printing, to ensure correct spacing, i.e:
[0, 0, 0, 6, 7, 0, 0, 4, 0]
[1, 0, 0, 0, 0, 0, 0, 3, 6]
[0, 4, 2, 1, 0, 0, 0, 0, 0]
[4, 0, 0, 7, 0, 0, 0, 0, 0]
[0, 0, 5, 0, 0, 0, 3, 0, 0]
[0, 0, 0, 0, 0, 2, 0, 0, 8]
[0, 0, 0, 0, 0, 1, 6, 7, 0]
[5, 8, 0, 0, 0, 0, 0, 0, 3]
[0, 3, 0, 0, 2, 9, 0, 0, 0]