CPSC 625
HW #3
due: Fri, 9/29/06 (in class, printed out)

These questions are based on the 4-Queens CSP.  

Use the following encoding of the problem.  Since there can only be
one queen in each column, let the variables be Q1, Q2, Q3, and Q4,
representing the queens in columns 1-4 respectively.  Each queen has
one of 4 possible rows in can be in, defining its domain.  For
example, initially Domain(Q1)={1,2,3,4}.  This representation
conveniently embeds the column constraints (so they cannot possibly
be violated, i.e. no 2 queens can be in the same column by design).

1. Write down all the remaining constraints.

2. Compute the total size of the search space (number of nodes).

3. Estimate (or count) the number of nodes checked when back-tracking
search is used (assuming the default ordering of variables and values).

4. Show a trace of the search with back-tracking, indicating which
variable or value is picked at each step and what values remain in the
domains of unassigned variables.  Indicate exactly where back-tracking
occurs, why, and to which previous node.

5a. Can the most-constrained variable (MCV) heuristic help (to reduce
search effort)?  If so, show how.  If not, explain.

5b. Give an example (e.g. by changing the order of the variables, or
picking certain values) where the MCV heuristic would make a difference 
(i.e. make the search more efficient).

6. Suppose we started by choosing Q1=2 and decide to consider Q4 next.
At this stage, Q4 has 3 possible values: Domain(Q4)={1,3,4}.  According
to the least-constraining value (LCV) heuristic, which value(s) would be 
preferred and why? (show which other values they conflict with)

7. Draw the constraint graph (and domains) for this problem.  Show a
trace of running constraint-propagation, giving in detail for each step
what is happening (propagating from what node to which neighbor; which
values from a domain are being deleted; when does back-tracking occur...).

8. The key to maximizing efficiency on this problem is to avoid as
much search as posssible, which would happen if we could only pick
Q1=2 over Q1=1 at the first step.  But none of the heuristics or
propagation techniques can help us do that.  However, AC-3 can rule out 
Q1=1 fairly quickly.  Show how the constraint-graph is processed by
AC-3, and how enforcing arc-consistency can lead to efficient search.