## [Part8] Search

##### Question 1: Conflict-Ordering Search

Consider seven variables X, Y, Z, A, B, C, D such that:

• X, Y, Z have the domain $$\{0, 1\}$$ and there are no constraints on these variables.
• A, B, C, D have the domain $$\{0, 1, 2\}$$ and there is a single constraint: A, B, C, D are all different, implemented using forward checking.

Consider a conflict-ordering search that, by default, considers the variables in the order given above (first X, then Y, then Z, then A, then B, ...) and always tries, given a selected variable V, Equal(V, V.min()) on the left branch, and NotEqual(V, V.min()) on the right branch.

There are no solutions. How many nodes will be visited by the solver?

Hint: Draw the tree.

##### Question 2: Last-Conflict Search and Conflict-Ordering Search

Select all the true statements:

##### Question 3: Discrepancy

What is the discrepancy limit to generate this binary search tree?

##### Question 4: First-Fail Principle

Select all variable selection heuristics that are not in the spirit of the first-fail principle:

##### Question 5: Search-Tree Size

Consider a model with 10 decision variables X1, X2, ..., X10 and the AllDifferent([X1,X2,...,X10]) constraint. Select all the true statements:

##### Question 6: Value Selection Heuristics

Select all the true statements: