Have you ever been trying to solve a Sudoku puzzle and been gripped by a sinking feeling that maybe you were stuck with a lemon? That maybe the puzzle you are struggling with actually has no solution at all? And, if you do find a solution, how can you be sure it's the only one? What if half an hour ago you had written 5 instead of 3 — would you then have gone down a path to a completely different solution?

Feel like giving up? Try some graph theory.

These questions and others are explored in the article Sudoku squares and chromatic polynomials, by Agnes M. Herzberg and M. Ram Murty, which appears in the June/July 2007 issue of the Notices of the American Mathematical Society. The authors use tools from a branch of mathematics called graph theory to systematically analyse Sudoku puzzles, and find that Sudoku leads to some unsolved problems in graph theory.

In this context a graph is a collection of nodes connected by line segments. We can think of the 81 squares in a Sudoku puzzle as 81 nodes in a graph. We will also represent each of the numbers one through nine by a different colour. 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 3 by 3 subgrid. Since no row, column, or 3 by 3 subgrid can contain more than one instance of each number, the graph will have no connected nodes of the same colour. For example, suppose we represent 1 with red. Two red nodes connected with a line segment would mean a row, column, or 3 by 3 subgrid had two 1s in it, which is forbidden in Sudoku.

In the language of graph theory, a colouring of a graph with no connections between same-coloured nodes is a called a proper colouring. What Sudoku solvers do every day is try to extend a partially-coloured graph (the original puzzle with open squares means the graph representing it has yet-to-be-coloured nodes) to a proper colouring.

With this analogy between Sudoku puzzles and graphs in place, Herzberg and Murty were able to use tools from graph theory to prove theorems about Sudokus. For example, they prove that the number of ways of extending a partial colouring of a graph is given by a polynomial, that is an expression of the form

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 colouring can be extended to a unique [proper] colouring," 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 most 17. But could it be 16 — or something even smaller? No one knows. One might think that a puzzle with many given entries is likelier to have a unique solution, but this is not necessarily the case. The article gives an example of a puzzle with 29 given entries that actually has two different solutions.

And if you have been worrying that your newspaper will run out of Sudoku puzzles some time soon, you can relax: the authors argue that the number of distinct Sudoku puzzles is somewhere around 5.5 billion — enough to keep Sudoku afficianados busy for a long time to come.

Further reading

• The article Sudoku squares and chromatic polynomials is available on the web site of the AMS Notices;
• Read about the history of Sudoku in the Plus article Anything but square: from magic squares to Sudoku;
• Find out more about the connections between Sudoku and other fields in the Plus article Forget Sudoku and smile for the camera;
• Plus is currently running a series of Sudoku-like puzzles. The first three appeared in Issue 43, Issue 42 and Issue 41, and there will be another one in Issue 44 due out in September;
• If you're into puzzles, read our recent news story on the Rubik cube;
• Find all our articles on graph theory in the Plus archive.