CS 127: Data Structures

Assignment 4: Knights Tour

Assigned on Friday, 10/5/01.
Design document due on paper at the beginning of class on Monday, 10/8/01.
Final program due electronically on Tuesday, 10/16/01 at 5 PM.

Overview

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 program that uses backtracking to find such a tour.

Submission Details

You should submit a program called "knights.cpp" that displays a knight's tour to the screen. Each spot on the chessboard should have a number that indicates its position in the tour. Assume that the first position, position "1", is in the top left corner of the board. For example, here is one possible solution your code might find:

   1    8   15   22    3   10   19   64
16   23    2    9   18   21    4   11
   7   14   17   24    5   12   63   20
34   25    6   13   44   27   52   61
55   46   33   26   53   62   43   28
32   35   54   45   40   29   60   51
47   56   37   30   49   58   39   42
36   31   48   57   38   41   50   59

Your code should print out a solution in a format similar to the above.

Programming Details

Recall that a knight's move is to jump two positions either vertically or horizontally and one position in the perpendicular direction. Such a move can be accomplished by setting x to either 1 or 2, setting y to 3-x, and then changing the first coordinate to be +x or -x and the second coordinate to be +y or -y (provided that the resulting position is still on the board).

When debugging your program, run it on a smaller size chessboard so that it runs faster. There is a valid tour on a 5x5 chessboard.

Optional Extra Functionality

If want to speed up the program, a good method is to order the list of squares to which it can move from a given position so that it will first try to go to the squares with the least accessibility, that is, to the squares from which there are the fewest knight's moves to squares not yet visited.

Have fun and good luck!