Description
For this project, you will write a recursive backtracking program to solve the
knight’s tour problem as described in exercise 19 on page 393 of your textbook “Data
Structures Using C++”. You have been provided template code that you must modify to complete this assignment. Specifically, you will implement the following two
functions:
void KnightsTour::move(int row, int col, int& m, int& num tours) :
move is a recursive backtracking function that will print all solutions to the
knight’s tour problem on a chessboard starting from positions row, col. The
total number of tours found is returned in the reference variable num tours.
In this function, m is an integer that represents the current move of the tour
(moves are labeled starting from 1). It is incremented at the beginning of each
call to move to indicate at what point along the tour the knight reached the
chessboard cell at indices row, col. In each call to move, you will record the
value of m in the private member variable board at position row, col. Next,
you will find all valid knight moves reachable from position row, col using the
function get moves. For each new move found from get moves, recursively call
move to find all remaining tours.
When m equals the total number of cells in the private member variable board,
it means a tour has been completed. Every time a tour has completed, you will
print board using the provided function print.
void KnightsTour::get moves(
int row, int col,
int row moves[], int col moves[],
int& num moves
) :
get moves is used to find all valid knight moves reachable from board indices
row, col. An invalid move would be one that sends the knight off the edge of the
board or to a position that has already been visited in the tour.
row moves and col moves are arrays used to store the indices of all new valid
moves found. num moves is used to indicate how many valid moves were found.
In other words, num moves records the sizes of row moves and col moves.
To ensure that everyone’s output remains consistent with the test cases used in
grading, check all valid moves in a CLOCKWISE FASHION starting from the
move in which the knight travels two squares to the right and one square up.
In this project, your are only required to find tours on a 5×5 chessboard starting
at locations specified by the user. The driver program to setup this chessboard and
accept user input has already been provided. There is no need to modify it.
1
Input
Find all knight’s tours for a 5×5 chessboard starting from indices 0 ≤ r < 5 and
0 ≤ c < 5. r and c are to be passed in as command line arguments. (A driver program
has already been implemented for you).
Output
Print the solution for every knight’s tour found starting from position r, c along with
the total number of tours t. (Remember to call print inside move).
Sample Test Cases
Test Case 1
$ ./a.out 3 3
23 4 11 16 25
12 17 24 5 10
3 22 9 18 15
8 13 20 1 6
21 2 7 14 19
21 4 11 16 19
12 17 20 5 10
3 22 9 18 15
8 13 24 1 6
23 2 7 14 25
...
21 14 3 8 23
4 9 22 13 2
17 20 15 24 7
10 5 18 1 12
19 16 11 6 25
Number of tours: 56
Turn In
Submit your source code through blackboard. If you have multiple files, package them
into a zip file.
Grading
Total: 100 pts.
2
• 10/100 - Code style, commenting, general readability.
• 05/100 - Compiles.
• 05/100 - Follows provided input and output format.
• 80/100 - Successful implementation of the knight’s tour backtracking algorithm.
3
