Paramagnetic and glass transitions in sudoku
Senior Honours student Alex Williams' project has been published in leading journal Physical Review.
His paper "Paramagnetic and glass transitions in sudoku" involved a study of the statistical mechanics of a model glassy system based on sudoku. Defining an energy and temperature based on the number of errors on a sudoku grid, Alex used methods devised at Los Alamos in the Manhattan project to reveal similarities between properties of sudoku puzzles and magnetic systems.
The “sudoku Hamiltonian” exhibits two transitions as a function of temperature: a paramagnetic and a glass transition. Of these, both transitions are associated with an entropy change. Paramagnetism measured from the dynamics of the Monte Carlo run shows a peak in specific heat, while the residual glass entropy is determined by finding multiple instances of the glass by repeated annealing.
There are relatively few such simple models for frustrated or glassy systems that exhibit both ordering and glass transitions; sudoku puzzles are unique for the ease with which they can be obtained, with the proof of the existence of a unique ground state via the satisfiability of all constraints. Simulations suggest that in the glass phase there is an increase in information entropy with lowering temperature. In fact, we have shown that sudoku puzzles have the type of rugged energy landscape with multiple minima that typifies glasses in many physical systems.
Alex's code also solves sudoku puzzles.