CSCI 220 Fall 2001, Project 1: The Knight's Tour

The Problem

The Knight's Tour problem is a chessboard puzzle in which you are to find a sequence of moves by a knight that will visit every square of the chessboard exactly once.

A knight moves by jumping two positions either vertically or horizontally, and one position perpindicular to whicher direction it moved two positions. (That is, it moves in an L shaped direction, for any rotation of the L.)

The Solution

You can find a solution to this puzzle using recursion and another problem solving method called backtracking.

The basic idea of backtracking is that you construct partial solutions of a problem (in this case a partial tour of the board) and then attempt to extend the solution. If the extended solution fails (the next square we jump to does not lead to a complete tour) then we back up and try a different partial solution (jump to a different square instead).

For example we will consider a 3 x 3 board, which does not have a valid tour, but will allow us to see how backtracking works to determine this.

An unvisited square of the board will be represented by the value 0. As we visit a square, we will mark it with the number it is in the tour.

In our example, we will start our attempted tour at row 1, column 1:

Initial Board
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |
The knight starts at (1,1)
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |
At each point in the tour, we keep a list of squares that we can reach in the next turn

In this case, there are two possible moves from the square marked 1: (2,3) and (3,2)

First we try (2,3); if moving to this square does not work, then we will backtrack and try (3,2).

| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 0 | 0 | 0 |
From this square, the knight has two possible moves: (1,1) and (3,1). (1,1) is occupied, so we immediately move on to trying (3,1)
| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |
From this square, the knight has two possible moves: (2,3) and (1,2). (2,3) is occupied, so we immediately move on to trying (1,2)
| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |
Possible moves from this square: (3,1) and (3,3)
(3,1) is occupied.
(3,3)
| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 5 |
Possible moves from this square: (2,1) and (1,2)
(2,1)
| 1 | 4 | 0 |
| 6 | 0 | 2 |
| 3 | 0 | 5 |
Possible moves from this square: (1,3) and (3,3)
(1,3)
| 1 | 4 | 7 |
| 6 | 0 | 2 |
| 3 | 0 | 5 |
Possible moves from this square: (2,1) and (3,2)
(2,1) is occupied
(3,2)
| 1 | 4 | 7 |
| 6 | 0 | 2 |
| 3 | 8 | 5 |
Possible moves from this square: (1,1) and (1,3)
(1,1) is occupied
(1,3) is occupied

No more possible moves, so the tour does not work if we place 8 in (3,2) and we back up

| 1 | 4 | 7 |
| 6 | 0 | 2 |
| 3 | 0 | 5 |
No more possible moves for 8, so the placement of 7 does not work so we back up
| 1 | 4 | 0 |
| 6 | 0 | 2 |
| 3 | 0 | 5 |
The other possible move from 6 was (3,3) which is occupied, so the placement of 6 does not work, and we back up
| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 5 |
The other possible move from 5 was (1,2) which is occupied, so the placement of 5 does not work, and we back up
| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |
There are no more choices to move from 4, so this placement of 4 fails and we back up
| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |
There are no more choices for 3, so the placement of 3 fails and we back up
| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 0 | 0 | 0 |
There are no more choices for 2, so the placement of 2 fails and we back up
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |
(3,2) is the second choice from 1, so we move to this square
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 2 | 0 |
And now the process continues. When a square can be marked we continue. If it cannot be placed we back up. In this way, all possible moves are tried. If at any point we have marked all 9 squares, we stop and print out the board. If we run out of moves from 1, we know that we have failed and output a message saying there is no tour.

Using Recursion to implement backtracking

Recursion is useful for backtracking because our attempt to extend a partial solution can be a recursive call of the function that attempts to find the total solution.

Let's call the recursive function KnightMove. It has several parameters:
Knightmove(board, row, col, movecount, success)
where board is the two dimensional board; row, col is the coordinate to which the knight is moving; movecount is the number we will place in board[row,col], and success is a boolean flag that starts with a value of false and will be set to true if movecount ever equals the number of squares on the board (indicating we've completed the tour).

The calls corresponding to our example above would be


KnightMove(board, 1, 1, 1, success)
KnightMove(board, 2, 3, 2, success)
KnightMove(board, 3, 1, 3, success)
KnightMove(board, 1, 2, 4, success)
KnightMove(board, 3, 3, 5, success)
KnightMove(board, 2, 1, 6, success)
KnightMove(board, 1, 3, 7, success)
KnightMove(board, 3, 2, 8, success)

At this point the backtracking begins as each of the calls of KnightMove, except for KnightMove(board, 1,1,1) return because they have no more moves to try.

This function now calls
KnightMove(board, 3, 2, 2, success)

and then the process continues (ultimately backing up to the top call and exiting without finding a tour).

Your Assignment

Write a program that uses backtracking to find a Knight's tour, if one exists, on an n x n board, where the user selects the board size and the starting square. The user will never select a board size of more than 10 x 10.

Your KnightMove procedure should follow the outline indicated above. The base case of the recursion is when the move counter is equal to the total number of squares in the board.

In the recursive case, you must build a list of squares the knight could move to, and then try to move to each square (by first checking to make sure it isn't occupied, and then recursively calling KnightMove with the new row, new col and adding one to movecount; if success returns with a value of true, you can stop checking, otherwise you keep going until you run out of possible moves).

Testing the algorithm

A 4 x 4 square has no solution. A 5 x 5 square has a solution beginning at square (1,1). Try these two at a minimum. (While implementing, you may want to try a 3 x 3 for the failure case.)

Once it is working, feel free to try 8 x 8, though you should be aware that tours that proving a tour doesn't exist starting from a square may take a long time (and uses lots of cpu time... :-).

Levels of Success

  1. Generate code to determine which cells can be reached from a given cell on the board in one jump of the knight. This will be used to determine which recursive calls should be made in the final solution.

    This is the minimal amount of work needed for a D on this project.

  2. Recursively touch each square of a two-dimensional array. Write a recursive function that simply starts at some cell of a two-dimensional array and moves along rows and columns in the array, until every cell of the array is touched. For example, you might start at [0,0] and proceed by next calling the function to hit cell [0,1] and then [0,2], etc. Success on this function will establish that you can generate a recursive function with the correct stopping condition (every cell has been touched) and the correct framework (the board, row and column variables, etc) the function will need to actually solve the problem.

    This is the minimal work needed for a C on this project.

  3. Combine the D and C parts of the project to implement a backtracking solution to the Knight's tour. Combining these parts means that instead of simply recursing to the next cell in the array, your recursive function goes to a cell listed in the legal moves generated, unless that cell has already been touched. Keep track of which cells have been touched by storing the current movecount (see example) in the cell.

    Unlike other recursive calls, backtracking is conditional, e.g. here is pseudocode describing the recursive calls:

    for each cell listed in legal moves
         if cell has not been touched already
             knightmove(board, moverow, movecolumn,movecount,success) 
             if (success == true) return true
    
    Notice in the above pseudocode that we might not visit every cell in legal moves (if they have been visited already) and we return true if we ever find a solution.

    If a legal tour exists, your program should output "a legal tour exists." If it does not, the program outputs, "a legal tour does not exist."

    This is the minimal work for a B on this project.

  4. Outputting solutions. Modify your code so that it
    1. Outputs the actual tour as a sequence of jumps.
    2. Allows the user the option of outputting every legal tour rather than only the first one found.

    This is the minimal work for an A on this project.

Deliverables

The handin name for this project is project1
Gary Lewandowski
Last modified: Wed Sep 19 08:52:27 EDT 2001