A popular chessboard puzzle (reputedly solved by Gauss at the age of four) is to find a sequence of moves by a knight that will visit every square of the board exactly once. Such a sequence is generally referred to as a knight's tour. Your task is to write a LISP program that uses backtracking to find such a tour.
Part 1
Your task is to a program that searches for a knight's tour of a chess board. From any starting square, find a sequence of legal knight moves that touch each remaining square exactly once. A knight moves either two squares vertically and one square horizontally, or one square vertically and two squares horizontally. From the square marked with 0, a knight can potentially move to any of the eight squares marked with 1.
..1.1.. .1...1. ...0... .1...1. ..1.1..Naturally, some of these possibilities may be limited by the edges of the board.
Your top-level function find-knights-tour will have 4 arguments: the number of rows and columns in the chessboard, and the knight's initial position row and column on the chess board. The find-knights-tour function should return a list of chessboard positions showing the tour, or nil if none exists (such as in the case of a 2x2 chessboard). For example consider the 5x6 chessboard below:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4
To find a knights tour for a 5x6 chessboard, staring at position (1,1), you would invoke the find-knight-tour function:
(find-knights-tour 5 6 1 1)The solution tour will be a list like
(A N Y U 3 R E P 1 S H D L W J F Q 4 V Z M B O 2 X K C G T I )Note: In your code, you won't use the letters A-Z and numbers 1-4. They are only shown here for illustration purposes. Instead, you will return a list of positions, i.e. the actual solution will be
((1 1) (3 2) (5 1) (4 3) ... (2 3))
Try to minimize the number of auxiliary functions that you need. Try your program chessboards of size 3x3,5x6, 6x6, 5x8, 8x8, and 12x3. starting a position (1,1). (Note: There is no valid tour for the 3x3 chessboard case.) Important Note: For part 1, you may run out of stack space on anything bigger than a 3x4 chessboard on the SEAS machines. If you get a stack overflow error, you can try compiling your code before executing it. When the LISP compiler compiles code, it does optimization to change tail recursion to iterative expressions; thus saving stack space. After compiling your LISP code on the SEAS machine, you should be able to solve a 7x7 in about 20 minutes. assignment.
To compile the code, do the following:
$ gcl >(compile-file "hw3.lsp") ;;; There should be some lisp output here. >(load "hw3.o") >(find-knights-tour 5 5 0 0)
Part 2
Define and implement a heuristic that would order the choices of potential moves to reduce the search time and space for the knights tour problem. Call the revised function that utilizes the heuristic find-knights-tour2. Again, try this function on program chessboards of size 3x3, 5x6, 6x6, 5x8, 8x8, and 12x3 starting a position (1,1).
You should be able to solve part 2 (e.g. a 8x8 knights tour problem) without compiling. With compiling, you should be able to solve up to a 20x20 tour within a minute.