CONSTRAINT SATISFACTION PROBLEMS 1 Instructor: Kris Hauser http://cs.indiana.edu/~hauserk CONSTRAINT PROPAGATION Place a queen in a square Remove the attacked squares from future consideration 2 CONSTRAINT PROPAGATION 5 5 5 5 5 6 7 6 6 5 5

5 5 6 Count the number of non-attacked squares in every row and column Place a queen in a row or column with minimum number Remove the attacked squares from future consideration 3 CONSTRAINT PROPAGATION 4 3 3 3 4 5 3 4 4 3 3 5

Repeat 4 CONSTRAINT PROPAGATION 3 3 3 4 3 4 3 2 3 4 5 CONSTRAINT PROPAGATION 3 3 3 1 4

2 2 1 3 6 CONSTRAINT PROPAGATION 2 2 1 2 2 1 7 7 CONSTRAINT PROPAGATION 1 2

2 1 8 CONSTRAINT PROPAGATION 1 1 9 CONSTRAINT PROPAGATION 10 WHAT DO WE NEED? More than just a successor function and a goal test

We also need: A means to propagate the constraints imposed by one queens position on the positions of the other queens An early failure test Explicit representation of constraints Constraint propagation algorithms 11 CONSTRAINT SATISFACTION PROBLEM (CSP) Set of variables {X1, X2, , Xn} Each variable Xi has a domain Di of possible values. Usually, Di is finite

Set of constraints {C1, C2, , Cp} Each constraint relates a subset of variables by specifying the valid combinations of their values Goal: Assign a value to every variable such that all constraints are satisfied 12 12 MAP COLORING NT WA Q SA

NSW V T 7 variables {WA,NT,SA,Q,NSW,V,T} Each variable has the same domain: {red, green, blue} No two adjacent variables have the same value: WANT, WASA, NTSA, NTQ, SAQ, SANSW, SAV, QNSW, NSWV 13 13 8-QUEEN PROBLEM 8 variables Xi, i = 1 to 8

The domain of each variable is: {1,2,,8} Constraints are of the forms: Xi = k Xj k for all j = 1 to 8, ji Similar constraints for diagonals All constraints are binary (in this class) 14 14 SUDOKU 81 variables Domain of each variable: {1,,9} Constraints:

xixj for all ij in same row, same col, same cell xi=vi for fixed cells 15 15 STREET PUZZLE 1 2 3 4 5 Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor}

Ai = {Dog, Snails, Fox, Horse, Zebra} The Englishman lives in the Red house Who Who owns owns the the Zebra? Zebra? The Spaniard has a Dog Who The Japanese is a Painter Who drinks drinks Water? Water? The Italian drinks Tea The Norwegian lives in the first house on the left The owner of the Green house drinks Coffee The Green house is on the right of the White house The Sculptor breeds Snails The Diplomat lives in the Yellow house The owner of the middle house drinks Milk The Norwegian lives next door to the Blue house The Violinist drinks Fruit juice 16 The Fox is in the house next to the Doctors 16

The Horse is next to the Diplomats STREET PUZZLE 1 2 3 4 5 Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra} i,j[1,5], ij, Ni Nj The Englishman lives in the Red house i,j[1,5], ij, Ci Cj The Spaniard has a Dog The Japanese is a Painter ... The Italian drinks Tea

The Norwegian lives in the first house on the left The owner of the Green house drinks Coffee The Green house is on the right of the White house The Sculptor breeds Snails The Diplomat lives in the Yellow house The owner of the middle house drinks Milk The Norwegian lives next door to the Blue house The Violinist drinks Fruit juice 17 The Fox is in the house next to the Doctors 17 The Horse is next to the Diplomats STREET PUZZLE 1 2 3 4 5 Ni = {English, Spaniard, Japanese, Italian, Norwegian}

Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra} (Ni = English) (Ci = Red) The Englishman lives in the Red house The Spaniard has a Dog (Ni = Japanese) (Ji = Painter) The Japanese is a Painter The Italian drinks Tea (N1 = Norwegian) The Norwegian lives in the first house on the left The owner of the Green house drinks Coffee The Green house is on the right of the White house The Sculptor breeds Snails (Ci = White) (Ci+1 = Green) The Diplomat lives in the Yellow house The owner of the middle house drinks Milk (C5 White) The Norwegian lives next door to the Blue house (C1 Green) The Violinist drinks Fruit juice 18 The Fox is in the house next to the Doctors left as an exercise

