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 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)
| 1 | 4 | 0 | | 0 | 0 | 2 | | 3 | 0 | 5 |Possible moves from this square: (2,1) and (1,2)
| 1 | 4 | 0 | | 6 | 0 | 2 | | 3 | 0 | 5 |Possible moves from this square: (1,3) and (3,3)
| 1 | 4 | 7 | | 6 | 0 | 2 | | 3 | 0 | 5 |Possible moves from this square: (2,1) and (3,2)
| 1 | 4 | 7 | | 6 | 0 | 2 | | 3 | 8 | 5 |Possible moves from this square: (1,1) and (1,3)
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.
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 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).
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... :-).
This is the minimal amount of work needed for a D on this project.
This is the minimal work needed for a C on this project.
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 trueNotice 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.
This is the minimal work for an A on this project.