Paper: The Chaos within Sudoku

The Chaos within Sudoku” is a paper about solving Sudoku puzzles with physics. They simulate an imaginary physical system, let it run, and when it stops the puzzle is solved. See the video below:

The thing about Sudoku is that Sudoku is hard. More specifically, when Sudoku is generalized to grids of arbitrary size, it’s NP-complete. What happens when you translate an NP-complete problem to a physical simulation? The authors find chaotic dynamics.  And in the process, they identify the hardest Sudoku puzzle…

Here’s a rough outline of how Sudoku is translated to a physical system:

1. A sudoku puzzle is expressed as a series of true/false statements (e.g. “The fourth row, third column is a 9”), and a series of constraints (e.g. “The fourth row has exactly one 9”)
2. Each true/false statement, rather than being assigned true or false, is assigned a variable that moves continuously between -1 and 1.
3. Over time, each variable is pushed towards the value that satisfies the most constraints.
4. The weight of a constraint grows as the constraint spends longer unsatisfied.
5. Eventually, the variables settle, and the algorithm terminates.

The simulation is deterministic, but has sensitive dependence on initial conditions. The authors illustrate this by running the simulation with a range of different initial conditions:

Three color plots are shown, labeled t=10, t=15, and t=20. The different colors correspond to different digits between 1 and 9. The colors are in a fractal pattern that becomes more complex at t=15 and t=20.

Taken from Figure 3 of the paper.

The x- and y-axes of these plots are different initial conditions.  The color represents the dominant digit in a particular square at a particular time t.  As you can see, the dominant digit has fractal dependence on initial conditions, and the fractal is especially complex at t=20.

The probability that the algorithm has not solved the puzzle at time t follows the expression e^(-kt).  The exponent k is called the “escape rate”, I suppose because it measures the rate that the solver can escape from the fractal chaos.

The exponent k also gives an objective measure of the hardness of Sudoku.  The authors go through a bunch of Sudoku puzzles, and find that their objective measure correlates well to human estimates.  By far, the hardest puzzles they found were on Wikipedia, although they aren’t there anymore.  Wikipedia got the puzzles from this forum thread.

Now, I present to you, the hardest Sudoku puzzle, dubbed “Platinum Blonde”.  You’re welcome.

Platinum Blonde

Leave a Reply

Your email address will not be published. Required fields are marked *