This 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: