Exercises: Artificial Intelligence

MiniMax & Constraint Processing:

MiniMax Algorithm
MiniMax & Constraint Processing: MiniMax Algorithm

PROBLEM 1
 Problem 1
• Perform the minimax algorithm on the figure
below. First without, later with ab-pruning.
Max

Min

Max

Min

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
MiniMax & Constraint Processing: MiniMax Algorithm

MINIMAX ALGORITHM
 MiniMax Algorithm
• Restrictions
– 2 players: Max = Computer & Min = Opponent
– Deterministic, perfect information
• Depth-bound & Evaluation function
– Construct tree (depth-bound)
Max 3
– Compute evaluation leaves
– Propagate upwards (min/max) Min 3 1

4 3 5 2 1
 ab-Pruning
• Generally applied optimization
– Instead of generating, then propagating
– Interleave generation and propagation
• Obtain information on redundant parts
• Generate tree: depth-first & Left-to-right
Max ≥3
– Propagate values of nodes
– Estimates for parent nodes Min =3 ≤2

4 3 5 2 1
MiniMax & Constraint Processing: MiniMax Algorithm

MINIMAX WITHOUT ab-PRUNING

ab
 MiniMax without ab-pruning

Max

Min

Max

Min 3

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax without ab-pruning

Max

Min

Max

Min 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax without ab-pruning

Max

Min

Max

Min 3 1 2 4 7 2 0 3 0 2 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax without ab-pruning

Max

Min

Max 3

Min 3 1 2 4 7 2 0 3 0 2 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax without ab-pruning

Max

Min

Max 3 2

Min 3 1 2 4 7 2 0 3 0 2 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax without ab-pruning

Max

Min

Max 3 2 7 0 3 3

Min 3 1 2 4 7 2 0 3 0 2 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax without ab-pruning

Max

Min 2 0

Max 3 2 7 0 3 3

Min 3 1 2 4 7 2 0 3 0 2 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax without ab-pruning

Max 2

Min 2 0

Max 3 2 7 0 3 3

Min 3 1 2 4 7 2 0 3 0 2 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
MiniMax & Constraint Processing: MiniMax Algorithm

MINIMAX WITH ab-PRUNING

ab
 MiniMax with ab-pruning

Max

Min

Max

Min

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning
• a-nodes: Temporary values at MIN-nodes
Max

Min

Max

Min ≤4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min

Max

Min ≤4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min

Max

Min ≤3

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min

Max

Min ≤3

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min

Max

Min =3

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning
• b-nodes: Temporary values at MAX-nodes
Max

Min

Max ≥3

Min =3

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min

Max ≥3

Min =3

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min

Max ≥3

Min =3 ≤2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning
• Prune: Parent b-node ≥ Child a-node
Max

Min

Max ≥3

Min =3 ≤2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min

Max =3

Min =3 =2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3

Min =3 =2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3

Min =3 =2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3

Min =3 =2 ≤4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3

Min =3 =2 ≤4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3

Min =3 =2 ≤2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3

Min =3 =2 ≤2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3

Min =3 =2 =2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤3

Max =3 =2

Min =3 =2 =2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤2

Max =3 =2

Min =3 =2 =2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤2

Max =3 =2

Min =3 =2 =2

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤2

Max =3 =2

Min =3 =2 =2
≤5

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤2

Max =3 =2

Min =3 =2 =2
≤5

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤2

Max =3 =2

Min =3 =2 =2
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min ≤2

Max =3 =2 ≥4

Min =3 =2 =2
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning
• Prune: Parent a-node ≤ Child b-node
Max

Min ≤2

Max =3 =2 ≥4

Min =3 =2 =2
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max

Min =2

Max =3 =2 =4

Min =3 =2 =2
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max ≥2

Min =2

Max =3 =2 =4

Min =3 =2 =2
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max ≥2

Min =2

Max =3 =2 =4

Min =3 =2 =2
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max ≥2

Min =2

Max =3 =2 =4

Min =3 =2 =2 ≤1
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning
• “Deep” cut-off: Ancestor b-node ≥ a-node
Max ≥2

Min =2

Max =3 =2 =4

Min =3 =2 =2 ≤1
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max ≥2

Min =2

Max =3 =2 =4 =1

Min =3 =2 =2 =1
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning

Max ≥2

Min =2 ≤1

Max =3 =2 =4 =1

Min =3 =2 =2 =1
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning
• Prune: Parent b-node ≥ Child a-node
Max ≥2

Min =2 ≤1

Max =3 =2 =4 =1

Min =3 =2 =2 =1
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 MiniMax with ab-pruning
• 17 static evaluations saved
Max =2

Min =2 =1

Max =3 =2 =4 =1

Min =3 =2 =2 =1
=4

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
MiniMax & Constraint Processing: MiniMax Algorithm

PROBLEM 2
 Problem 2
• Can the nodes be ordered in such a way that
ab-pruning can cut off more branches?
Max

Min

Max

Min

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
MiniMax & Constraint Processing: MiniMax Algorithm

OPTIMIZING ab-PRUNING
ab
 Optimizing ab-Pruning
• Best case: Each layer best node left-to-right
Max 2

Min 2 0

Max 3 2 7 0 3 3

Min 3 1 2 4 7 2 0 3 0 2 3 1

4 3 5 2 1 4 2 3 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 Optimizing ab-Pruning
• Best case: Each layer best node left-to-right
Max

Min

Max 2 3 7 0 3 3

Min 2 3 1 4 7 2 0 3 0 2 3 1

4 2 3 4 3 5 2 1 5 4 7 3 2 1 4 0 5 3 0 2 7 4 3 6 5 3 1
 Optimizing ab-Pruning
• Best case: Each layer best node left-to-right
Max

Min

Max

Min 2 3 1 7 4 2 0 3 0 3 2 1

4 2 3 4 3 5 2 1 7 5 4 3 2 1 4 0 5 3 0 3 6 2 7 4 5 3 1
 Optimizing ab-Pruning
• Best case: Each layer best node left-to-right
Max

Min

Max

Min

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
MiniMax & Constraint Processing: MiniMax Algorithm

MINIMAX WITH ab-PRUNING

ab
 Minimax with ab-Pruning

Max

Min

Max

Min

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min

Max

Min ≤2

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min

Max

Min ≤2

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min

Max

Min ≤2

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min

Max

Min =2

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min

Max =2

Min =2

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2

Min =2

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2

Min =2

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2

Min =2 ≤3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2

Min =2 ≤3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2

Min =2 ≤3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2

Min =2 =3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 ≥3

Min =2 =3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 ≥3

Min =2 =3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 =3

Min =2 =3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 =3

Min =2 =3

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 =3

Min =2 =3
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 =3 ≥7

Min =2 =3
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 =3 ≥7

Min =2 =3
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min ≤2

Max =2 =3 =7

Min =2 =3
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max

Min =2

Max =2 =3 =7

Min =2 =3
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2

Max =2 =3 =7

Min =2 =3
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2

Max =2 =3 =7

Min =2 =3
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2

Max =2 =3 =7

Min =2 =3 ≤0
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2

Max =2 =3 =7

Min =2 =3 ≤0
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2

Max =2 =3 =7

Min =2 =3 =0
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2

Max =2 =3 =7 =0

Min =2 =3 =0
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2 ≤0

Max =2 =3 =7 =0

Min =2 =3 =0
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning

Max ≥2

Min =2 ≤0

Max =2 =3 =7 =0

Min =2 =3 =0
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
 Minimax with ab-Pruning
• 19 static evaluations saved
Max ≥2

Min =2 =0

Max =2 =3 =7 =0

Min =2 =3 =0
=7

2 3 4 3 4 5 1 2 7 4 5 2 3 0 1 4 3 5 0 3 6 2 4 7 1 3 5
Exercises: Artificial Intelligence

MiniMax & Constraint Processing:

MiniMax Algorithm for 3 Players
MiniMax & Constraint Processing: MiniMax Algorithm for 3 Players

PROBLEM
 Problem
• Come up with a MiniMax algorithm for 3
players and apply on the figure below.
. . .

. . . . . .

. . . . . . . . . . . .

1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
MiniMax & Constraint Processing: MiniMax Algorithm

MINIMAX FOR 3 PLAYERS

 MiniMax For 3 Players
• All players are Max
• Evaluation function given by vector
. . .

. . . . . .

. . . . . . . . . . . .

1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• Each layer assigned to 1 player
• Turn: every 3 layers
. . .

Player 1
. . . . . .
Player 2
. . . . . . . . . . . .
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• Max third player: third position of vector

