Perhaps inevitably, sudoku puzzles are showing up in the mathematics classroom. Although these extremely popular puzzles don’t involve even arithmetic, they’re wonderful exercises in logic—and lend themselves to illuminating excursions into such mathematical topics as combinatorics, Latin squares, polyominoes, computer algorithms, chess problems, graph colorings, and permutation group theory.
This year’s Joint Mathematics Meetings (JMM) in New Orleans provided evidence of this interest in the form of a two-part session devoted to sudoku and other puzzles, organized by Laura Taalman of James Madison University.
Although Taalman has described sudoku as “muggle math,” she finds the puzzles endlessly fascinating and has created entertaining sudoku variants. In “snowflake” sudoku, for example, the numbers from 1 to 9 are filled in so that no number is repeated in any row, column, block, or various diagonals. In color variants, the usual sudoku rules apply, but no number can appear more than once with any color.
Some of these variants can be seen at her “Brainfreeze Puzzles” Web site at http://www.brainfreezepuzzles.com/, with a book, Color Sudoku, on the way.
There are lots of open mathematical problems associated with sudoku, many of which lend themselves to undergraduate research projects, Taalman says.
At this stage in the sudoku craze, many people have written computer programs to solve and create sudoku puzzles. Science fair projects have sought insights into this addictive pastime, addressing such questions as what criteria determine how difficult a given puzzle may be.
Mathematician Jonathan M. Kane of the University of Wisconsin-Whitewater, for example, first learned about sudoku in the summer of 2005 when he and his wife were on a trip to Europe and noticed someone reading Sudoku for Dummies. By the end of the year, he had created software for solving puzzles and generating new ones, which he called “Sudoku Studio.” Users can input puzzles from any source and solve them using the program or work on puzzles generated by the program.
At the JMM, Kane provided some insights into the reasoning that went into his puzzle solver and generator.
Kane’s sudoku solver begins by constructing the set of all values that can be entered in each unfilled square. It then fills in any squares for which an available set has only one element. Then, if a value appears in only one available set for a row, column, or block, those squares are filled in. And so on. The program solves any puzzle that has at least one solution in a fraction of a second.
To generate a puzzle, Kane’s software starts with a completely filled grid, then removes numbers until the puzzle has the desired degree of difficulty, as measured by how many rules must be applied to solve the resulting puzzle.
Given that the available number of standard sudoku puzzles (nine-by-nine grid with three-by-three blocks) is 6,670,903,752,021,072,936,960, there’s plenty of material to work with for a long time to come.
If you would like to comment on this article, see the MathTrek blog version.
