4765 words - 20 pages

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 backtracking in 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. ...view middle of the document...

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

1

Sudoku boards can be classiﬁed 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 is m2 . The sizes of regular subboards and boards are given for a few values of m in the

following table:

Deﬁnition of the Sudoku Board

Subboard Width

and Height

m

2

3

4

5

6

Sudoku is played on a 9 × 9 board. There are

eighty-one cells on the board, which is broken

J. F. Crook is professor emeritus of 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 ﬁrst two Sudoku books—on

Christmas Day, 2005, and on my seventieth birthday in

2007.

460

Board Width

and Height

m2

4

9

16

25

36

Number of Cells

on the Board

m2 × m2

16

81

256

625

1296

The most common nonregular Sudoku board is the

6 × 6, which consists of six nonoverlapping 2 × 3 subboards. The newspaper USA Today publishes 6 × 6

puzzles regularly.

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 deﬁnition of the solution

of a Sudoku puzzle.

Deﬁnition 1 (Sudoku Solution). 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 deﬁnition 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

diﬃcult puzzles can only be solved eﬃciently by

writing down in each empty cell the possible numbers that can occupy the cell. This list of possible

numbers for each cell is called the markup of the

cell. The markup of the example puzzle in Figure

2 is shown in Figure 3.

We now deﬁne preemptive sets, which is the

primary tool for solving Sudoku puzzles up to

the point where either (1) a solution is found or

(2) continuation requires randomly choosing one

of two or more numbers from the markup of an

empty cell.

Deﬁnition 2 (Preemptive Sets). A preemptive set

is composed of numbers from the set [1, 2, . . . , 9]

and is a set of size m, 2 ≤ m ≤ 9, whose numbers are potential occupants of m cells exclusively,

where exclusively means that no other numbers in

the set [1, 2, . . . , 9] other than the members of the

preemptive set are potential occupants...

Draw inspiration from millions of example essays and papers