48 Constraint Satisfaction Problem

A constraint satisfaction problem consists of

• A set of variables.
• A domain for each variable.
• A set of constraints. In a CSP, an assignment is complete if every variable has a value, otherwise it is partial. Solutions are complete assignments satisfying all the constraints.

Example : Module scheduling problem

• Variables - Modules : AI1, DSA, SEPP etc
• Domain - year-term : {1-1,1-2,2-1,2-2,3-1,3-2}
• Constraints : pre-requisites - {AI1 < AI2, OOP < SE..}
• Solutions - e.g.: (AI1=1 2, OOP=1 1, AI2=2 2, SE=2 1…)

Standard Search Problems vs CSPs

Standard Search Problems

• State is a “black-box” : arbitrary data structure
• Goal state can be any function over states

Constraint Satisfaction Problems (CSPs)

• State is defined by variables $X_1,X_2,\dots$ with values from domains $D_1,D_2,\dots$
• Goal test is a set of constraints specifying allowable combinations of values of variables.
• An example of formal representation language, in which many search problems can be abstracted. This allows useful general-purpose algorithms with more power that standard search algorithms.

Constraint Graphs

Constraint graphs are used to represent relations among constraints in CSPs, where nodes correspond to the variables and arcs reflect the constraints.

Example : Einstein Puzzle

Problem : There are two houses, House1 and House2. E ach house has a different Colour (blue or red), and a different Pet (cat, dog or fish). We also have the following constraints: House1 does not have a dog nor fish. The blue house has a fish . Question: which colour and pet each house has?

• Variables :
  • Colour1, Colour2, Pet1, Pet2
• Domain :
  • Colour1, Colour2 = {blue, red}
  • Pet1, Pet2 = {cat, dog, fish}
• Constraints :
  • Pet1 $\ne$ {cat, dog, fish}
  • If Colour1 = blue, then Pet1 = fish
  • If Colour2 = blue then Pet2 = fish
  • If Colour1 $\ne$ Colour2, Pet1 $\ne$ Pet2

Example : Sudoku

Problem : Sudoku is to fill a 9 × 9 grid with digits so that each column, each row, and each of the regions contain all of the digits from 1 to 9.

• Variables : each open cell
• Domain : $D\in \{1,2,3,\dots ,9\}$
• Constraints :
  • Each row contains different numbers
  • Each column contains different numbers
  • Each region contains different numbers