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, η = −log10 κ 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.

• Publication year

  2012

• Venue

  Scientific Reports

• Publication date

  2012-08-01

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1038/srep00725arXiv 1208.0370PMID 23061008PMCID 3468838
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration

  2012cited by this paper
• Solving Single-Digit Sudoku Subproblems

  2012cited by this paper
• Taking Sudoku Seriously: The Math Behind the World's Most Popular Pencil Puzzle

  2012influential reference
• Optimization hardness as transient chaos in an analog approach to constraint satisfaction

  2011influential reference
• Transient Chaos: Complex Dynamics on Finite Time Scales

  2011influential reference
• Chaos: From Simple Models To Complex Systems

  2009cited by this paper
• The status of the P versus NP problem

  2009cited by this paper
• Constraint satisfaction problems with isolated solutions are hard

  2008cited by this paper
• Chaotic transients in spatially extended systems

  2008cited by this paper
• Locked constraint satisfaction problems.

  2008cited by this paper
• Searching with iterated maps

  2007influential reference
• An improved local search algorithm for 3-SAT

  2004cited by this paper
• An improved deterministic local search algorithm for 3-SAT

  2004cited by this paper
• Complexity and Completeness of Finding Another Solution and Its Application to Puzzles

  2003cited by this paper
• Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces (extended abstract)

  2000cited by this paper
• Statistical Mechanics, Three-Dimensionality and NP-Completeness: I. Universality of Intractability of the Partition Functions of the Ising Model Across Non-Planar Lattices

  2000influential reference
• Chaos in Dynamical Systems: Contents

  1993cited by this paper
• Escape from strange repellers.

  1984cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• On the computational complexity of Ising spin glass models

  1982cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper

• Correspondences in computational and dynamical complexity I

  2026cites this paper
• Project Patti: Why can You Solve Diabolical Puzzles on one Sudoku Website but not Easy Puzzles on another Sudoku Website?

  2025cites this paper
• Noise resilience of deterministic analog combinatorial optimization solvers

  2025cites this paper
• Handling Sudoku puzzles with irregular learning cellular automata

  2024cites this paper
• On the Emergence of Ergodic Dynamics in Unique Games

  2024cites this paper
• Surveying the space of descriptions of a composite system with machine learning

  2024cites this paper
• A Theory of Intelligences: Concepts, Models, Implications

  2023cites this paper
• Entropy as a Measure of Puzzle Difficulty

  2023cites this paper
• Using Entropy for Modeling Difficulty in the Asteroid Escape Sliding Puzzle

  2023cites this paper
• Puzzle-Mopsi: a location-puzzle game

  2022cites this paper
• Two faces of grit–perseverance: Is it always good to exert grit?

  2022cites this paper
• Projective Embedding of Dynamical Systems: uniform mean field equations

  2022cites this paper
• Genuinely quantum solutions of the game Sudoku and their cardinality

  2021cites this paper
• The Need to Visualize Sudoku

  2021cites this paper
• Accelerating numerical simulation of continuous-time Boolean satisfiability solver using discrete gradient

  2021cites this paper
• Global minimization via classical tunneling assisted by collective force field formation

  2021cites this paper
• Entropic herding

  2021cites this paper
• Genuinely quantum SudoQ and its cardinality

  2021cites this paper
• Timescales of Boolean satisfiability solver using continuous-time dynamical system

  2020cites this paper
• Accelerating a continuous-time analog SAT solver using GPUs

  2020cites this paper
• Coherent Ising machines—Quantum optics and neural network Perspectives

  2020cites this paper
• The New Cryptographic Method for Software and Hardware Protection of Communication Channels in Open Environments

  2020cites this paper
• A Continuous-time Dynamical System Solving the Satisfiability Problem

  2020cites this paper
• Coupled oscillators for computing: A review and perspective

  2020cites this paper
• BIBLIOGRAPHY

  2019cites this paper
• Perseverance in solving Sudoku: role of grit and cognitive flexibility in problem solving

  2019influential citation
• The Low-Dimensional Neural Architecture of Cognitive Complexity Is Related to Activity in Medial Thalamic Nuclei.

  2019cites this paper
• Planning Your Route: Where to Start?

  2018cites this paper
• Computational Red Teaming in a Sudoku Solving Context: Neural Network Based Skill Representation and Acquisition

  2018cites this paper
• Solving Constraint-Satisfaction Problems with Distributed Neocortical-Like Neuronal Networks

  2018cites this paper
• Solving Sudoku with Ant Colony Optimisation

  2018cites this paper
• Perspectives of Using Oscillators for Computing and Signal Processing

  2018cites this paper
• Problem Solving at the Edge of Chaos: Entropy, Puzzles and the Sudoku Freezing Transition

  2018cites this paper
• A continuous-time MaxSAT solver with high analog performance

  2018influential citation
• A high-performance analog Max-SAT solver and its application to Ramsey numbers

  2018influential citation
• An analog SAT solver based on a deterministic dynamical system: (Invited paper)

  2017cites this paper
• O-Mopsi

  2017cites this paper
• Sudoku Solver

  2017cites this paper
• Using Stochastic Spiking Neural Networks on SpiNNaker to Solve Constraint Satisfaction Problems

  2017influential citation
• Vertex coloring of graphs via phase dynamics of coupled oscillatory networks

  2016cites this paper
• Distributed Coordination for Nonsmooth Convex Optimization via Saddle-Point Dynamics

  2016cites this paper
• Solving odd even sudoku puzzles by binary integer linear programming

  2016cites this paper
• Efficient Analog Circuits for Boolean Satisfiability

  2016cites this paper
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems

  2016cites this paper
• Dissociation between mental fatigue and motivational state during prolonged mental activity

  2015cites this paper
• Reordering Variables using ‘Contribution Number' Strategy to Neutralize Sudoku Sets

  2015cites this paper
• The joy of transient chaos.

  2015cites this paper
• PuzzleJAR : Automated Constraint-based Generation of Puzzles of Varying Complexity

  2015cites this paper
• Scalable methods to integrate task knowledge with the Three-Weight Algorithm for hybrid cognitive processing via optimization

  2014cites this paper
• Solving Sudoku efficiently with Dancing Links

  2014cites this paper
• Asymmetric Continuous-Time Neural Networks without Local Traps for Solving Constraint Satisfaction Problems

  2013cites this paper
• Computing finite models using free Boolean generators

  2013cites this paper
• Agent-based Optimization of Advisory Strategy Parameters

  2013cites this paper
• An Improved Three-Weight Message-Passing Algorithm

  2013cites this paper
• Stochastic Computations in Cortical Microcircuit Models

  2013cites this paper
• Chaotic Boltzmann machines

  2013cites this paper
• On the Difficulty of Nonograms

  2012influential citation