Next / Previous / Contents / Shipman's homepage


Describes a program to solve Sudoku puzzles, using the Python programming language.

This publication is available in Web form and also as a PDF document. Please forward any comments to

Table of Contents

1. Introduction
2. Encoding the puzzle
3. Operation of the solver
4. Design considerations
5. The sudosolver module: Puzzle-solving logic
5.1. Prologue
5.2. Manifest constants
5.3. class SudokuSolver
5.4. SudokuSolver.__init__(): Constructor
5.5. SudokuSolver.__readPuzzle(): Convert puzzle to internal form
5.6. SudokuSolver.__readChar(): Translate one input character
5.7. SudokuSolver.get(): Fetch one value from the board
5.8. SudokuSolver.__rowColToX(): Convert row and column to board position
5.9. SudokuSolver.write(): Output the state of the puzzle
5.10. SudokuSolver.writeRow(): Write one row of the puzzle
5.11. SudokuSolver.solve(): Find all solutions
5.12. SudokuSolver.__reSolve(): Recursive solver method
5.13. SudokuSolver.__solution(): Signal a solution
5.14. SudokuSolver.__findPossibles(): What digits are legal at a given position?
5.15. SudokuSolver.__usedInRow(): Eliminate digits by row
5.16. SudokuSolver.__usedInColumn(): Eliminate digits by column
5.17. SudokuSolver.__usedInSubmat(): Eliminate digits by submatrix
5.18. SudokuSolver.__set(): Store a value in a cell
5.19. SudokuSolver.__xToRowCol(): Translate board position to row and column
6. sudoku: Simple text-based solver
6.1. sudoku: Prologue
6.2. Imports
6.3. main(): Main procedure
6.4. message(): Write to the standard error stream
6.5. fatal(): Report a fatal error
6.6. solveFile(): Solve one puzzle
6.7. solutionFound(): The observer callback for solutions
6.8. sudoku: Epilogue
7. Trace tables
7.1. Trace table: SudokuSolver.__init__()
7.2. Trace table: SudokuSolver.__readPuzzle()
7.3. Trace table: SudokuSolver.get()
7.4. Inspection: SudokuSolver.write()
7.5. Inspection: SudokuSolver.writeRow()