A hybrid AC3-tabu search algorithm for solving Sudoku puzzles
Autor
Soto R.
Crawford B.
Galleguillos C.
Monfroy E.
Paredes F.
Resumen
The Sudoku problem consists in filling a n2×n2 grid so that each column, row and each one of the n×n sub-grids contain different digits from 1 to n2. This is a non-trivial problem, known to be NP-complete. The literature reports different incomplete search methods devoted to tackle this problem, genetic computing being the one exhibiting the best results. In this paper, we propose a new hybrid AC3-tabu search algorithm for Sudoku problems. We merge a classic tabu search procedure with an arc-consistency 3 (AC3) algorithm in order to effectively reduce the combinatorial space. The role of AC3 here is do not only acting as a single pre-processing phase, but as a fully integrated procedure that applies at every iteration of the tabu search. This integration leads to a more effective domain filtering and therefore to a faster resolution process. We illustrate experimental evaluations where our approach outperforms the best results reported by using incomplete search methods. © 2013 Elsevier Ltd. All rights reserved.
Colecciones
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Article
Parameter tuning of a choice-function based hyperheuristic using Particle Swarm Optimization (2020)
Crawford B.; Soto R.; Monfroy E.; Palma W.; Castro C.; Paredes F. (2013) -
Conference Paper
Autonomous tuning for constraint programming via artificial bee colony optimization (2020)
Soto R.; Crawford B.; Mella F.; Flores J.; Galleguillos C.; Misra S.; Johnson F.; Paredes F. (Springer Verlag, 2015) -
Article
Using autonomous search for solving constraint satisfaction problems via new modern approaches (2020)
Soto R.; Crawford B.; Olivares R.; Galleguillos C.; Castro C.; Johnson F.; Paredes F.; Norero E. (Elsevier B.V., 2016)