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
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;
Conference_Titel :
Adaptive Science & Technology (ICAST), 2014 IEEE 6th International Conference on
DOI :
10.1109/ICASTECH.2014.7068127
