CS 127: Data Structures

Assignment: Knights Around the Chessboard

Assigned on Friday, 10/18.
No design document due because of midterm break. I strongly recommend that you start early.
Final program due electronically on Friday, 10/25 at 4 PM. Be aware that the labs in the CMC close 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. Your task is to write a program that uses backtracking to find such a sequence.

Submission Details

You should submit a program called "knights.cpp" that displays such a sequence on the screen. Each spot on the chessboard should have a number that indicates its position. 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.

Running Quickly

Your recursive code could take significant amounts of time to run quickly on an 8x8 chessboard (or larger). To receive full credit, your code only needs to run on a 5x5 chessboard and should take no longer than 2 minutes to run on one of the newer departmental machines (e.g. those in CMC 306).

If you would like an extra challenge, try to get your code to run in under 2 minutes on an 8x8 chessboard. A good method is to order the list of squares to which the knight 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. This will speed up your code considerably.

Have fun and good luck!