Problem Solving at the Edge of Chaos: Entropy, Puzzles and the Sudoku Freezing Transition

Sudoku is a widely popular NP-Complete combinatorial puzzle whose prospects for studying human computation have recently received attention, but the algorithmic hardness of Sudoku solving is yet largely unexplored. In this paper, we study the statistical mechanical properties of random Sudoku grids, showing that puzzles of varying sizes attain a hardness peak associated with a critical behavior in the constrainedness of random instances. In doing so, we provide the first description of a Sudoku freezing transition, showing that the fraction of backbone variables undergoes a phase transition as the density of pre-filled cells is calibrated. We also uncover a variety of critical phenomena in the applicability of Sudoku elimination strategies, providing explanations as to why puzzles become boring outside the typical range of clue densities adopted by Sudoku publishers. We further show that the constrainedness of Sudoku puzzles can be understood in terms of the informational (Shannon) entropy of their solutions, which only increases up to the critical point where variables become frozen. Our findings shed light on the nature of the k-coloring transition when the graph topology is fixed, and are an invitation to the study of phase transition phenomena in problems defined over alldifferent constraints. They also suggest advantages to studying the statistical mechanics of popular NP-Hard puzzles, which can both aid the design of hard instances and help understand the difficulty of human problem solving.

I. Introduction

Sudoku is a combinatorial puzzle whose origins trace back to Leonhard Euler's work with Latin Squares [13], but which has achieved unprecedented worldwide popularity in the last decade. Dubbed “the Rubik's cube of the 21th century” [25], the Sudoku phenomenon has sparked a number of mathematical and scientific studies, including using the structure of the puzzle to perform both traditional and quantum cryptography [6], [14], [15] and devise cytometry devices [33]. The constraints of Sudoku puzzles have also been harnessed to successfully generate the first demonstration of non-Markovian light, by imprinting overlapping Sudoku solutions on spatial light modulators [8]. Perhaps most interestingly, due to their popularity and -Hardness [34] Sudoku puzzles have found a niche in the interdisciplinary study of human learning and problem solving. Leu and Abbas [16] use Sudoku to study human problem-solving skills and their acquisition, representing them in a cognitively plausible manner with neural networks. The puzzle has also been used as a benchmark for collaborative problem-solving on social networks on more than one occasion [10], [31], and for working memory in cognitive processing on at least one [17]. Apart from mathematical results such as the minimum necessary number of clues to ensure solution uniqueness or the properties of the Sudoku symmetry group [2], [20], the Sudoku fever has sparked developments and insightful analogies in the social [11] and physical sciences [9], [32].