Knight's Tour 1

Background:

The Swiss mathematician Leonhard Euler (1707 - 1783) proposed a problem regarding the movement of the knight chess piece on a chess board. The challenge that Euler proposed was to move the knight around an empty chessboard, and to touch each of the 64 squares once and only once. Directions: To start, move the knight from any position on the board using its standard L-shaped moves (two over in one direction, then one in a perpendicular direction). Practice on this empty grid. Number any position as 1 and then visit as many squares as possible, numbering each move as you go:

This task is much more difficult than it first appears!

Assignment:

Your task in this lab is to write a program that will move a knight around an empty chess board, leaving behind a trail of increasing integers, ranging from 1 to, hopefully, 64. Here are the specifications for your assignment:

1. The knight will start in row 1, column 1.

2. The program will mark squares as they are visited, ranging from 1-64.

3. The program will continue until a complete tour is accomplished (all 64 squares) or the program gets stuck with nowhere to go.

4. The program will print the results, looking something like this:

       1   2   3   4   5   6   7   8

   1   1   0  21   0   0  14  23  12
2  20   0   6   9  22  11   0   0
3   7   2  19  36  15  46  13  24
4   0   5   8  47  10  37   0  45
5   0  18   3  16  35  44  25  38
6   4  31  34   0  42  39  28   0
7   0   0  17  32  29  26  43  40
8   0  33  30   0   0  41   0  27

   47 squares were visited

5. Use the Random class to generate the necessary random numbers.

6. Here are two suggestions to solve this lab.

   Suggestion 1:

   Think about the 8 different possible moves a knight can make from a square. If we analyze them, we can break each one down into a horizontal and vertical component.

Here are the 8 different possible moves analyzed as horizontal and vertical components:

Move 1 2 3 4 5 6 7 8 horizontal +1 +2 +2 +1 -1 -2 -2 -1   vertical -2 -1 +1 +2 +2 +1 -1 -2

If you stored the above data in 2 arrays, called horizontal and vertical, it would be possible to move the knight to the next square using a statement like:

row = row + vertical[moveNumber];
col = col + horizontal[moveNumber];

This kind of approach will help to simplify your program.

Suggestion 2:

Declare the board as a 9 x 9 grid. This will allow you to work with rows 1..8 and column 1..8. Row 0 and column 0 will not be used in this approach.