CMSC 471

Artificial Intelligence -- Fall 2010

HOMEWORK TWO
out 9/14/10; due 9/30/10

http://www.cs.umbc.edu/courses/undergraduate/471/fall10/hw/hw2.html

A Knight's tour starts by placing a Knight on a chess board. The Knight then makes a sequence of legal moves (according to the rules of chess) in which it touches each square exactly once. Note that starting on a square counts as touching it. Your task for this homework is to write generic search code that can be made to perform either depth-first search or breadth-first search and use it to solve the Knight's tour problem for chess boards of different sizes.

The following are required of your solution:

Your code must be written in Lisp.
The top level search routine must take two arguments, an object that contains information on the problem to be solved and an object the contains information on the search method. See slide 27 of the lecture notes on search for a template for such a generic method.
The search problem object must have a slot for the size of the chess board, N, which is square (i.e., it will have N*N squares).

You should turn in the following:

A printout of your source code.
Email a single lisp file with all of your source code to the TA.
A plot of the number of nodes expanded for depth first search for various values N. Choose enough different values of N to convey some sense of the computational complexity of DFS for this problem.
A plot as described above for breadth first search.
A short (1 - 2 paragraph) writeup explaining why the plots look the way they do, being sure to explain either differences or similarities in terms of what the search algorithms are doing.

Now for some advice!

You'll probably want to use CLOS, the Common Lisp Object System, that allows you to define objects (like class in Java). There are several good introductions to CLOS on the web. I like this one.

You can define a generic search class like this:

  (defclass generic-search ()
    ((nodes :accessor nodes :initform nil)))

This defines a class named generic-search with one slot that is intialized to be an empty list (:initform nil) and can be accessed by a function named nodes. For example, try this code:

(setf x (make-instance 'generic-search))
(nodes x)
(setf (nodes x) '(1 2 3))
(nodes x)

This can be specialized for DFS like this:

  (defclass DFS (generic-search) ())

This class inherits the slot above. Now we can define a method that takes a DFS object and a node as arguments and enqueues the node for DFS:

(defmethod enqueue-node ((searcher DFS) node)
  (push node (nodes searcher)))

A similar method to dequeue a node would look like this:

(defmethod dequeue-node ((searcher DFS))
  (pop (nodes searcher)))

Now you can define a BFS object and methods named enqueue-node and dequeue-node for it, like this:

  (defclass BFS (generic-search) ())

(defmethod enqueue-node ((searcher BFS) node)
 ...)

(defmethod dequeue-node ((searcher BFS))
 ...)

Then if you have a variable that is either a BFS or DFS object and call, say, enqueue-node on it, Lisp figures out the type and calls the right method! So you just code your search routine in terms of calls to enqueue-node and dequeue-node and pass in either a DFS or BFS object depending on which type of search you want.

Putting it all together, your top level code to test the entire thing might look like this:

(setf problem (make-instance 'knights-tour-problem :n 10))
(setf searcher (make-instance 'DFS))
(setf DFS-nodes (search problem searcher))
(setf searcher (make-instance 'BFS))
(setf BFS-nodes (search problem searcher))

CMSC 471

Artificial Intelligence -- Fall 2010

HOMEWORK TWO out 9/14/10; due 9/30/10

HOMEWORK TWO
out 9/14/10; due 9/30/10