A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles
CONTENIDO PARA USUARIOS REGISTRADOS
Inicia sesión para disfrutar este recurso. Si aún no estás afiliado a BibloRed, haz clic en el botón.
Acceder- Autor
- Año de publicación 2015
- Idioma Inglés
- Publicado por Revista VirtualPRO,
- Descripción
- 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.
-
Citación recomendada (normas APA)
- Hindawi Publishing Corporation, "A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku Puzzles", -:Revista VirtualPRO,, 2015. Consultado en línea en la Biblioteca Digital de Bogotá (https://www.bibliotecadigitaldebogota.gov.co/resources/3435966/), el día 2024-06-17.