Constraint Satisfaction Tutorial

Notes for CC484 Students:

• Overview lecture
• Problem Reduction
• Complete Search Methods
• Sotchastic Search

Assignments 1 & 2, 2006

Edgar Galvan's Classes:

• Class 1 Slides / Exercise
• Class 2 Slides / Exercise
• Class 3 Slides / Exercise
• Class 4 Slides (Genetic Programming)

Demo Programs:

• Backmarking Algorithm by Luis Vargas, 2002-03 (Installation shield, 23MB)
• Learning Nogoods Algorithm by Cesareo Gutierrez Casorran, 2002-03 (Java programs, 176K)

References:

• E P K Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993 (On-line)
• F Rossi, P van Beek & T Walsh, Handbook of Constraint Programming, Elsevier, 2006
• http://cswww.essex.ac.uk/CSP links to other major research sites

Exercises for Students:

• Problem formulation: the witnesses identities problem
• The SEND-MORE-MONEY problem: Problem Formulation and Model Selection
• Lookahead search: the 8-Queens problem
• Search: Intelligent backtracking
• Problem formulation: From CSP to SAT (answer)
• GSAT hill-climbing (answer)
• GSAT and GLS heuristic search
• Tests:
  • Exercises 2003-04 (Answers)
  • Exercises and Answers 2002-03