Crook’s pencil-and-paper algorithm

You probably noticed in the previous activity that there are indeed Sudokus that cannot be solved using method 2 or 3.  James Crook, professor emiritus of Computer Science at Winthrop University, came up with an algorithm that will solve any Sudoku puzzle, and can be done on paper. The following discussion is in part adapted from his paper “A Pencil-and-Paper Algortihm for Solving Sudoku Puzzles”, which is available at http://www.ams.org/notices/200904/rtx090400460p.pdf.

Crook uses a hybrid approach, which is a sophistated combination of our simple solving algorithm, the place-finding method, the candidate-checking method, and the method of preemptive sets, which we will learn about in a minute. Remember that the candidate-checking and place-finding methods are nice and fast, but sometimes fail. Our simple solving algorithm can solve everything, but is not very easy to do for humans, because there are so many combinations to check. Crook’s method of preemptive sets reduces the number of combinations in a clever way.

Mark-ups will help be an important tool in our algorithm. We will often write the mark-up in small print in the bottom right corner of a cell. 

Let’s think again about the simple solving algorithm worked: for each cell, we entered numbers between 1 and 9 into cells cell by cell. If we found that our choices violated the Sudoku condition, we erased one or more numbers, entered new numbers and tried again. As a result, there were many situations where we tried a lot of numbers which all lead to violations, before finding the correct one. In an improved version of the simple solving algorithm, one could first mark up the puzzle, and then for each cell not try numbers 1 to 9 in increasing order, but only the numbers from the markup: this means that there are fewer checks to do, thus less work. Here is another modification: first use the candidate-checking and place-finding methods on the puzzle, then mark it up, and finally use the simple solving algorithm to deal with whatever could not be solved using the other methods. This is, in part, what Crook’s algorithm does.

To refer to cells, Crook uses a notation where for example c(2,1) refers to the cell in row 2 from the top, column 1 from the left. He denotes preemptive sets by first listing the numbers belonging to it, and then the cells that they might occupy: For example, {[4,7], [c(2,1),c(2,9)]} refers to the preemptive set consisting of the numbers 4 and 7 lie in the cells c(2,1) and c(2,9).

Here is an easy-to-prove but extremely useful theorem about preemptive sets:

Suppose that we are solving a Sudoku puzzle and have discovered a preemptive set. If the preemptive set lies completely within one column (or row, or 3x3 box), then the occupancy theorem allows us to cross out any numbers that appear in the preemptive set from the markups of cells outside of preemptive sets in that column (or row, or 3x3 box). We now have three methods of working towards solutions of Sudoku puzzles that work well on paper: methods 1 and 2, and the method of preemptive sets, which helps allows us to cross numbers out in the markups of cells.

We can now state Crook’s algorithm for solving Sudoku puzzles on paper:

Crook’s algorithm in an example

To illustrate the algorithm, we will solve the below (difficult) Sudoku, which Crook discusses in his paper. The puzzle itself is from the book “Solving Sudoku” by Michael Mepham (see References).

After steps 1 and 2 of the algorithm, the Sudoku board looks as follows:

In part 3 of the algorithm, we immediately find the preemptive set {[4,7], [c(2,1),c(2,9)]}. By the occupancy theorem, we may eliminate 4 and  from the markups of all cells in the top-right 3x3 box. This exposes the 9 as the only candidate for cell c(2,7), so we enter the 9.

Continuing to look for preemptive sets, we find the preemptive set {[2,4,9],[c(4,4),c(4,6),c(4,7)]}, and after removing the respective numbers from the markups in row 4, we find the preemptive set {[1,3,8],[c(4,1),c(4,2),c(4,8)]}.

Looking over the board one more time, we see that there are no other preemptive sets, and that methods 2 and 3 would not allow us to enter any further numbers into cells either. We thus move on to step 5 of the algorithm.

At this point, it is a good idea to copy the entire Sudoku board with the markup and continue working on a separate sheet of paper. When choosing a cell to enter a number from its markup, it is usually best to choose a cell with a markup consisting of as few numbers as possible (why, and what is the exception to this rule?). In our case there are several cells with a markup consisting of 2 numbered. For instance, we could enter a 7 into c(2,1) using a red pen.

In step 6 of the algorithm, we use methods 2 and 3 to enter the numbers 7,4,4,8 and 8 into the cells c(2,1, c(3,2), c(2,9), c(6,2), and c(7,9) respectively. At this point we get a violation of the Sudoku condition, since the middle 3x3 box on the right cannot contain the number 8. As a result, we erase everything we worked out in red, erase 7 from the markup of c(2,1) and proceed to step 5. (In practice, it is probably easier to copy the state of the puzzle before we started using red onto a new sheet of paper.)

In step 5, we observe that the markup of cell c(2,1) now only contains one number, so we choose this cell and enter 4. In step 6, we write 7 into cells c(3,2) and c(2,9). We are now unable to find any further preemptive sets or make progress with methods 2 or 3, so we go back to step 5.

This time, we choose cell c(9,8) and enter the number 4 from its markup in green color. This time we are lucky: the use of methods 2 and 3, as well as the method of preemptive pairs, will solve the puzzle for us in step 6 of the algorithm. One way of completing the puzzle is as follows:

cell            entry

c(7,8)        8

c(8,9)        4

c(8,3)        8

c(6,9)        8

c(4,2)        4

c(2,9)        7

c(2,1)        4

c(3,2)        7

c(7,2)        6

c(7,3)        3

c(7,1)        7

c(8,5)        7

c(9,5)        3

c(6,2)        4

c(5,2)        1

c(5,1)        6

c(4,1)        3  (using the preemptive pair {[1,3],[c(1,9),c(3,9)]})

c(6,8)        3

c(1,5)        4

c(7,9)        5

c(3,8)        4       

c(3,7)        5

c(5,8)        9

c(4,8)        1

c(5,7)        4

c(5,3)        2

c(4,7)        2

c(6,4)        2

c(7,6)        4

c(4,6)        9

c(4,4)        4

c(7,5)        2

c(3,5)        9

c(3,4)        1

c(1,6)        3

c(3,6)        2

c(1,9)        1

c(3,9)        3

c(8,6)        1

c(9,4)        9

c(9,1)        1

c(8,1)        9

We have thus found the following solution for the puzzle: