Skip to Main content Skip to Navigation
Journal articles

A restarted estimation of distribution algorithm for solving sudoku puzzles

Sylvain Maire 1, 2 Cyril Prissette 3
1 MNC - Modélisation Numérique et Couplages
2 TOSCA - TO Simulate and CAlibrate stochastic models
CRISAM - Inria Sophia Antipolis - Méditerranée , IECL - Institut Élie Cartan de Lorraine : UMR7502
3 LSEET - Laboratoire de sondages électromagnétiques de l'environnement terrestre
Abstract : We describe a stochastic algorithm to solve sudoku puzzles. Our method consists in computing probabilities for each symbols 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 diffcult puzzles.
Keywords : Restart techniques Stochastic algorithms Estimation of distribution Sudoku puzzles Restart techniques.
Document type :
Journal articles
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
https://hal.inria.fr/inria-00591852
Contributor : Sylvain Maire <>
Submitted on : Tuesday, May 10, 2011 - 1:31:21 PM
Last modification on : Tuesday, May 18, 2021 - 2:32:02 PM
Long-term archiving on: : Friday, November 9, 2012 - 11:01:19 AM

File

Vignette du document
sudoku3.16_1_.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00591852, version 1

Collections

INSU | CNRS | INRIA | IECN | INSMI | LSEET | UNIV-LORRAINE | UNIV-TLN

Citation

Sylvain Maire, Cyril Prissette. A restarted estimation of distribution algorithm for solving sudoku puzzles. Statistics and Computing, Springer Verlag (Germany), 2012. ⟨inria-00591852⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

677

Files downloads

495

 

Contact                    Legal Notice                    Personal Data