DocumentCode
3582095
Title
Solving sudokus via metaheuristics and AC3
Author
Soto, Ricardo ; Crawford, Broderick ; Galleguillos, Cristian ; Misra, Sanjay ; Olguin, Eduardo
Author_Institution
Pontificia Univ. Catolica de Valparaiso, Valparaiso, Chile
fYear
2014
Firstpage
1
Lastpage
3
Abstract
The Sudoku puzzle consists in filling a square matrix with 9 rows and 9 columns, divided into 9 3×3 regions, so that each column, row, and region contains different digits from 1 to 9. Such a puzzle belongs to the NP-complete class of problems, existing different exact and approximate methods able to solve it. This paper reports recent results for solving Sudokus achieved by combining metaheuristics and a filtering technique coming from the constraint programming domain named AC3.
Keywords
computational complexity; constraint handling; optimisation; AC3; NP-complete class; Sudoku puzzle; approximate methods; constraint programming domain; filtering technique; metaheuristics; square matrix; Electronic mail; Genetic algorithms; IEEE Computer Society; Particle swarm optimization; Programming; Search problems; Arc-consistency; Constraint Satisfaction; Sudoku;
fLanguage
English
Publisher
ieee
Conference_Titel
Adaptive Science & Technology (ICAST), 2014 IEEE 6th International Conference on
Type
conf
DOI
10.1109/ICASTECH.2014.7068127
Filename
7068127
Link To Document