Due dates: WARNING 3 different deadlines.

1. Problems 1 & 2:  Friday, Feb 18, 2000 at the beginning of the class.
2. Problem 3 Tasks 1 and 2: Monday, Feb 21, 2000, before 6:00 p.m.
3. Problem 3 Tasks 3, 4, 5, 6 & 7 (grad only):  Monday, February 28, 2000 before 6:00 p.m

1. suppose that we run a greedy search algorithm with h(n) =  - g(n).  What sort of search will the greedy search emulate? Explain.
2. suppose that we run a search algorithm with h(n) =  g(n).  What sort of search will the greedy search emulate? Explain.

Problem 3:  LISP programming assignment.

The goal of this exercise is to implement a backtrack-search mechanism in Common Lisp and test basic techniques of Constraint Satisfaction.
It consists of two parts:  Tasks 1 to 6 are for both undergrad and graduate students, and Task 7 is for graduate students only.  Undergraduate students  are welcome to implement Task 7 and will receive the credit as a bonus for the homework component of the final grading.

In this exercise, you need to implement various data structures in Common Lisp for solving the n-queens problem and implement a backtrack depth-first search that takes as input an integer n and solves the corresponding n-queens.

We are going to use the following formulation for the n-queens as a CSP:  the variables are the queens Q1, Q2, ..., Qn, one queen per line of the chessboard. The domain of each variable is the set of n columns in the line corresponding to the queen.  For the queen k,  this set is {(k, 1), (k, 2,), (k, 3), ..., (k, n)}.  Two queens attack each other if they are in the same column, same line or same diagonal  The goal is to find a position for all queens such as queens do not attack each other.

Tasks:

1. Implement depth-first search with backtracking and back-checking for finding one solution.
2. Generate one solution for n=1, 3, 4, 5, and 8.  Report the solution, the number of nodes expanded and the number of constraint checks carried out.  A constraint check is counted one every time you check the consistency of one variable's value against another one.
3. Implement an arc-consistency algorithm (choose AC-3 from Bartak's web page).  Run AC-3 on the 5 n-queen instances we have tested above (i.e., n = 1, 3, 4, 5, 8).  Report whether or not values have been pruned and, in any, the number of values pruned.
4. Implement a full look-ahead search mechanism by interleaving each variable instantiation with consistency filtering carried over all future variables.  (Note: forward checking is a partial look-ahead schema in which arc-consistency is not checked among all future variables but only for a future variable against  future variables deeper in the tree.)
5. Generate one solution for n=1, 3, 4, 7, and 8.  Report the solution, the number of nodes expanded and the number of constraint checks carried out.
6. Modify your final backtrack search to find all solutions.  Report the solutions, the number of nodes expanded and the number of constraint checks carried out.
7. (AIMA 4.12, but only partially.) Solve the n-queens problem using hill climbing  and hill climbing with random start.  Measure the search cost and percentage of solved problems using randomly generated start states.

• Input:  n, number of queens
• Create a structure for storing the queens as variables.  Use defclass or defstruct.  Each queen must have the following attributes: a unique identifier generated using  the Lisp function (gentemp "QUEEN-" ); a domain to store the set of values; and a current domain to store the domain as it is being filtered and modified by the search and consistency checking processes.
• Write a function to generate the queens and their domains given the input.
• Create a data structure for the nodes of the search tree with the following attributes: a unique identifier generated using  (gentemp "NODE-" ), a pointer to the CSP variable, an assigned value, a list of children nodes (not needed really if you are going to find one solution, may be useful while looping for all solutions, your choice).
• Write a list function for checking whether two positions on the board (a, b) and (c, d) threatens each other or not (the function threatens you saw in HW2 is useful but has a bug, a little one.
• Any time you backtrack, you need to restore the domains of the future variables by using the unaltered domains stored in the structure of the CSP variable.  In full look-ahead, before you restart search (after the backtrack step) you need to filter again the domains of all future variables by checking against the past variables and by doing arc-consistency over all future varaibles.

Step, trace, and inspect are functions of Common Lisp, and available on any CL implementation.  Check LWH: Chapter 10.
Composer is an enhanced environment for LISP code development that comes with Allegro Common Lisp of Franz Inc.  It has a window-based inspector, debugger, on-line documentation, profiler, xreference, etc..
To load composer, when your ACL image contains composer, type in a common-lisp buffer:  (require 'composer).
Then type (composer:start-composer) (alternatively, you can start composer from the menu buttons on top of your xemacs window.)
To inspect a variable var, you can type :wi var  (this stands for window inspect var).
To enter the debugger (once you are in a break loop because of the some bug), you can type  :wde, and a window will appear with the last instructions.