In C++. Thanks.

Knight's Tour:

In the game of (International) Chess the knight moves in an unusual pattern of 2 squares horizontally and then 1 square vertically or 2 squares vertically and then 1 square horizontally. The 8 possible moves for a knight are shown below:

		8		1
	7				2
			Kn
	6				3
		5		4

Somewhere along the line the question was asked: Could a knight move to every location on a chess board without ever landing on a square more than once. This challenge is known as the Knight's Tour.

Your assignment is to come up with a recursive solution to the Knight's Tour. As your knight travels the board record the squares that he has touched by storing the move count, so for example the first square that the knight starts from would be marked with a 1 and the next square that the knight moves to would be marked with a 2 and so on until on a normal 8x8 chess board the knight moves to the last square and stores a 64 there......the knight would have them completed his tour. For this assignment, it is ok to use some global variables for recording some of the statistics you may want ( move count, tries, board, ect ).

Remember in recursion you call a function to solve a problem, then the function will call itself to solve the next step of the problem. This will go on until the function gets to some ending solution. In this case, your function would be a move for the knight, and it would call itself for the next place to try moving to, which would call itself for the next place to move, and so on, and so on.

Programming Note:

• Think about what information needs to be passed into the function and what information needs to be returned from the function.
• What are the things that you need to do in a square?

For output from the program, you need to print out a map of where the knight visited in his tour. Here is an example of a Knight's Tour for a 5x5 board starting from the upper left corner:

Yeehaw!!! after 41 tries and 16 bad moves 1 20 17 12 3 16 11 2 7 18 21 24 19 4 13 10 15 6 23 8 25 22 9 14 5 

I do also want you to display the number of tries (these were squares the knight actually moved i.e. an empty square on the board).

Debugging Suggestions: For debugging use a 5x5 board to see if the recursive calls are working. This is nice for following the algorithm for a few moves. Have the board print out after each move when you are first testing to verify that your algorithm is working. Once you are convinced your algorithm is good, you can have the board printed periodically to give you an update ( I had mine print out after every 10 million tries... some of the tours on an 8x8 board can take a while.... starting at location 4, 4 (when first row and col are 0) the program ran over night and had tried 62,200,000,000 moves and had a ways to go before solving it with this brute force algorithm). The solution for a tour starting at 0,0 did not take that long; and only took 3,242,065 tries to find the solution.

I solved the problem by using a function prototype like the following:

bool moveKnight( int row, int col, int movNum);

The boolean return value I used as a signal of the results of the function; false meant this call could not move further, true meant that the end was found (eventually) from this move. This is just a way of thinking of it, and your are not required to have the same function prototype.