English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Sudoku is a widely popular $\mathcal{NP}$-Complete combinatorial puzzle whoseprospects for studying human computation have recently received attention, butthe algorithmic hardness of Sudoku solving is yet largely unexplored. In thispaper, we study the statistical mechanical properties of random Sudoku grids,showing that puzzles of varying sizes attain a hardness peak associated with acritical behavior in the constrainedness of random instances. In doing so, weprovide the first description of a Sudoku \emph{freezing} transition, showingthat the fraction of backbone variables undergoes a phase transition as thedensity of pre-filled cells is calibrated. We also uncover a variety ofcritical phenomena in the applicability of Sudoku elimination strategies,providing explanations as to why puzzles become boring outside the typicalrange of clue densities adopted by Sudoku publishers. We further show that theconstrainedness of Sudoku puzzles can be understood in terms of theinformational (Shannon) entropy of their solutions, which only increases up tothe critical point where variables become frozen. Our findings shed light onthe nature of the $k$-coloring transition when the graph topology is fixed, andare an invitation to the study of phase transition phenomena in problemsdefined over \emph{alldifferent} constraints. They also suggest advantages tostudying the statistical mechanics of popular $\mathcal{NP}$-Hard puzzles,which can both aid the design of hard instances and help understand thedifficulty of human problem solving.

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