Today on MadisonOnline

Puzzling over Sudoku

Explaining -- and expanding on -- the pop-culture phenomenon

By Laura Taalman, Ph.D.
Condensed from the article in Fall 2007 Madison

18-clue Sudoku puzzle

18-clue puzzles in Sudoku books can be quite difficult. If you're up to a challenge, try this puzzle. Each row, column, and block must contain 1 to 9 exactly once. For the solution, click here.

America has been taken over by little 9 by 9 grids full of numbers. Sudoku puzzles are now a regular feature in almost every newspaper, and bookstores devote entire sections to Sudoku books. But, we're late to the party; Sudoku has been popular since the '80s in Japan after its first appearance in print in an American puzzle magazine in 1979. The roots of Sudoku are even older, dating back to Latin squares and magic squares, which have been studied for hundreds of years.

In case you've missed the phenomenon, here is how Sudoku puzzles work: each puzzle is a 9 by 9 grid with some numbers filled in, and your job is to fill in the rest of the grid so that every row, column and 3 by 3 block contains each of the whole numbers from 1 to 9 exactly once. Sudoku puzzles are always constructed so that there is only one possible way to fill in the grid. Many puzzle authors also impose the condition that the set of cells in which the initial clues appear has 180-degree rotational symmetry. This means that if you rotate the puzzle 180 degrees, the cells with clues appear in the same locations. This symmetry convention is also followed in the black squares of most crossword puzzles. Although this symmetry does not add anything to the experience of playing the puzzle, it does make the puzzles more pleasing to the eye.

One of the most basic questions that can be asked about Sudoku puzzles is an unsolved problem: how many clues are needed to guarantee a unique solution? Mathematicians and computer scientists have conjectured that at least 17 clues are always needed. Although there are many known 17-clue puzzles and no known 16-clue Sudoku puzzles, it is still an open problem to prove that no 16-clue puzzles exist. When the rotational symmetry condition is imposed, the conjectured number jumps to 18; no 17-clue rotationally symmetric Sudoku puzzles have yet been found. You won't usually see 18-clue puzzles in Sudoku books, because they can be quite difficult. If you were up to the challenge and tried the puzzle above, check your results with the solution.

Rating the difficulty level

Although puzzles with fewer clues tend to be more difficult than puzzles with more clues, the number of clues alone does not determine the difficulty of a Sudoku puzzle. Because difficulty level is subjective, it is hard to accurately rate Sudoku puzzles. Different puzzle makers will use different methods to rate their puzzles, usually using computer programs written for that purpose. Some puzzle rating programs apply well-known human solving techniques to a puzzle and keep track of the complexity of techniques required to solve the puzzle. This method of rating works well if the people later playing the puzzle tend to use the same solving techniques used by the computer program. If you've ever played a supposedly easy-rated puzzle and found it very challenging (or vice-versa), it may be that you do not usually use the same solving techniques used by the rating program.

A more objective way of rating puzzles, developed by JMU alumnus Philip Riley ('02M), is to have a computer play a particular puzzle thousands of times in thousands of different ways and keep a running average of the time and number of steps required to solve the puzzle. This is in fact how the puzzles in this article were rated. However, since the puzzles are not all of the same type, you still might find some puzzles inherently harder than others. One-star puzzles are meant to be very easy, and five-star puzzles should keep you awake at night.

The James Madison Sudoku puzzle

Each row, column, and jigsaw region must must contain exactly the letters that appear in "JAMES MADISON." Notice that the letters A, M and S will appear twice in every row, column and region.

Arithmetic, no. Mathematics, yes.

Newspapers that run Sudoku puzzles often reassure their readers that although the puzzles involve numbers, they do not require any mathematics. What they really mean is that Sudoku does not require any arithmetic. We do not need to worry about the numerical properties of the numbers in the puzzle. However, the heart of mathematics is not numbers and arithmetic, but rather reasoning and logic. In this sense, Sudoku puzzles are entirely about mathematics.

How are Sudoku puzzles made?

So where do Sudoku puzzles come from? The puzzles in most Sudoku books sold in the United States are generated by computer, sometimes by starting with a completed grid and removing entries one by one, and sometimes by starting with a blank grid and adding entries one by one, at each step checking to see if the puzzle has a unique solution. There are Japanese puzzle companies that make all of their wonderful puzzles entirely by hand. The puzzles in this article were made by myself and Philip Riley, together known as Brainfreeze Puzzles. We make "cyborg" puzzles, meaning that we use computers for the tedious parts of the process but design and build each puzzle individually by hand. The "James Madison Sudoku" puzzle was made especially for Madison magazine readers.

About the author

Mathematics professor Laura Taalman earned her Ph.D. in mathematics from Duke University and completed undergraduate work at the University of Chicago. Her research includes singular algebraic geometry, knot theory and the mathematics of Sudoku and other puzzles. She has written a textbook that combines calculus, pre-calculus, and algebra into one course; and she is one of the organizers of the Shenandoah Undergraduate Mathematics and Statistics Conference at JMU. The Mathematical Association of America has honored her with the Trevor Evans Award and the Alder Award for Distinguished Teaching.

Download the PDFs for the full version of this feature and all of Fall 2007 Madison."Puzzling over Sudoku" begins on Page 57.
Click here to subscribe to Madison.