Twan

11-06-2006, 11:08 AM

Hi there everyone. I haven't been here in awhile but I recently came across a problem in computer science that I am looking for some guide in.

Here's my problem:

One of the more interesting puzzlers for chess buffs is the Knight’s Tour problem. The question is this: Can the chess piece called the knight move around an empty chessboard and touch each of the 64 squares once and only once? We study this intriguing problem in depth here.

The knight makes L-shaped moves (over two in one direction and then over one in a perpendicular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in Fig. 4.30 .

a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight’s Tour by hand. Put a 1 in the first square you move to, a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate?

b) Now let us develop a program that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is initialized to zero. We describe each of the eight possible moves in terms of both their horizontal and vertical components. For example, a move of type 0, as shown in Fig. 4.30 , consists of moving two squares horizontally to the right and one square vertically upward. Move 2 consists of moving one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The eight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows:

horizontal[ 0 ] = 2

horizontal[ 1 ] = 1

horizontal[ 2 ] = -1

horizontal[ 3 ] = -2

horizontal[ 4 ] = -2

horizontal[ 5 ] = -1

horizontal[ 6 ] = 1

horizontal[ 7 ] = 2

vertical[ 0 ] = -1

vertical[ 1 ] = -2

vertical[ 2 ] = -2

vertical[ 3 ] = -1

vertical[ 4 ] = 1

vertical[ 5 ] = 2

vertical[ 6 ] = 2

vertical[ 7 ] = 1

Let the variables currentRow and currentColumn indicate the row and column of the knight’s current position. To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the statements

currentRow += vertical[ moveNumber ]; currentColumn += horizontal[ moveNumber ];

Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chessboard. Run the program. How many moves did the knight make?

/*

===================================

File: prg0342.cpp

Mod: D

Date: 9/19/2006

===================================

*/

#include <iostream.h>

#include <cstdlib.h>

#include <ctime.h>

#include <math.h>

int board [8][8] = { { 0 }, { 0 } };

int horizontal [8];

int vertical [8];

int currentRow = 3;

int currentColumn = 4;

int main ()

{

int moveNumber = 0;

horizontal[ 0 ] = 2;

horizontal[ 1 ] = 1;

horizontal[ 2 ] = -1;

horizontal[ 3 ] = -2;

horizontal[ 4 ] = -2;

horizontal[ 5 ] = -1;

horizontal[ 6 ] = 1;

horizontal[ 7 ] = 2;

vertical[ 0 ] = -1;

vertical[ 1 ] = -2;

vertical[ 2 ] = -2;

vertical[ 3 ] = -1;

vertical[ 4 ] = 1;

vertical[ 5 ] = 2;

vertical[ 6 ] = 2;

vertical[ 7 ] = 1;

for (int counter = 1; counter < 64; counter++)

{

moveNumber++;

if (moveNumber > 7)

moveNumber = 0;

currentRow += horizontal [ moveNumber ];

currentColumn += vertical [ moveNumber ];

if (board[ currentRow ][ currentColumn ] != 0 || currentRow > 7 || currentColumn > 7 || currentRow < 0 || currentColumn < 0)

{

currentRow -= horizontal [ moveNumber ];

currentColumn -= vertical [ moveNumber ];

moveNumber++;

}

else

board [ currentRow ][ currentColumn ] = counter;

cout << "The current row is " << currentRow << " and the current column is " << currentColumn << "." << endl;

}

return 0;

}

The program isn't running properly, but I'm pretty sure I'm doing everything needed. I'm not asking for code, just some direction so I can fully understand it myself.

Here's my problem:

One of the more interesting puzzlers for chess buffs is the Knight’s Tour problem. The question is this: Can the chess piece called the knight move around an empty chessboard and touch each of the 64 squares once and only once? We study this intriguing problem in depth here.

The knight makes L-shaped moves (over two in one direction and then over one in a perpendicular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in Fig. 4.30 .

a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight’s Tour by hand. Put a 1 in the first square you move to, a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate?

b) Now let us develop a program that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is initialized to zero. We describe each of the eight possible moves in terms of both their horizontal and vertical components. For example, a move of type 0, as shown in Fig. 4.30 , consists of moving two squares horizontally to the right and one square vertically upward. Move 2 consists of moving one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The eight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows:

horizontal[ 0 ] = 2

horizontal[ 1 ] = 1

horizontal[ 2 ] = -1

horizontal[ 3 ] = -2

horizontal[ 4 ] = -2

horizontal[ 5 ] = -1

horizontal[ 6 ] = 1

horizontal[ 7 ] = 2

vertical[ 0 ] = -1

vertical[ 1 ] = -2

vertical[ 2 ] = -2

vertical[ 3 ] = -1

vertical[ 4 ] = 1

vertical[ 5 ] = 2

vertical[ 6 ] = 2

vertical[ 7 ] = 1

Let the variables currentRow and currentColumn indicate the row and column of the knight’s current position. To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the statements

currentRow += vertical[ moveNumber ]; currentColumn += horizontal[ moveNumber ];

Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chessboard. Run the program. How many moves did the knight make?

/*

===================================

File: prg0342.cpp

Mod: D

Date: 9/19/2006

===================================

*/

#include <iostream.h>

#include <cstdlib.h>

#include <ctime.h>

#include <math.h>

int board [8][8] = { { 0 }, { 0 } };

int horizontal [8];

int vertical [8];

int currentRow = 3;

int currentColumn = 4;

int main ()

{

int moveNumber = 0;

horizontal[ 0 ] = 2;

horizontal[ 1 ] = 1;

horizontal[ 2 ] = -1;

horizontal[ 3 ] = -2;

horizontal[ 4 ] = -2;

horizontal[ 5 ] = -1;

horizontal[ 6 ] = 1;

horizontal[ 7 ] = 2;

vertical[ 0 ] = -1;

vertical[ 1 ] = -2;

vertical[ 2 ] = -2;

vertical[ 3 ] = -1;

vertical[ 4 ] = 1;

vertical[ 5 ] = 2;

vertical[ 6 ] = 2;

vertical[ 7 ] = 1;

for (int counter = 1; counter < 64; counter++)

{

moveNumber++;

if (moveNumber > 7)

moveNumber = 0;

currentRow += horizontal [ moveNumber ];

currentColumn += vertical [ moveNumber ];

if (board[ currentRow ][ currentColumn ] != 0 || currentRow > 7 || currentColumn > 7 || currentRow < 0 || currentColumn < 0)

{

currentRow -= horizontal [ moveNumber ];

currentColumn -= vertical [ moveNumber ];

moveNumber++;

}

else

board [ currentRow ][ currentColumn ] = counter;

cout << "The current row is " << currentRow << " and the current column is " << currentColumn << "." << endl;

}

return 0;

}

The program isn't running properly, but I'm pretty sure I'm doing everything needed. I'm not asking for code, just some direction so I can fully understand it myself.