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

The Problem

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

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 |

| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |

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 |

| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |

| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |

| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 5 |

| 1 | 4 | 0 |
| 6 | 0 | 2 |
| 3 | 0 | 5 |

| 1 | 4 | 7 |
| 6 | 0 | 2 |
| 3 | 0 | 5 |

| 1 | 4 | 7 |
| 6 | 0 | 2 |
| 3 | 8 | 5 |

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 |

| 1 | 4 | 0 |
| 6 | 0 | 2 |
| 3 | 0 | 5 |

| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 5 |

| 1 | 4 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |

| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 3 | 0 | 0 |

| 1 | 0 | 0 |
| 0 | 0 | 2 |
| 0 | 0 | 0 |

| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |

| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 2 | 0 |

Using Recursion to implement backtracking

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

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

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

• All of the code you wrote, written and documented according to rules of good style.

• A journal describing your efforts.