. . .

. . . . . .

. . . . . . . . . . . .
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• MaxThirdPlayer([1,2,3],[4,2,1]) = [1,2,3]
• MaxThirdPlayer([6,1,2],[7,4,-1]) = [6,1,2]
• MaxThirdPlayer([5,-1,-1],[-1,5,2]) = [-1,5,2]
• MaxThirdPlayer([7,7,-1],[5,4,5]) = [5,4,5]

. . .

. . . . . .

1 2 3 6 1 2 -1 5 2 5 4 5
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• Second player’s move

. . .

. . . . . .
Player 2
1 2 3 6 1 2 -1 5 2 5 4 5
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• Max second player: second position of vector

. . .

. . . . . .
Player 2
1 2 3 6 1 2 -1 5 2 5 4 5
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• MaxSecondPlayer([1,2,3],[6,1,2]) = [1,2,3]
• MaxSecondPlayer([-1,5,2],[5,4,5]) = [-1,5,2]
. . .

1 2 3 -1 5 2
Player 2
1 2 3 6 1 2 -1 5 2 5 4 5
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• First player’s move

. . .

Player 1
1 2 3 -1 5 2
Player 2
1 2 3 6 1 2 -1 5 2 5 4 5
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• Max first player: first position of vector

. . .

Player 1
1 2 3 -1 5 2
Player 2
1 2 3 6 1 2 -1 5 2 5 4 5
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
 MiniMax For 3 Players
• MaxFirstPlayer([1,2,3],[-1,5,4]) = [1,2,3]

1 2 3

Player 1
1 2 3 -1 5 2
Player 2
1 2 3 6 1 2 -1 5 2 5 4 5
Player 3
1 2 3 4 2 1 6 1 2 7 4 -1 5 -1 -1 -1 5 2 7 7 -1 5 4 5
Exercises: Artificial Intelligence

MiniMax & Constraint Processing:

The 4 Houses problem
MiniMax & Constraint Processing: The 4 Houses problem

PROBLEM
 Problem
• Variant of the 4 houses problem
– There are 4 Families: A, B, C & D
– Living in 4 Houses: 1, 2, 3 & 4
– C lives in a house with higher number than D
– D lives next to A in a lower numbered house
– There is at least one house between D and B
– C does not live in 3
– B does not live in 1
 Problem
• Which family lives in which house?
– Solve with backtracking
– Solve with backjumping
– Solve with backmarking
• Consider the following sets of assignments:
– {A=1},{A=2,B=2},{A=2,B=3},{A=2,B=3,C=1},{A=2,B=4}
– Which of these are no-goods?
• You can use arc-consistency arguments to determine
the no-goods and the not no-goods
MiniMax & Constraint Processing: The 4 Houses problem

CONSTRAINT PROCESSING:
PROBLEM REPRESENTATION
 Constraint Processing
• Problem representation:

∫B
A∫ ∫1
B∫
A B
D=A-1 ∫C
B∫

∫C
A∫ |B-D|≥2

∫3
C∫ C C>D D
MiniMax & Constraint Processing: The 4 Houses problem

CONSTRAINT PROCESSING:
BACKTRACKING
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backtracking
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 3 4 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,D)
c(B,D)
c(C,D)
MiniMax & Constraint Processing: The 4 Houses problem

CONSTRAINT PROCESSING:
BACKJUMPING
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D) Backjump to A
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backjumping
∫1
B∫
∫B
A∫
A B
A 1 2 ∫C
D=A-1 B∫
∫C
A∫ |B-D|≥2
B 1 2 1 2 3 C C>D D
c(A,B) ∫3
C∫

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1
c(A,D)
c(B,D)
c(C,D)
MiniMax & Constraint Processing: The 4 Houses problem

CONSTRAINT PROCESSING:
BACKMARKING
 Constraint Processing: Backmarking
1 2 3 4 Backup

A A 1 1 1 1
B 1 1 1 1
1
1

B C 1 1 1 1
D 1 1 1 1
1
1
c(A,B)

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 1 1 1 1
1
1

B C 1 1 1 1
D 1 1 1 1
1
1
c(A,B)

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1
C 1 1 1 1
D 1 1 1 1
1
1
c(A,B)

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2
C 1 1 1 1
D 1 1 1 1
1
1
c(A,B)

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2
C 1 1 1 1
D 1 1 1 1
1
1
c(A,B)

