publication . Preprint . 2013

Difficult Sudoku Puzzles Created by Replica Exchange Monte Carlo Method

Watanabe, Hiroshi;
Open Access English
  • Published: 08 Mar 2013
Abstract
An algorithm to create difficult Sudoku puzzles is proposed. An Ising spin-glass like Hamiltonian describing difficulty of puzzles is defined, and difficult puzzles are created by minimizing the energy of the Hamiltonian. We adopt the replica exchange Monte Carlo method with simultaneous temperature adjustments to search lower energy states efficiently, and we succeed in creating a puzzle which is the world hardest ever created in our definition, to our best knowledge. (Added on Mar. 11, the created puzzle can be solved easily by hand. Our definition of the difficulty is inappropriate.)
Subjects
ACM Computing Classification System: MathematicsofComputing_GENERAL
free text keywords: Condensed Matter - Statistical Mechanics
Download from

H. Teller, and E. Teller, J. Chem. Phys. 21, 1087 (1953). [10] K. Hukushima and K. Nemoto, J. Phys. Soc. Jpn, 65,

1604 (1996). [11] R. H. Swendsen and J.-S. Wang, Phys. Rev. Lett. 57,

2607 (1986). [12] W. Kerler and P. Rehberg, Phys. Rev. E 50, 4220 (1994). [13] H. Nishimori and J. Inoue, J. Phys. A 31 5661 (1998). [14] https://github.com/kaityo256/sudoku/

Abstract
An algorithm to create difficult Sudoku puzzles is proposed. An Ising spin-glass like Hamiltonian describing difficulty of puzzles is defined, and difficult puzzles are created by minimizing the energy of the Hamiltonian. We adopt the replica exchange Monte Carlo method with simultaneous temperature adjustments to search lower energy states efficiently, and we succeed in creating a puzzle which is the world hardest ever created in our definition, to our best knowledge. (Added on Mar. 11, the created puzzle can be solved easily by hand. Our definition of the difficulty is inappropriate.)
Subjects
ACM Computing Classification System: MathematicsofComputing_GENERAL
free text keywords: Condensed Matter - Statistical Mechanics
Download from

H. Teller, and E. Teller, J. Chem. Phys. 21, 1087 (1953). [10] K. Hukushima and K. Nemoto, J. Phys. Soc. Jpn, 65,

1604 (1996). [11] R. H. Swendsen and J.-S. Wang, Phys. Rev. Lett. 57,

2607 (1986). [12] W. Kerler and P. Rehberg, Phys. Rev. E 50, 4220 (1994). [13] H. Nishimori and J. Inoue, J. Phys. A 31 5661 (1998). [14] https://github.com/kaityo256/sudoku/

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue