LAB EXERCISE

KNIGHT'S TOUR 2

Background:

Rather than trying a random approach to solve for the next move we will develop an algorithm which uses some information and logic about each square. As you played the game you should have noticed that the edges were more difficult to visit and the corners the most difficult of all. If we analyze each square we will notice that some are more accessible than others. Here is an analysis of the accessibility of each square.

A square with an accessibility of 8 means that it can be approached from 8 different other squares. A corner square is rated at 2, while the edges are rated at 3 or 4. It makes sense to try and visit squares with lower accessiblity values first, leaving the more accessible middle squares for later in the algorithm.

Assignment:

1. Write a revised version of the Knight's Tour program using the accessibility strategy. In determining the next move, the knight should move to the square with the lowest accessibility value. In the case of a tie you may move the knight to any of the tied squares.

2. The original accessibility information is stored in an 8-line text file called access.txt. Each line consists of the 8 accessibility numbers for that line, separated by blank spaces, terminated with the return key. You should read this data file to set up your starting accessibility data table. It would be a good idea to test your initialization of the accessibility table.

3. To ensure a greater degree of success, as the knight moves around the board you should reduce the accessibility numbers in the appropriate squares. For example, if location[4][5] is visited, then the 8 squares which can be reached from location[4][5] should have their accessibility values reduced by -1.

4. Proper decomposition of the problem will be of great importance in this lab exercise.

5. Turn in your source code and a run output with the highest number of visited squares.