12.4  Exercises

For exercises 1-3, start from the constraint model for the queens problem given in section 12.2.4. It is available in the examples directory as queens_ic.ecl.

1. Use the search/6 predicate from the ic_search library and the standard model for the queens problem (given below) to find ONE solution to the 42-queens problem. With a naive search strategy this requires millions of backtracks. Using heuristics and/or incomplete search, try to find a solution in less than 100 backtracks!
2. How many solutions does the 9-queens problem have?
3. Solve the "8 sticky queens problem": Assume that the queens in neighbouring columns want to stick together as close as possible. Minimize the sum of the vertical distances between neighbouring queens. What is the best and what is the worst solution for this problem?
4. For given N, create a list of length N whose members are numbers between 1 and N (inclusive), which are all different (easy so far) and satisfy the following constraint. For each element E of the list, its successors are divided into two sets,
   • BiggerE: the successors which are greater than E and
   • SmallerE: the successors less than E.
   (Thus no successor takes the same value as E). The cardinalities of the sets BiggerE and SmallerE differ by at most 1.
5. A harder version of the problem is similar. For given N, create a list of length N whose members are numbers between 1 and some upper bound Max (start with, say Max = N²), which are all different (easy so far) and satisfy the following (more complex) constraint. For each K from 1..N, call the Kth element of the list Ek. Its successors are divided into two sets, as before:
   • BiggerEk: the successors which are greater than or equal to Ek + K and
   • SmallerEk: the successors less than or equal to Ek - K.
   (Thus no successor takes a value between Ek-K+1 and Ek+K-1.) The cardinalities of the sets BiggerEk and SmallerEk differ by at most 1.

   What is the smallest upper bound Max for which there is a feasible solution?