Centro Investigación en Educación Superior

A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles

CATEGORÍA(S): , , , .
AUTOR(ES): Ricardo Soto / Broderick Crawford / Cristian Galleguillos / Fernando Paredes / Enrique Norero.
Licencia Creative Commons Reconocimiento CC BY. Esta obra está bajo una Licencia Creative Commons Reconocimiento CC BY 4.0 Internacional.

The Sudoku problem is a well-known logic-based puzzle of combinatorial number-placement. It consists in filling a n2 × n2 grid, composed of n columns, n rows, and n subgrids, each one containing distinct integers from 1 to n2. Such a puzzle belongs to the NP-complete collection of problems, to which there exist diverse exact and approximate methods able to solve it. In this paper, we propose a new hybrid algorithm that smartly combines a classic tabu searchprocedure with the <monospace>alldifferent</monospace> global constraint from the constraint programming world. The <monospace>alldifferent</monospace> constraint is known to be efficient for domain filtering in the presence of constraints that must be pairwise different, which are exactly the kind of constraints that Sudokus own. This ability clearly alleviates the work of the tabu search, resulting in a faster and more robust approach for solving Sudokus. We illustrate interesting experimental results where our proposed algorithm outperforms the best results previously reported by hybrids and approximate methods.

Documentos relacionados

Portada 1

Serie Creación – Documento de trabajo n°29: Apunte de clase elaborado por Docente – Kinesiólogo. Juan Inostroza Silva Universidad San Sebastián de Puerto Montt.

La Terapia de Onda Corta Pulsada (TOCP) es una modalidad ampliamente utilizado en el Reino Unido (Al Mandil y Watson […]

Saltar a la barra de herramientas