Skip to main content
ICT
Lesson AB23 - Two-Dimensional Arrays
 
Main   Previous
 

LAB ASSIGNMENT AB23.3 page 9 of 9

Knight’s Tour 2

Background:

Rather than trying a random approach to solve for the next move, we will develop an algorithm that uses some information and logic that we have about each square. As you played the game in Lab Assignment AB23.2, Knight’s Tour 1, you should have noticed that the edges were much more difficult to visit and the corners were the most difficult of all. If we analyze each square, we 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 accessibility 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 this accessibility strategy. In determining the next move, the knight should move to an available square with the lowest accessibility value. In the case of a tie, you can move the knight to any of the tied squares.

  2. The original accessibility information is stored in an 8-line text file named access.txt. Each line consists of the 8 accessibility numbers for that line, separated by blank spaces, terminated with the enter 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 that can be reached from location[4][5] should have their accessibility values reduced by 1.

  4. Proper decomposition of the problem into single-purpose methods will be of great importance in this lab assignment.

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

 

Main   Previous
Contact
 © ICT 2006, All Rights Reserved.