1) Create a 5x5 matrix in C++

2) The matrix is initialized to all 0's showing no traversal yet.

3) Cur_Row and Cur_Col as 2 integer values representing the location of the Knight. Depending on where you start it might be 3 3 or 5 5 or 1 1 or 8 8.

4) Cur_Move is the current move number starting at 1 and being incremented each move.

5) There are 8 possible moves from the current location but not all are valid but must be considered.

Cur_Row=+2 Cur_Col=+1

Cur_Row=+2 Cur_Col=-1

Cur_Row=-2 Cur_Col=+1

Cur_Row=-2 Cur_Col=-1

Cur_Row=+1 Cur_Col=+2

Cur_Row=+1 Cur_Col=-2

Cur_Row=-1 Cur_Col=+2

Cur_Row=-1 Cur_Col=-2

6) Each valid move place the value of Cur_Move in the matrix at Cur_Row, Cur_Col and increment Cur_Move

7) The search space could be a tree or stack just like in the water jug problem. Only nodes are expanded in the tree if the value of Cur_Row and Cur_Col are less than the value of the max size of the matrix and the value at the location is 0 (unvisited).

For a 5x5 here are 2 solutions with the order of locations visited listed

1) starting location in the middle at 3 3

3 3, 1 4, 2 2, 4 1, 5 3, 4 5, 2 4, 1 2, 3 1, 5 2, 4 4, 2 5, 1 3, 2 1, 4 2, 5 4, 3 5, 2 3, 1 5, 3 4, 5 5, 4 3, 5 1, 3 2, 1 1

2) starting at bottom corner 5 5

5 5, 3 4, 1 5, 2 3, 1 1, 3 2, 5 1, 4 3, 3 5, 1 4, 2 2, 4 1, 3 3, 5 4, 4 2, 2 1, 1 3, 2 5, 4 4, 5 2, 3 1, 1 2, 2 4, 4 5, 5 3

Write a program using this representation to perform the knights tour. The result should be the matrix with the values showing the move that the square was visited. There might be other valid solutions but I know this one is valid. Define the search of the space and how to handle backtracking.

The output matrix for case 1 is:

25 8 13 2 19

14 3 18 7 12

9 24 1 20 17

4 15 22 11 6

23 10 5 16 21