• Knights Tour 4 x 4, Version 1
• Knights Tour 4 x 4, Version 2

This part of the assignment requires you to create rules that define move(X,Y) for the 8 x 8 chessboard. Your solution should define the 8 types of knight moves (rather than relying on an exhaustive list of the individual moves).

Make sure you modify the comments in the program to reflect your solution. Provide a listing of your source code and a trace that shows that your solution works properly on the following examples:

	path(2,15).
	path(1,63).

Incorporate your solution to Part 1 into the heuristic search program, whose main program is given in knight.heur.pl. This program makes use of several other PROLOG programs that you need to download by clicking on the following links:

• bf.pl -- an implementation of best first search
• pq.pl -- an implementation of a priority queue
• set.pl -- an implementation of a set data structure

Recall that best-first search uses a heuristic/3 predicate. By setting that predicate's 3rd parameter to 0, you can perform an exhaustive breadth-first search using your knight moves. For this assignment you will just do a breadth-first search.

Incorporate your solution in Part 1 into the best-first search program. Just replace the name of your file for the 'knights16v2.pl' file in the setup/0 predicate. To run this program, you must first run the setup/0 predicate. Then run start(X,Y), replacing X and Y with the starting and ending numbers for the knight's path. The program should perform a breadth-first search using your moves and print out a solution path. Again, to perform breadth-first you must set heuristic(_,_,0). In the next assignment you will replace breadth-first with a heuristic search by defining a non-trivial version of heuristic/3.

HAND IN DIRECTIONS:

• Hand in a printed copies of your PROLOG programs. They should contain comments that describe the problem and your solution and document your predicate definitions.

• Hand in a copy of your Unix xterm session showing a copy of your PROLOG sessions for Part 1 and 2. You should annotate your trace to show where it demonstrates that each of the required predicates works properly. Note: You needn't run your program with the PROLOG trace turned on. Just a copy of your program's output will suffice.

  To make a copy of your PROLOG sessions, you use the Unix script command:

   $ script sfilename               //  a copy of your session will be saved
   bash$ prolog                     //  script changes the unix prompt
   ?-                               // Do your PROLOG thing.
   ?- ...
   ?- ^D                            // exit PROLOG
   bash$ ^D                         // control-D exits from script
   Script done. File is sfilename.
   $lpr sfilename                   // print your script and annotate it