The Horse is next to the Diplomats STREET PUZZLE 1 2 3 4 5 Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra} (Ni = English) (Ci = Red) The Englishman lives in the Red house The Spaniard has a Dog (Ni = Japanese) (Ji = Painter) The Japanese is a Painter The Italian drinks Tea (N1 = Norwegian)

The Norwegian lives in the first house on the left The owner of the Green house drinks Coffee The Green house is on the right of the White house The Sculptor breeds Snails (Ci = White) (Ci+1 = Green) The Diplomat lives in the Yellow house The owner of the middle house drinks Milk (C5 White) The Norwegian lives next door to the Blue house (C1 Green) The Violinist drinks Fruit juice 19 The Fox is in the house next to the Doctors unary constraints The Horse is next to the Diplomats STREET PUZZLE 1 2 3 4

5 Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra} The Englishman lives in the Red house The Spaniard has a Dog The Japanese is a Painter The Italian drinks Tea The Norwegian lives in the first house on the left N1 = Norwegian The owner of the Green house drinks Coffee The Green house is on the right of the White house The Sculptor breeds Snails The Diplomat lives in the Yellow house The owner of the middle house drinks Milk D3 = Milk The Norwegian lives next door to the Blue house 20 The Violinist drinks Fruit juice The Fox is in the house next to the Doctors 20 The Horse is next to the Diplomats STREET PUZZLE

1 2 3 4 5 Ni = {English, Spaniard, Japanese, Italian, Norwegian} Ci = {Red, Green, White, Yellow, Blue} Di = {Tea, Coffee, Milk, Fruit-juice, Water} Ji = {Painter, Sculptor, Diplomat, Violinist, Doctor} Ai = {Dog, Snails, Fox, Horse, Zebra} The Englishman lives in the Red house C1 Red The Spaniard has a Dog A1 Dog The Japanese is a Painter The Italian drinks Tea The Norwegian lives in the first house on the left N1 = Norwegian The owner of the Green house drinks Coffee The Green house is on the right of the White house The Sculptor breeds Snails The Diplomat lives in the Yellow house The owner of the middle house drinks Milk D3 = Milk

The Norwegian lives next door to the Blue house 21 The Violinist drinks Fruit juice J3 Violinist The Fox is in the house next to the Doctors The Horse is next to the Diplomats TASK SCHEDULING T1 T2 T4 T3 Four tasks T1, T2, T3, and T4 are related by time constraints: T1 T2 T2 T4

must must must must be done during T3 be achieved before T1 starts overlap with T3 start after T1 is complete Are the constraints compatible? What are the possible time relations between two tasks? What if the tasks use resources in limited supply? 22 How to formulate this problem as a CSP? 3-SAT n Boolean variables u1, ..., un

p constraints of the form ui* uj* uk*= 1 where u* stands for either u or u Known to be NP-complete 23 23 FINITE VS. INFINITE CSP Finite CSP: each variable has a finite domain of values Infinite CSP: some or all variables have an infinite domain E.g., linear programming problems over the reals: We will only consider finite CSP 24

CSP AS A SEARCH PROBLEM n variables X1, ..., Xn Valid assignment: {Xi1 vi1, ..., Xik vik}, 0 k n, such that the values vi1, ..., vik satisfy all constraints relating the variables Xi1, ..., Xik Complete assignment: one where k = n [if all variable domains have size d, there are O(d n) complete assignments] States: valid assignments Initial state: empty assignment {}, i.e. k = 0 Successor of a state: {Xi1vi1, ..., Xikvik} {Xi1vi1, ..., Xikvik, Xik+1vik+1} Goal test: k = n

25 {Xi1vi1, ..., Xikvik} {Xi1vi1, ..., Xikvik, Xik+1vik+1} r = n-k variables with s values rs branching factor 26 26 A KEY PROPERTY OF CSP: COMMUTATIVITY The order in which variables are assigned values has no impact on the reachable complete valid assignments Hence: 1) One can expand a node N by first selecting one variable X not in the assignment A associated with N and then assigning every value v in the domain of X [ big reduction in branching factor]

