A sudoku solver |  |
A sudoku solver | |
Abstract
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 tcc-doc@nmt.edu.
Table of Contents
sudosolver.py module: Puzzle-solving logicclass SudokuSolverSudokuSolver.__init__():
ConstructorSudokuSolver.__readPuzzle(): Convert puzzle to internal formSudokuSolver.__readChar():
Translate one input characterSudokuSolver.get(): Fetch
one value from the boardSudokuSolver.__rowColToX():
Convert row and column to board positionSudokuSolver.write():
Output the state of the puzzleSudokuSolver.writeRow():
Write one row of the puzzleSudokuSolver.solve(): Find
all solutionsSudokuSolver.__reSolve():
Recursive solver methodSudokuSolver.__solution():
Signal a solutionSudokuSolver.__findPossibles(): What digits
are legal at a given position?SudokuSolver.__usedInRow():
Eliminate digits by rowSudokuSolver.__usedInColumn(): Eliminate digits by columnSudokuSolver.__usedInSubmat(): Eliminate
digits by submatrixSudokuSolver.__set(): Store
a value in a cellSudokuSolver.__xToRowCol():
Translate board position to row and columnThis document describes the operation and implementation of a Python program to solve sudoku puzzles, a Japanese fad that has been recently caught on in the United States. The program is an illustration of “lightweight literate programming,” in which the program's executable code is embedded in its documentation. For an introduction to lightweight literate programming and numerous examples, see the author's Lightweight literate programming page.
This project uses the Zero-defect or Cleanroom development methodology. For a discussion of this method, see the author's Cleanroom pages.
The framework for a sudoku puzzle is a 9×9 grid. This grid is divided into nine 3×3 submatrices, and the lines between submatrices are thicker.
In an unsolved puzzle, some of the cells of this grid are filled in with digits from 1 through 9, and the rest of the cells are empty. The challenge is to place digits in the empty cells so that:
Each digit appears exactly once in each row.
Each digit appears exactly once in each column.
Each digit appears exactly once in each 3×3 submatrix.
Files mentioned in this document are available online:
sudosolver.py: The module containing the
solution logic.
sudogui: The GUI driver (not
yet written).