Sudoku

A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles
J. F. Crook

T

he puzzle Sudoku has become the passion of many people the world over in the past few years. The interesting fact about Sudoku is that it is a trivial puzzle to solve. The reason it is trivial to solve is that an algorithm exists for Sudoku solutions. The algorithm is a tree-based search algorithm based on backtrackingin a tree until a solution is found. If all a person needs to do is sit down at their personal computer, punch in the numbers given in the puzzle, and then watch a computer program compute the solution, we can reasonably ask why a person would bother to struggle to solve Sudoku puzzles. The reason is that people enjoy struggling with pencil and paper to work out Sudoku solutions. Herzberg and Murty(2007, p. 716) give two reasons for the enjoyment of this struggle: First, it is sufficiently difficult to pose a serious mental challenge for anyone attempting to do the puzzle. Secondly, simply by scanning rows and columns, it is easy to enter the “missing colors”, and this gives the solver some encouragement to persist. This paper develops an algorithm for solving any Sudoku puzzle by pencil andpaper, especially the ones classified as diabolical.

down into nine 3 × 3 subboards that do not overlap. We call these subboards boxes and number them from 1 to 9 in typewriter order beginning in the upper left-hand corner of the board, as displayed in Figure 1. The notation for referring to a particular cell on the board is to give the row number followed by the column number. For example, thenotation c (6, 7)—where c denotes cell—denotes the cell at the intersection of row 6 and column 7. The theory we develop in the next section uses the widely known concept of matching numbers across cells. Various authors, as suits their whim, name matching numbers differently. For example, Sheldon (2006, p. xiv) names them partnerships, whereas Mepham (2005, p. 9) names the concept number sharing.Here, we will use the name preemptive sets, which is more precise from a mathematical point of view. The theory developed here applies to Sudoku boards of all sizes.1
Sudoku boards can be classified into regular and nonregular boards. The formula for regular Sudoku boards is: Let m denote the width and height of a Sudoku subboard, where m ≥ 2. Then the width and height of a regular Sudoku board ism2 . The sizes of regular subboards and boards are given for a few values of m in the following table: Subboard Width and Height m 2 3 4 5 6 Board Width and Height m2 4 9 16 25 36 Number of Cells on the Board m2 × m2 16 81 256 625 1296
1

Definition of the Sudoku Board
Sudoku is played on a 9 × 9 board. There are eighty-one cells on the board, which is broken
J. F. Crook is professor emeritusof computer science, Winthrop University, Rock Hill, SC. His email address is crookj@winthrop.edu. I thank John Hohn, Kathryn Cooper, David Gill, and Libby Neely for reading my paper. I also thank Loretta Nethercot for giving me my first two Sudoku books—on Christmas Day, 2005, and on my seventieth birthday in 2007.

The most common nonregular Sudoku board is the 6 × 6, which consists of sixnonoverlapping 2 × 3 subboards. The newspaper USA Today publishes 6 × 6 puzzles regularly.

460

Notices of the AMS

Volume 56, Number 4

Figure 1. The Sudoku board.

Figure 2. Example of a Sudoku puzzle.

Preemptive Sets and the Occupancy Theorem
The single most important tool for solving Sudoku puzzles is based on the definition of the solution of a Sudoku puzzle. Definition 1 (SudokuSolution). The solution of a Sudoku puzzle requires that every row, column, and box contain all the numbers in the set [1, 2, . . . , 9] and that every cell be occupied by one and only one number. This definition implies that no row, column, or box will have any number repeated. An example of a Sudoku puzzle is shown in Figure 2. The more difficult puzzles can only be solved efficiently by writing down...