Back to Study Material Artificial Intelligence

Constraint satisfaction problem

A Constraint Satisfaction Problem, or CSP, is defined by three components: a set of variables, each with a domain of possible values, and a set of constrai...

Constraint satisfaction problem

Problems Defined by Constraints

A Constraint Satisfaction Problem, or CSP, is defined by three components: a set of variables, each with a domain of possible values, and a set of constraints that specify which combinations of values are allowable. The goal is to assign a value to every variable such that all constraints are satisfied simultaneously. This formulation is remarkably general and covers a vast range of practical problems including scheduling, configuration, map colouring, and Sudoku.

Map colouring is the classic illustrative example. The variables are the regions of a map. The domain of each variable is a set of colours. The constraints specify that no two adjacent regions may share the same colour. Solving the CSP means assigning a colour to every region while satisfying all adjacency constraints. The famous four-colour theorem guarantees that any planar map can be solved with just four colours.

CSP algorithms exploit the constraint structure to prune the search space. Backtracking search assigns values one variable at a time and backtracks when a partial assignment violates a constraint. Forward checking prunes the domains of unassigned variables whenever a value is assigned: if a neighbour's domain becomes empty, the current assignment is abandoned immediately. Arc consistency, enforced by the AC-3 algorithm, further reduces domains by removing values that cannot be part of any consistent solution regardless of how other variables are assigned.

Variable and Value Ordering

Heuristics for variable selection significantly affect performance. The minimum remaining values heuristic chooses the variable with the fewest legal values remaining, focusing attention on the most constrained part of the problem first. The degree heuristic breaks ties by choosing the variable involved in the most constraints with unassigned variables.

Interview Tip

When asked about CSPs in interviews, connect them to real problems. Sudoku is a CSP where variables are cells, domains are digits one through nine, and constraints enforce that each row, column, and three-by-three box contains distinct digits. Walk through how arc consistency would propagate after placing a digit in one cell to reduce the domains of cells in the same row, column, and box. This concreteness makes abstract concepts memorable.