27 27 {Xi1vi1, ..., Xikvik} {Xi1vi1, ..., Xikvik, Xik+1vik+1} r = n-k variables with s values rs branching factor s branching factor 28 The depth of the solutions in the search tree is un-changed (n) 4 variables X1, ..., X4 Let the valid assignment of N be: A = {X1 v1, X3 v3} For example pick variable X4

Let the domain of X4 be {v4,1, v4,2, v4,3} The successors of A are all the valid assignments among: {X1 v1, X3 v3 , X4 v4,1 } {X1 v1, X3 v3 , X4 v4,2 } {X1 v1, X3 v3 , X4 v4,3 } 29 29 A KEY PROPERTY OF CSP: COMMUTATIVITY The order in which variables are assigned values has no impact on the reachable complete valid assignments

Hence: 1) One can expand a node N by first selecting one variable X not in the assignment A associated with N and then assigning every value v in the domain of X [ big reduction in branching factor] 2) One need not store the path to a node 30 Backtracking search algorithm BACKTRACKING SEARCH Essentially a simplified depth-first algorithm using recursion 31 31 BACKTRACKING SEARCH (3 VARIABLES) Assignment = {} 32

32 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 Assignment = {(X1,v11)} 33 33 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 X3 v31 Assignment = {(X1,v11), (X3,v31)} 34 34 BACKTRACKING SEARCH

(3 VARIABLES) X1 v11 X3 v31 X2 Then, the search algorithm backtracks to the previous variable (X3) and tries another value Assume that no value of X2 leads to a valid assignment Assignment = {(X1,v11), (X3,v31)} 35 35 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 X3

v31 v32 X2 Assignment = {(X1,v11), (X3,v32)} 36 36 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 X3 v31 X2 v32 X2 The search algorithm backtracks to the previous variable (X3)

and tries another value. But assume that X3 has only two possible values. The algorithm backtracks to X1 Assume again that no value of X2 leads to a valid assignment Assignment = {(X1,v11), (X3,v32)} 37 37 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 v12 X3 v31 X2

v32 X2 Assignment = {(X1,v12)} 38 38 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 v12 X3 v31 X2 X2 v32 v21 X2

Assignment = {(X1,v12), (X2,v21)} 39 39 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 v12 X3 v31 X2 X2 v32 X2 v21 The algorithm need not consider the variables in the same order in

this sub-tree as in the other Assignment = {(X1,v12), (X2,v21)} 40 40 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 v12 X3 v31 X2 X2 v21 v32 X2 X3

v32 Assignment = {(X1,v12), (X2,v21), (X3,v32)} 41 41 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 v12 X3 v31 X2 X2 v21 v32 X2 X3

v32 The algorithm need not consider the values of X3 in the same order in this sub-tree Assignment = {(X1,v12), (X2,v21), (X3,v32)} 42 42 BACKTRACKING SEARCH (3 VARIABLES) X1 v11 v12 X3 v31 X2 X2 v21

v32 X2 X3 v32 Since there are only three variables, the assignment is complete Assignment = {(X1,v12), (X2,v21), (X3,v32)} 43 43 BACKTRACKING ALGORITHM CSP-BACKTRACKING(A) 1. 2. 3. 4. If assignment A is complete then return A X select a variable not in A

D select an ordering on the domain of X For each value v in D do a. b. c. 5. Add (Xv) to A If A is valid then i. result CSP-BACKTRACKING(A) ii. If result failure then return result Remove (Xv) from A Return failure Call CSP-BACKTRACKING({}) [This recursive algorithm keeps too much data in memory. An iterative version could save memory (left as an exercise)] 44 44

CRITICAL QUESTIONS FOR THE EFFICIENCY OF CSP-BACKTRACKING CSP-BACKTRACKING(A) 1. 2. 3. 4. If assignment A is complete then return A X select a variable not in A D select an ordering on the domain of X For each value v in D do a. Add (Xv) to A b. If a is valid then i. result CSP-BACKTRACKING(A) ii. If result failure then return result c. Remove (Xv) from A 5. Return failure 45 45

