Abstract

Constraint satisfaction problems (CSPs) involve finding an assignment of discrete values to variables under the presence of constraints which limit what combinations of assignments are allowed. An example would be colouring a graph with a limited number of colours, such that no two adjacent nodes have the same colour, or solving a Sudoku puzzle. These both involve potentially searching a combinatorially large space of candidate solutions for a feasible assignment.

The talk will begin with an introduction to CSPs and some examples, and point out the specific deficiencies of naive approaches such as basic backtracking (as in Prolog), and how constraint propagation and specialised algorithms for global constraints improve on this. We’ll then see how a sequence of successively more sophisticated approaches and heuristics reduce graph colouring and Sudoku from requiring intractable amounts of time to being solvable within seconds.