The chaos within Sudoku.
The mathematical structure of Sudoku puzzles is akin to hard constraint satisfaction problems lying at the basis of many applications, including protein folding and the ground-state problem of glassy spin systems. Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by this system. We also show that the escape rate κ, an invariant of transient chaos, provides a scalar measure of the puzzle's hardness that correlates well with human difficulty ratings. Accordingly, η = -log₁₀κ can be used to define a "Richter"-type scale for puzzle hardness, with easy puzzles having 0 < η ≤ 1, medium ones 1 < η ≤ 2, hard with 2 < η ≤ 3 and ultra-hard with η > 3. To our best knowledge, there are no known puzzles with η > 4.
Faculty of Physics, Babeş-Bolyai University , Str. Kogalniceanu Nr. 1, RO-400084 Cluj-Napoca, Romania. ercsey.ravasz@phys.ubbcluj.ro
Mária
M
Ercsey-Ravasz
Zoltán
Z
Toroczkai
D000465:Algorithms; D006801:Humans; D017711:Nonlinear Dynamics; D010988:Play and Playthings