“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:
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:
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.
Leave a Reply