Lab 23.2 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. Each turn, the knight will pick a random valid move to make, with each valid move being equally likely. Hint: make a list of valid moves and then pick randomly from that list.

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

5. 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
   

6. Each time you run the program you should get different results. If you keep getting the same squares visited, then you are not choosing randomly.

Suggestion

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:

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.

You must Sign In to submit to this assignment