Project 3 Solution

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 mod-ify to complete this assignment. Speci cally, 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 nd 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 nd 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 nd all valid knight moves reachable from board indices row, col. An invalid move would be one that sends the knight o 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 nd tours on a 5x5 chessboard starting at locations speci ed 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 5x5 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 les, package them into a zip le.


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