Resumen

El problema del Sudoku es un conocido rompecabezas lógico de colocación de números combinatoria. Consiste en rellenar una cuadrícula de n2 × n2, compuesta por n columnas, n filas y n subcuadrículas, cada una de las cuales contiene enteros distintos de 1 a n2. Dicho rompecabezas pertenece a la colección de problemas NP-completos, para los que existen diversos métodos exactos y aproximados capaces de resolverlo. En este trabajo, proponemos un nuevo algoritmo híbrido que combina inteligentemente un procedimiento clásico de búsqueda tabú con la restricción global alldifferent del mundo de la programación de restricciones. Se sabe que la restricción alldifferent es eficiente para el filtrado de dominios en presencia de restricciones que deben ser pares diferentes, que son exactamente el tipo de restricciones que poseen los Sudokus. Esta capacidad alivia claramente el trabajo de la búsqueda tabú, resultando en un enfoque más rápido y robusto para resolver Sudokus. Ilustramos interesantes resultados experimentales en los que nuestro algoritmo propuesto supera los mejores resultados anteriormente reportados por los métodos híbridos y aproximados.

• Materias:Inteligencia artificial Algoritmos genéticos Ingeniería civil Neurociencia Cognitiva
• Subjects:Artificial intelligence Genetic algorithms Civil engineering Cognitive Neuroscience
• Palabras claves:métodos aproximados, mundo de la programación de restricciones, colección de problemas, presencia de restricciones, procedimientos de búsqueda tabú, tipo de restricciones, el algoritmo propuesto supera, nuevo algoritmo híbrido, resultados experimentales interesantes, rompecabezas basado
• Keywords:approximate methods, constraints programming world, collection of problem, presence of constraints, tabu search procedures, kind of constraints, proposed algorithm outperforms, new hybrid algorithm, interesting experimental results, based puzzle