CRITICAL QUESTIONS FOR THE EFFICIENCY OF CSP-BACKTRACKING 1. Which variable X should be assigned a value next? 2. In which order should Xs values be assigned? 46 CRITICAL QUESTIONS FOR THE EFFICIENCY OF CSP-BACKTRACKING 1. Which variable X should be assigned a value next? The current assignment may not lead to any solution, but the algorithm does not know it yet. Selecting the right variable X may help discover the contradiction more quickly

2. In which order should Xs values be assigned? 47 CRITICAL QUESTIONS FOR THE EFFICIENCY OF CSP-BACKTRACKING 1. Which variable X should be assigned a value next? The current assignment may not lead to any solution, but the algorithm does not know it yet. Selecting the right variable X may help discover the contradiction more quickly 2. In which order should Xs values be assigned? The current assignment may be part of a solution. Selecting the right value to assign to X may help discover this solution more

quickly 48 CRITICAL QUESTIONS FOR THE EFFICIENCY OF CSP-BACKTRACKING 1. Which variable X should be assigned a value next? The current assignment may not lead to any solution, but the algorithm does not know it yet. Selecting the right variable X may help discover the contradiction more quickly 2. In which order should Xs values be assigned? The current assignment may be part of a solution. Selecting the right value to assign to X may help discover this solution more quickly More on these questions very soon ...

49 FORWARD CHECKING A simple constraint-propagation technique: 1 2 3 4 5 6 7 8 Assigning the value 5 to X1 leads to removing values from the domains of X2, X3, ..., X8 X1 X2 X3 X4 X5 X6 X7 X8 50 50 FORWARD CHECKING IN MAP COLORING NT

WA Constraint graph Q NSW SA T V WA NT Q NSW V SA T

RGB RGB RGB RGB RGB RGB RGB 51 51 FORWARD CHECKING IN MAP COLORING NT WA Q NSW

SA T V WA NT Q NSW V SA T RGB RGB

RGB RGB RGB RGB RGB R RGB RGB RGB RGB RGB RGB Forward checking removes the value Red of NT and of SA

52 52 FORWARD CHECKING IN MAP COLORING NT WA Q NSW SA T V WA NT Q NSW

V SA T RGB RGB RGB RGB RGB RGB RGB R GB RGB

RGB RGB GB RGB R GB G RGB RGB GB RGB 53 53

FORWARD CHECKING IN MAP COLORING NT WA Q NSW SA T V WA NT Q NSW V SA

T RGB RGB RGB RGB RGB RGB RGB R GB RGB RGB

RGB GB RGB R B G RB RGB B RGB R B G

RB B B RGB 54 54 FORWARD CHECKING IN MAP COLORING Empty set: the current assignment {(WA R), (Q G), (V B)} does not lead to a solution WA NT Q NSW

V SA T RGB RGB RGB RGB RGB RGB RGB R GB RGB

RGB RGB GB RGB R B G RB RGB B RGB R

B G RB B B RGB 55 55 FORWARD CHECKING (GENERAL FORM) Whenever a pair (Xv) is added to assignment A do: For each variable Y not in A do: For every constraint C relating Y to the variables in A do: Remove all values from Ys domain that do not satisfy C 56 56

MODIFIED BACKTRACKING ALGORITHM CSP-BACKTRACKING(A, var-domains) 1. 2. 3. 4. If assignment A is complete then return A X select a variable not in A D select an ordering on the domain of X For each value v in D do a. b. c. d. 5. Add (Xv) to A var-domains forward checking(var-domains, X, v, A)

If no variable has an empty domain then (i) result CSP-BACKTRACKING(A, var-domains) (ii) If result failure then return result Remove (Xv) from A Return failure 57 57 MODIFIED BACKTRACKING ALGORITHM CSP-BACKTRACKING(A, var-domains) 1. 2. 3. 4. If assignment A is complete then return A X select a variable not in A D select an ordering on the domain of X For each value v in D do No need any more to a. b.

c. d. 5. Add (Xv) to A verify that A is valid var-domains forward checking(var-domains, X, v, A) If no variable has an empty domain then (i) result CSP-BACKTRACKING(A, var-domains) (ii) If result failure then return result Remove (Xv) from A Return failure 58 MODIFIED BACKTRACKING ALGORITHM CSP-BACKTRACKING(A, var-domains) 1. 2.

