Constraint Satisfaction Problems - Overview

Lecturers: Prof. Dr. Bernhard Nebel, Prof. Dr. Christian Becker-Asano und Dr. Stefan Wölfl

Exercises: Dr. Stefan Wölfl


Lecture: Monday 10:15-12:00 and Wednesday 10:15-11:00
Exercises: Wednesday 11:15-12:00


Lecture: Building 51, Room SR 00 006
Exercises: Building 51, Room SR 00 006


The lecture and exercises will be given in english. The slides are in english. Exercises can be submitted in english or german.


The lecture provides an extensive introduction into the domain of constraint satisfaction problems. For this purpose both theoretic and algorithmic questions will be examined.

In particular, the following topics are planed:

  • Foundations and introduction: sets, relations, graphs, constraint networks and satisfiability, binary constraint networks.
  • Inference-based methods: arc and path consistency, n-consistency and global consistency
  • Search: backtracking, backjumping, comparison of methods, stochastic local search.
  • Selected advanced topics: expressiveness and complexity of constraint languages, qualitative constraint networks.


The lecture is intended for Bachelor, Master and Diploma students.

Knowledge of propositional logic and theoretical computer science (NP-completeness, polynomial reductions) are expected. Basic knowledge of search (depth-first, backtracking, local search) will be helpful.


Slides used in the lecture will be availbale on the lecture page. Additional material on discussed topics will be anounced in the lecture. There is no book or script of this lecture.

The lecture will not be recorded.