CSE 151 Programming Assignment 1
Introduction to Artificial Intelligence

Due Thursday, April 25, at the start of class.

The 8-Queens Problem

For this programming assignment, you will construct a search algorithm that solves the 8-queens problem described in the text (page 64). Your algorithm should use depth-first search. You should write your algorithm in Lisp. Your top-level function should be called "solve-8-queens". This function should take a single required integer argument, and it should return a list of lists. Each element in the returned list should be a list containing the position (row-number and column-number) of one of the queens. Number the rows and columns from 1 to 8 (not from 0 to 7). The required numeric argument will determine which node expansion operator is used by your program, as described below.

The assignment has two parts:

  1. Test the performance of search using the following operator: place a queen in the column with the fewest unattacked squares, in such a way that it does not attack any other queens. Your program should search the space of possible queen placements using this operator when it is passed the numeric argument "0" (zero)

  2. Test the performance of search using a different operator of your own design. Try to come up with an operator that is efficient to apply (low complexity to compute) but results in fewer nodes being expanded in finding a solution. Your program should search the space of possible queen placements using this operator when it is passed the numeric argument "1" (one). If you work in a group (see below), your will be implementing one additional operator for each group member. In this case, your program should also accept the numeric arguments "2" (if there are two people in your group) and "3" (if there are three people in your group) and use your second and third operators (respectively) in searching for queen placements.
For both parts of the assignment, your program should print out the numeric value of the input argument, the number of nodes expanded, the amount of cpu time expended, and the final solution. The final solution should look something like this: 
			******Q*
			*Q******
			****Q***
			*******Q	Almost a solution
			*****Q**
			***Q****
			**Q*****
			Q*******
The program you turn in should not print out pages and pages of debug information.

If you work in a group, each person in the group should come up with an operator in part 2, above. So, if there are three people in your group, you should report on a total of four operators (including the "zero" operator provided). These different operators should be used when calling your "solve-8-queens" function with integer arguments greater than zero. Clearly specify in both inline comments and in your write-up (see below) the name of the group member responsible for each operator. Also, provide the number of people in your group in your Lisp code by defining the special variable "*group-size*" to be the number of people in your group, as follows:

(defvar *group-size* 3)

If you work alone, define this special variable to be "1".

Hint: Try to design your algorithm so that adding a new operator is easy. This will make doing the second part of the assignment much easier. For fun, you might want to try testing more than one operator of your own design. Feel free to experiment and to include the timing results for any additional operators you may try.

What To Hand In

You may work alone or in groups of up to three people on the programming assignments (including this one).

Turn in the code using the turnin utility by the date and time given above. This is done by placing all of your Lisp code into a single source code file called, say, "queens.lisp", and then executing:

% turnin -c cs151s queens.lisp

The turnin program will print out some messages, including the size of the file submitted. Make sure that this size is reasonable (and that you haven't turned in something else by mistake). Make sure that the names and login IDs of all group members appear clearly in a comment at the top of your source file.

When working as part of a group, only one group member needs to submit the group's source code using turnin. Just make absolutely sure that all group members have their names and login IDs in a header comment in that file.

Each group should also bring to class and hand in a full listing of the code which should include comments showing where in the code each of the operators is and what it does. In addition, each member of the group must turn in their own written document explaining how the program works and why they think the results came out the way they did. In particular, each group member should write a few paragraphs describing the different operators their code used and discussing the advantages and disadvantages of each operator (including the one given above). Make sure you clearly identify all the members of your group on everything you hand in.

Software Engineering Guidelines

All the code that you write should be high-quality. This means that you should pay attention to making it concise, elegant, and completely correct. Do not develop your software just by trial and error. Instead, follow good software engineering practice. Before you start coding, think carefully about the requirements that your code should satisfy, and about what algorithms you will use.

Find errors as much as possible by rereading your code, not just by testing. Do not be satisfied as soon as your code seems to work. Continue looking for errors and making your code more elegant and concise until you are satisfied that it is likely to be completely correct.

Your code should be well-documented. This means that there should be comments explaining the purpose, inputs, and outputs of every non-trivial function or procedure that you write, and comments explaining any tricky parts of your code. You should write comments at the same time that you write the corresponding code. Comments added afterwards are rarely as useful.

Coding Hints

Some Lisp code has been generated which provides functions for several forms of uninformed search. You may use this code, if you wish, to construct your solution to this assignment. You will still need to define a representation for chess board states, to define operator functions, and to define a goal test function. You will also need to put this all together to meet the program specification, above.

This code is offered as is with no guarantees of performance or utility. (There are a number of ways in which this code could be improved.) Use it or modify it as you will, but be sure to give credit to the author of any code that you do end up using.

This code is available either in three separate modules (files), or grouped into one big file. You must turn in only one file which contains all Lisp code needed to run your program. Do not expect the graders to have access to the code provided here, and do not turn in more than one file. The available code includes:

These three files have also been grouped into one big file called city_all.lisp.

Note that you can time a run of the "find-route" function using the Common Lisp "time" macro.

Please direct questions and bug reports to dnoelle@cs.ucsd.edu.

Grade Statistics 

------------------------------------------------------------
 Under Range    In Range  Over Range         Sum
           0          14           0    1120.000
------------------------------------------------------------
        Mean      Median    Midpoint   Geometric    Harmonic
      80.000      92.500      63.500      76.054      70.870
------------------------------------------------------------
          SD   Quart Dev       Range     SE mean
      22.271      13.500      63.000       5.952
------------------------------------------------------------
     Minimum  Quartile 1  Quartile 2  Quartile 3     Maximum
      32.000      68.000      92.500      95.000      95.000
------------------------------------------------------------
        Skew    Kurtosis
      -1.075       2.513
------------------------------------------------------------
   Null Mean           t    prob (t)           F    prob (F)
       0.000      13.440       0.000     180.645       0.000
------------------------------------------------------------


Histogram:

       Midpt    Freq
      37.500       2 **
      48.500       0 
      59.500       1 *
      70.500       1 *
      81.500       1 *
      92.500       9 *********

[--------------------------------------]
Tuesday, 14 May 1996, 00:00:00 GMT
Tim Bailey & David Noelle / tbailey@sdsc.edu & dnoelle@cs.ucsd.edu