A restarted estimation of distribution algorithm for solving sudoku puzzles

Maire Sylvain () and Prissette Cyril ()
Additional contact information
Maire Sylvain: Laboratoire des Sciences de l'Information et des Systemes (LSIS), UMR6168, ISITV, Universite de Toulon et du Var, Avenue G. Pompidou, BP 56, 83262 La Valette du Var cedex, France
Prissette Cyril: Laboratoire des Sciences de l'Information et des Systemes (LSIS), UMR6168, ISITV, Universite de Toulon et du Var, Avenue G. Pompidou, BP 56, 83262 La Valette du Var cedex, France

Monte Carlo Methods and Applications, 2012, vol. 18, issue 2, 147-160

Abstract: In this paper, we describe a stochastic algorithm to solve sudoku puzzles. Our method consists in computing probabilities for each symbol of each cell updated at each step of the algorithm using estimation of distributions algorithms (EDA). This update is done using the empirical estimators of these probabilities for a fraction of the best puzzles according to a cost function. We develop also some partial restart techniques in the RESEDA algorithm to obtain a convergence for the most difficult puzzles. Our algorithm is tested numerically on puzzles with various levels of difficulty starting from very easy ones to very hard ones including the famous puzzle AI Escargot. The CPU times vary from few hundreds of a second for the easy ones to about one minute for the most difficult one.

Keywords: Stochastic algorithms; estimation of distribution; sudoku puzzles; restart techniques (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma-2012-0004 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:18:y:2012:i:2:p:147-160:n:3

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/mcma-2012-0004

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().