Observatorio de I+D+i UPM

Memorias de investigación
Communications at congresses:
Using Graphs to Derive CSP Heuristics and its Application to Sudoku
Year:2009
Research Areas
  • Automatic
Information
Abstract
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.
International
No
Congress
ICTAI '09. 21st International Conference on Tools with Artificial Intelligence
960
Place
Newark, NJ USA
Reviewers
Si
ISBN/ISSN
978-1-4244-5619-2
Start Date
02/11/2009
End Date
04/11/2009
From page
538
To page
545
ICTAI '09. 21st International Conference on Tools with Artificial Intelligence, 2009.
Participants
  • Autor: Agustin Jimenez Avello (UPM)
  • Autor: Pablo San Segundo Carrillo (UPM)
Research Group, Departaments and Institutes related
  • 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 2019 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)