The tutorial teaches concepts from the AI literature on Constraint Satisfaction. Accompanying animations are in http://www.cs.cmu.edu/~awm/animations/constraint. This is a special case of uninformed search in which we want to find a solution configuration for some set of variables that satisfies a set of constraints. Example problems including graph coloring, 8-queens, magic squares, the Waltz algorithm for interpreting line drawings, many kinds of scheduling and most important of all, the deduction phase of minesweeper. The algorithms we'll look at include backtracking search, forward checking search and constraint propagation search. We'll also look at general-purpose heuristics for additional search accelerations.

Download Slides PDF