Observatorio de I+D+i UPM

Memorias de investigación
Ponencias en congresos:
Using Graphs to Derive CSP Heuristics and its Application to Sudoku
Año:2009
Áreas de investigación
  • Automática
Datos
Descripción
This paper presents a general purpose methodology to derive new heuristics for constraint satisfaction problems using the information contained in an auxiliary graph. The method is then applied to implement a powerful heuristic for Sudoku which is `almost perfect¿ in the sense that a depth first search procedure needs very few backtracks to solve the 16x16 puzzle. The heuristic uses a least-constraining tie break for variable ordering, something very unusual in CSP domains. The paper also presents a minimal set of logical rules which the authors conjecture to solve all 9x9 Sudoku grids with unique solution with just one level of recursion at most.
Internacional
No
Nombre congreso
ICTAI '09. 21st International Conference on Tools with Artificial Intelligence
Tipo de participación
960
Lugar del congreso
Newark, NJ USA
Revisores
Si
ISBN o ISSN
978-1-4244-5619-2
DOI
Fecha inicio congreso
02/11/2009
Fecha fin congreso
04/11/2009
Desde la página
538
Hasta la página
545
Título de las actas
ICTAI '09. 21st International Conference on Tools with Artificial Intelligence, 2009.
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Agustin Jimenez Avello (UPM)
  • Autor: Pablo San Segundo Carrillo (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Control Inteligente
  • Centro o Instituto I+D+i: Centro de Automática y Robótica (CAR). Centro Mixto UPM-CSIC
  • Departamento: Electrónica, Automática e Informática Industrial
  • Departamento: Automática, Ingeniería Electrónica e Informática Industrial
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)