8. CP

8.1. Theory

• Slides

8.2. Exercises

8.2.1. N-Queens Problem: First-Fail Strategy

The N-Queens problem is the following: how to place N queens on a NxN chess board without any queen attacking each other.

Given a 6-Queens problem with one variable deciding the position of the queen in each row and the following partial assignments, which variable will be chosen next by the first-fail strategy in each case?

Partial assignment A \(q_1 = 3, q_6 = 1\)

Partial assignment B \(q_3 = 5, q_5 = 4\)

Partial assignment C \(q_4 = 2, q_5 = 4\)

8.2.2. Element Constraint and Bound vs. Domain Consistency

The Element constraint has the form \(X = C(Y)\) where \(C\) is a vector of integers and \(X\) and \(Y\) are integer variables.

Given \(dom(X) = \{0, 1, 2, 3, 4, 5\}\) and \(dom(Y) = \{0, 1, 2, 3, 4, 5\}\), and the array \(C = [2, 4, 5, 1, 2, 5]\).

1. How will the domains of \(X\) and \(Y\) evolve after imposing the constraint?

2. And after removing 5 from the domain of \(X\)?

3. For the different cases given in the table below, mention if domain consistency or bound consistency is achieved.

\(dom(X)\)	\(dom(Y)\)
\(\{0,1,2,3,4,5\}\)	\(\{0,1,2,3,4,5\}\)
\(\{1,2,3,4,5\}\)	\(\{0,2,3\}\)
\(\{2,5\}\)	\(\{0,2,5\}\)
\(\{2,3,4,5\}\)	\(\{0,1,2,3\}\)

8.2.3. AllDifferent Constraint

Given the variables \(X1, X2, X3, X4\) and their domains \(dom(X1)=\{1,3\}, dom(X2)=\{1,3\}, dom(X3)=\{1,3,8\}, dom(X4)=\{8,9\}\).

The constraint AllDifferent \((X1,X2,X3,X4)\) links them.

Justify why the value 8 should be removed from the domain of \(X4\).