LAB EXERCISE

 

KNIGHT'S TOUR 1

 

 

 

Background:

 

The mathematician Euler proposed a problem regarding the chess piece called the knight.  The challenge Euler proposed is to move the knight around an empty chess board, touching each of the 64 squares once and only once.  You may start the knight at any position on the board and move it using its standard L-shaped moves (two over in one direction, over one in a perpendicular direction).  Try it on this empty grid.  Number any position as 1 and then visit as many squares as possible, numbering as you go:

 

 

 

 

More difficult than it seems! 

 

 

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, col 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 your dice class developed in Lesson 12 to generate the necessary random numbers.

 

6.   Here are two suggestions to solve this lab.

 

Suggestion 1:    Here is an idea on how to deal with the 8 different possible moves.  If we analyze the possible moves we can break each move down into a horizontal and vertical component.

 

 

 

 

Here are the 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 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.

 

 

7.   Turn in your source code and a run output as described above.