Programming Assignment #2: Function Recursion (Knights Tour)
Knight's Tour:
In the game of Chess (international chess, at least) 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
Knight
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 challege 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 around 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, 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.
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
Debugging Suggestions: For debugging use a 4x4 board to see if the recursive calls are working. Note: on a 4x4 board there is no solution when starting in the upper left corner, but it is still 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 of the required tour does not take that long; it only takes 3,242,065 tries to find the soltution
Turn in: A paper copy of your code with a print out of your of the tour take by your knight on a 8x8 board. For the tour you turn in, start the knight in the upper left corner. The tour can be captured from the command window (black screen) by using Select All and then Copy from the command windows menus, then you can paste your output below your programs code as a comment.
