Color Me Puzzled

My fondness for puzzles is well known. What is less well known, but probably more expected, is my total inability to solve the bloody things. Crosswords. Sudoku. Jumble. I work on them throughout the day, keeping a pencil handy and filling in a square everytime I walk by. I'm no Mark Nelson, but I do the best I can.

Which is one reason why, from time to time, puzzles like Sudoku have found their way into Dr. Dobb's in the guise of articles like Gigi Sayfan's Maven: Building Complex Systems or even in this space with post such as I'm Puzzled.

And it is the reason I found Agnes M. Herzberg and M. Ram Murty's paper Sudoku Squares and Chromatic Polynomials so interesting. In their paper, Herzberg and Murty turn to graph theory in systematically analyzing Sudoku puzzles. In the process, they also find that analyzing Sudokus leads to some unsolved problems in graph theory.

Of course, this is also a topic that Eytan Suchard, Raviv Yatom, and Eitan Shapir covered in their Dr. Dobb's Journal article Sudoku and Graph Theory.

In the context of Sudoku, a "graph" is a collection of nodes connected by line segments. Sudoku has 81 squares (nodes) in a 9x9 Sudoku puzzle (graph). The twist that Herzberg and Murty take is to identify each of the numbers 1-9 by a different color. In a Sudoku graph, two nodes are connected by a line segment if the two squares they represent are in the same row, column, or 3x3 subgrid. Since no row, column, or 3x3 subgrid can contain more than one instance of each number, the graph will have no connected nodes of the same color. (For example, suppose you represent 1 with red. Two red nodes connected with a line segment would mean a row, column, or 3x3 subgrid had two 1s in it, which is a no-no in Sudoku.)

According to the American Mathematical Society, in graph theory, a colored graph with no connections between same-colored nodes is called a "proper coloring." What Sudoku solvers do every day is try to extend a partially-colored graph (the original puzzle with open squares means the graph representing it has yet-to-be-colored nodes) to a proper coloring.

With this analogy between Sudoku puzzles and graphs, Herzberg and Murty use graph theory to prove theorems about Sudokus. For example, they prove that the number of ways of extending a partial coloring of a graph is given by a polynomial. If the value of this polynomial is zero for a given Sudoku puzzle, then the puzzle has no solution; if the value is 1, then the puzzle has only one solution; and so forth. They also prove that, in order for any Sudoku puzzle to have only one solution, at least 8 of the 9 numbers must appear as given entries in the puzzle; if only 7 numbers are given, then the puzzle has at least two solutions. And this brings up an unsolved mathematical question: "It would be extremely interesting to determine under what conditions a partial coloring can be extended to a unique [proper] coloring," Herzberg and Murty write.

Some Sudokus are harder than others, with the really difficult ones containing very few given entries. What is the minimum number of given entries needed to ensure that a puzzle has a unique solution" Herzberg and Murty give an example of a Sudoku puzzle with just 17 given entries that has only one solution. So the minimum number is at least 17. But could it be 16 -- or something even smaller. No one knows. You might think that a puzzle with many given entries is likelier to have a unique solution, but this is not necessarily the case they say. In their paper, they give an example of a puzzle with 29 given entries that actually has two different solutions.

Posted by Jon Erickson at 11:42 AM  Permalink