A Python implementation of a Sudoku solver using backtracking and constraint search. The name is not original but all the work within was completed independently
pydoku.py input.csv [-v]
The vebosity flag is optional and will print out the intial confuguration and the final solution to the screen.
The solver expects an input matrix in a CSV format, with 0 designating the blank entries:
0,3,5,2,9,0,8,6,4
0,8,2,4,1,0,7,0,3
7,6,4,3,8,0,0,9,0
2,1,8,7,3,9,0,4,0
0,0,0,8,0,4,2,3,0
0,4,3,0,5,2,9,7,0
4,0,6,5,7,1,0,0,9
3,5,9,0,2,8,4,1,7
8,0,0,9,0,0,5,2,6
An example input file is provided in the repository as test_ide.csv.
The output correspondingly is a CSV file named solution_$inputfile where $inputfile is the filename of the original template. A solution for the test sudoku provided above would be:
1,3,5,2,9,7,8,6,4
9,8,2,4,1,6,7,5,3
7,6,4,3,8,5,1,9,2
2,1,8,7,3,9,6,4,5
5,9,7,8,6,4,2,3,1
6,4,3,1,5,2,9,7,8
4,2,6,5,7,1,3,8,9
3,5,9,6,2,8,4,1,7
8,7,1,9,4,3,5,2,6
This file is provided in the repository as validate_ide.csv so to avoid name clashes with the solutions generated by the solver.
PuDoKu is heavily inspired by Peter Norvig's excellent description of constraint-search approach towards solving sudoku puzzles. The solver uses recursive constraint search to eliminate the possibilites for each elements on the grid until a single value is determined. The discovery of a valid solution for a particular element removes that solution from all 'peering' elements (e.g. same row, column, or block), thus constraining the problem with each new discovery.
For the situations when the optimal choice cannot be determined from existing constraints alone, one of the possible choices is selected and the constraint search continue until it converges on valid solution for the entire puzzle. The choices that lead to impossible configurations are rolled back and another choice is made in its stead.
The algorithm is not the optimal sudoku solver due to recursion and backtracking, but it is quite fast on a 9x9 grid and can solve even "hard" puzzles with fewer than 20 provided clues.
The solver was developed and tested under Python 2.7.8 provided by Continuum Analytics. All of the code is contained in a single file to simplify portability. The solver is a single class that keeps track of all grid values, checks for solution validity, and performs the constraint search. File reading and writing are stand-alone functions so that the solving implementation is stand-alone from the textual representation in the files. No 3rd party libraries were used in the implementation to minimize dependencies.
There are sanity checks throughout the code, but a complete unit-testing suite should be written to check for any corner cases. The logic for finding a cell's peers should be refactored as well; it works well but is a bit on the ugly side. Since there are a lot of methods for solving sudokus, the code can be further augmented to allow for selection of the underlying algorithm.
CC Eugene Yedvabny, November 2014