Sudoku Proves to Be Good for You, Mathematically Speaking

June 22, 2007

Sudoku fans Ram Murty and Agnes M. Herzberg—both mathematicians at Queen's University in Kingston, Ontario—have examined the popular puzzle from a mathematical perspective. They find "beautiful" connections between sudoku and areas of mathematics such as graph theory, number theory, probability, and statistics. They also claim that solving sudoku puzzles helps improve people's math skills.

In their paper "Sudoku Squares and Chromatic Polynomials," published in the June/July Notices of the American Mathematical Society, the authors interpret the nine-by-nine puzzle as a graph-coloring problem.

In this context, a graph is a collection of points (nodes or vertices) connected by lines (edges). Each of the 81 squares of a sudoku puzzle can be represented by a point in a graph. A line connects two points if the two squares that they represent are in the same row, column, or three-by-three subgrid. If each number has a different color, a correct sudoku graph would contain no connected points of the same color, resulting in a proper coloring. The chromatic number is the smallest number of colors needed to color a graph so that no two adjacent vertices share the same color. Solving a sudoku puzzle is equivalent to finding a proper coloring for a partially colored graph.

By analyzing sudoku in terms of graph coloring, Murty and Herzberg provide answers to a number of questions about the puzzle. For instance, they prove that at least eight of the nine different numbers must appear as entries for a puzzle to have a unique solution. But they can't prove that a puzzle with fewer than 17 given entries can have a unique solution. At the same time, the mathematicians show that, taking symmetries into account, there are only 5,472,730,538 essentially different sudoku grids.

Murty and Herzberg suggest that the mathematical theory underlying sudoku can be used in a wide variety of applications, including the analysis of complex communications networks and airline schedules.

And, Murty told the Kingston Whig-Standard, "There are some logical skills that people are unlocking when they're solving a sudoku puzzle."

"Everyone has an innate mathematical ability," Murty said. "It just has to be brought out, and in some way sudoku does that."

Source: Kingston Whig-Standard, June 12, 2007; American Mathematical Society, June 8, 2007; Queen's University, June 8, 2007