Struggling to solve today's sudoku? Is your tried and tested method hitting a brick wall and you feel like you are going around in circles? Then new research from Nature Scientific Reports might make you feel a bit better. You might not necessarily be stuck... perhaps you are just in a patch of transient chaos on your way to the solution.

A sudoku is a 9x9 grid with some digits (1 through to 9) already filling some of the squares of the grid. From these clues you need to fill in the rest of the squares so that the digits 1 through to 9 appear exactly once in each row, column and 3x3 subblock (as marked by the bold lines) of the grid. Although it might not seem like it, properly set sudokus always have a solution and a unique solution at that.

One way of solving these puzzles is using brute force – you try every combination of the digits 1 though to 9 in the squares until you find one that satisfies these constraints – however this could take an extraordinarily long time. Zoltán Toroczkai from the University of Notre Dame, USA, gave us some estimates based on an easy example and a hard example of sudokus: "Such brute force search would take on Sequoia (the best supercomputer currently available) approximately 10⁵ seconds, or about 27 hours, for the easy puzzle. And for the hard puzzle [the brute force search would take] approximately 10²⁷ seconds, or about 2.7x10²³ hours or about 3x10¹⁹ years." The amount of time this method would take to solve the hard puzzle is significantly longer than the age of the universe (estimated to about 1.3x10¹⁰ years)!

Toroczkai and his colleague Mária Ercsey-Ravasz have found a much quicker method that always finds the solution to a sudoku. But what is particularly interesting about their method is that on the way to the solution, their algorithm can go through a period of chaotic behaviour and the length of this chaotic period is a strong indicator of the hardness of the sudoku in question. Moreover, this mathematical measure of hardness closely agrees with our intuitive human perception of the puzzle's hardness.

Ercsey-Ravasz and Toroczkai say that the mathematical structure of sudoku puzzles is akin to the problems lying at the basis of many applications, including protein folding and statistical mechanics. This mathematical structure is revealed by reimagining the puzzle as a series of constraints involving boolean (true or false) variables.

Sudoku and its boolean representation: (a) a typical puzzle with bold digits as clues; (b) the setup of the boolean representation in a 9x9x9 grid; (c) layer L₄ of the puzzle (the one containing the digit 4) with 1s in the location of the clues and the regions that cannot be the digit 4 as they are blocked out by the presence of the clues (shaded area).

Suppose you are given a sudoku with its initial clues (image (a) above). Imagine a tower nine cells high sitting on the right-top square which has been filled with a 4 as one of the clues (image (b) above). Then this tower has a 0 in every cell except for the 4th cell up, which is marked with a 1. The nine cells in a tower represent a boolean expression for the value of the square: 0 for all the digits that are not the value of the square and 1 for the digit (represented by the 4th level in the tower) that is the value of the square.

Now imagine these 9-cell-high towers sitting on each square of the sudoku, filled with 0s and 1s according to the clues we've been given. You can now see layers in this 9x9x9 block which represent all the locations of a particular digit. So the fourth layer (image (c) above) gives all the information so far we have for the position of the 4's in the puzzle, showing 1s in the three locations given as clues. This layer also shows all the 0s that result from the constraints of the puzzle: if there is a 4 in the first row (shown as a 1 in the top right of layer 4) then the rest of the cells in the first row in this layer must be 0 as each digit appears exactly once in each row. Similarly for the other cells in the ninth column in this layer and the top right subblock in this layer.

In this way a sudoku can be described as a something called a +1-in-9-SAT type constraint satisfication problem: a problem where a series of boolean constraints (where exactly 1 out of 9 variables must be true in each constraint) must be satisfied. Ercsey-Ravasz and Toroczkai have developed an algorithm for solving a more generalised version of this problem that, for every empty square in the sudoku, assigns something called a spin, s_a, for each possible digit a=1,...,9. Starting from some randomly chosen values of the spins (which can take a value from -1 to +1), the algorithm uses differential equations expressing the constraints of the problem to continuously alter the values of the spins. "The dynamics [of the system of differential equations] ultimately drives one of the spin variables to +1, and the rest to -1, corresponding to the boolean formulation of the solution," says Toroczkai.

Not only does their algorithm always find the solution of the sudoku, it also gives a fascinating glimpse into how hard the puzzle was to solve. The algorithm produces a period of chaotic behaviour in the values of the spins for each square. As there is always a solution this chaotic period is always transient but the length of this chaotic period gives a mathematical measure of the hardness of the problem. This mathematical measure of the hardness of the problem closely agrees with our intuitive human assessment of the hardness of these sudoku puzzles, as indicated by the grading (eg hard, easy, killer) given by the puzzle setters.

Sudokus are a specific instance of something called an NP problem (technically speaking, a sudoku is an exact cover type constraint satisfaction problem, and when generalised to an N X N grid is one of Karp's 21 NP-complete problems). Sudokus give a nice illustration of what characterises these NP problems: we don't have an easy way to find a solution but we can easily check if a given answer is correct. Although Ercsey-Ravasz and Toroczkai's algorithm will always find the solution for a 9x9 sudoku within a reasonable amount of time (just a few seconds), the time the algorithm would take would quickly spiral out of control if we increased the size of the grid. (You can read more about NP and NP-complete problems in The travelling salesman.)

As we have no easy ways to solve NP problems, and there may indeed never be a quick way to solve these problems (unless someone does prove that P=NP), knowing how hard these problems are may be the next best thing. And Ercsey-Ravasz and Toroczkai's use of chaos theory methods might help us understand how hard it is to solve problems in computational biology and statistical physics, as well as how many cups of tea it might take to solve today's sudoku.

On the 20th of November 2012 the Centre for Mathematical Sciences in Cambridge will be hosting the first UK screening of Travelling Salesman, an intellectual thriller imagining the consequences of solving the P vs NP problem (which would be much more serious than just solving sudoku quickly!). You can buy tickets here and read our recent article to find out what this problem is all about.