C 1
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2
C 1 2 1 1
D 1 1 1 1
1
1
c(A,B)

C 1 2
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2
C 1 2 0 1
D 1 1 1 1
1
1
c(A,B)

C 1 2 3
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2
C 1 2 0 2
D 1 1 1 1
1
1
c(A,B)

C 1 2 3 4
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2
C 1 2 0 2
D 1 1 1 1
1
1
c(A,B)

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3
C 1 2 0 2
D 1 1 1 1
2
3
c(A,B)

C 1 2 3 4 1 2 3
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3
C 1 2 0 2
D 1 1 1 1
2
3
c(A,B)

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3
C 1 2 0 2
D 1 1 1 1
2
3
c(A,B)

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3 4
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3 4
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3 4
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3 4
C 1 2 0 2
D 1 1 1 1
2
2
c(A,B)

C 1 2 3 4 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3 4
C 1 2 0 2
D 1 1 1 1
2
3
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1
A 0 1 1 1
B 0 1 1 1
1
1

B 1 2 3 4
C 1 2 0 2
D 1 1 1 1
2
3
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4
C 1 2 0 2
D 1 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1
C 1 2 0 2
D 1 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2
C 1 2 0 2
D 1 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 1 2 0 2
D 1 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 2 0 2
D 1 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 2 0 2
D 3 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 2 0 2
D 3 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 2 0 2
D 3 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 2 0 2
D 3 1 1 1
1
1
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 1 0 2
D 3 1 1 1
1
3
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 1 0 2
D 3 1 1 1
1
3
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 1 0 2
D 3 1 1 1
1
3
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Backmarking
1 2 3 4 Backup

A 1 2
A 0 0 1 1
B 0 1 1 1
1
1

B 1 2 3 4 1 2 3
C 2 1 0 2
D 3 1 1 1
1
3
c(A,B)

C 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
c(A,C)
c(B,C)

D 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1
c(A,D)
c(B,D)
c(C,D)
MiniMax & Constraint Processing: The 4 Houses problem

CONSTRAINT PROCESSING: NO-

GOODS
 Constraint Processing: No-goods
• {A=1}: No-good
– No value for D such that A = D + 1
• {A=2,B=2}: No-good
– A and B should have different houses
• {A=2,B=3}: Not a no-good: {A=2,B=3,C=4,D=1}
• {A=2,B=3,C=1}: No-good
– A = D + 1, thus D = 1, but C = 1
• {A=2,B=4}: No-good
– A = D + 1, thus D = 1, thus C = 3, but C cannot be 3
MiniMax & Constraint Processing: The 4 Houses problem

PROBLEM
 Problem
• Intelligent backtracking:
– Obtained No-goods:
• {A=1},{A=2,B=2},{A=2,B=3,C=1},{A=2,B=4}
– And the no-goods:
• {A=3,B=2},{A=3,B=4},{A=4,B=2},{A=4,B=3},{A=4,C=2}
• Apply standard backtracking
– Depth-first and left-to-right
– Don’t visit nodes containing no-goods
 Constraint Processing: Intelligent
Backtracking
A 1
NG
B
c(A,B)

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B
c(A,B)

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1
c(A,B)

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1 2
c(A,B) NG

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1 2 3
c(A,B) NG

C
c(A,C)
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1 2 3
c(A,B) NG

C 1
c(A,C) NG
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1 2 3
c(A,B) NG

C 1 2
c(A,C) NG
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1 2 3
c(A,B) NG

C 1 2 3
c(A,C) NG
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1 2 3
c(A,B) NG

C 1 2 3 4
c(A,C) NG
c(B,C)

D
c(A,D)
c(B,D)
c(C,D)
 Constraint Processing: Intelligent
Backtracking
A 1 2
NG
B 1 2 3
c(A,B) NG

C 1 2 3 4
c(A,C) NG
c(B,C)

D 1
c(A,D)
c(B,D)
c(C,D)
MiniMax & Constraint Processing: The 4 Houses problem

EFFICIENCY
 Efficiency
All (One solution) Opened Nodes Checks
Standard
28 (13) 142 (56)
Backtracking

Backjumping 21 (8) 93 (30)

Backmarking 28 (13) 79 (34)

Intelligent
6 (4) 16 (9) + NG
Backtracking