3. 4. If assignment A is complete then return A X select a variable not in A D select an ordering on the domain of X For each value v in D do a. b. c. d. 5. Add (Xv) to A var-domains forward checking(var-domains, X, v, A) If no variable has an empty domain then (i) result CSP-BACKTRACKING(A, var-domains) (ii) If result failure then return result Remove (Xv) from A Return failure

Need to pass down the updated variable domains 59 MODIFIED BACKTRACKING ALGORITHM CSP-BACKTRACKING(A, var-domains) 1. 2. 3. 4. If assignment A is complete then return A X select a variable not in A D select an ordering on the domain of X For each value v in D do a. b. c. d.

5. Add (Xv) to A var-domains forward checking(var-domains, X, v, A) If no variable has an empty domain then (i) result CSP-BACKTRACKING(A, var-domains) (ii) If result failure then return result Remove (Xv) from A Return failure 60 1) Which variable Xi should be assigned a value next? Most-constrained-variable heuristic Most-constraining-variable heuristic 2) In which order should its values be assigned?

Least-constraining-value heuristic 61 MOST-CONSTRAINED-VARIABLE HEURISTIC 1) Which variable Xi should be assigned a value next? Select the variable with the smallest remaining domain [Rationale: Minimize the branching factor] 62 62 8-QUEENS Forward checking New assignment 4 3

2 3 4 Numbers of values for each un-assigned variable 63 63 8-QUEENS Forward checking New assignment 3 2 1 3 New numbers of values for each un-assigned variable 64

64 MAP COLORING NT WA Q SA NSW V T SAs remaining domain has size 1 (value B remaining) Qs remaining domain has size 2 NSWs, Vs, and Ts remaining domains have size 3 Select SA 65

MOST-CONSTRAINING-VARIABLE HEURISTIC 1) Which variable Xi should be assigned a value next? Among the variables with the smallest remaining domains (ties with respect to the mostconstrained-variable heuristic), select the one that appears in the largest number of constraints on variables not in the current assignment [Rationale: Increase future elimination of values, to reduce future branching factors] 66 66 MAP COLORING NT WA Q SA

NSW V T Before any value has been assigned, all variables have a domain of size 3, but SA is involved in more constraints (5) than any other variable Select SA and assign a value to it (e.g., 67 Blue) 67 LEAST-CONSTRAINING-VALUE HEURISTIC 2) In which order should Xs values be assigned? Select the value of X that removes the smallest number of values from the domains of those variables which are not in the current assignment [Rationale: Since only one value will eventually be assigned to X, pick the

least-constraining value first, since it is the most likely not to lead to an invalid assignment] 68 [Note: Using this heuristic requires performing a forward-checking step for every value, not just for MAP COLORING NT WA Q SA NSW V {} T

Qs domain has two remaining values: Blue and Red Assigning Blue to Q would leave 0 value for SA, while assigning Red would leave 1 value 69 69 MAP COLORING NT WA Q SA NSW V {Blue} T Qs domain has two remaining values: Blue and

Red Assigning Blue to Q would leave 0 value for SA, while assigning Red would leave 1 value So, assign Red to Q 70 70 MODIFIED BACKTRACKING ALGORITHM CSP-BACKTRACKING(A, var-domains) 1. 2. 3. 4. a. b. ) Most-constrained-variable heuristic ) Most-constraining-variable heuristic ) Least-constraining-value heuristic

If assignment A is complete then return A X select a variable not in A D select an ordering on the domain of X For each value v in D do c. d. 5. Add (Xv) to A var-domains forward checking(var-domains, X, v, A) If no variable has an empty domain then (i) result CSP-BACKTRACKING(A, var-domains) (ii) If result failure then return result Remove (Xv) from A Return failure 71 71 APPLICATIONS OF CSP CSP techniques are widely used

Applications include: Crew assignments to flights Management of transportation fleet Flight/rail schedules Job shop scheduling Task scheduling in port operations Design, including spatial layout design 72 72 RECAP CSPs Backtracking search Constraint propagation 73 HOMEWORK

R&N 6.3-5 74