Biblioteca32.346 documentos en línea

Artículo

A Hybrid alldifferent-Tabu Search Algorithm for Solving Sudoku PuzzlesUn algoritmo híbrido de búsqueda alldifferent-Tabu para resolver los sudokus

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.

  • Tipo de documento:
  • Formato:pdf
  • Idioma:Inglés
  • Tamaño: Kb

Cómo citar el documento

Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.

Este contenido no est� disponible para su tipo de suscripci�n

Información del documento