A prefiltered cuckoo search algorithm with geometric operators for solving Sudoku problems.
The Sudoku is a famous logic-placement game, originally popularized in Japan and today widely employed as pastime and as testbed for search algorithms. The classic Sudoku consists in filling a 9 × 9 grid, divided into nine 3 × 3 regions, so that each column, row, and region contains different digits from 1 to 9. This game is known to be NP-complete, with existing various complete and incomplete search algorithms able to solve different instances of it. In this paper, we present a new cuckoo search algorithm for solving Sudoku puzzles combining prefiltering phases and geometric operations. The geometric operators allow one to correctly move toward promising regions of the combinatorial space, while the prefiltering phases are able to previously delete from domains the values that do not conduct to any feasible solution. This integration leads to a more efficient domain filtering and as a consequence to a faster solving process. We illustrate encouraging experimental results where our approach noticeably competes with the best approximate methods reported in the literature.
Pontificia Universidad Católica de Valparaíso, 2362807 Valparaíso, Chile ; Universidad Autónoma de Chile, 7500138 Santiago, Chile.
Ricardo
0000-0002-5755-6929
R
Soto
Pontificia Universidad Católica de Valparaíso, 2362807 Valparaíso, Chile ; Universidad Finis Terrae, 7501015 Santiago, Chile.
Broderick
B
Crawford
Pontificia Universidad Católica de Valparaíso, 2362807 Valparaíso, Chile.
Cristian
C
Galleguillos
CNRS, LINA, University of Nantes, 44322 Nantes, France.
Eric
0000-0001-7970-1368
E
Monfroy
Escuela de Ingeniería Industrial, Universidad Diego Portales, 8370109 Santiago, Chile.
Fernando
F
Paredes
D000465:Algorithms; D005716:Game Theory; D011340:Problem Solving