-
September 24th, 2011, 11:39 AM
#1
Knight's tour c++
Hey guys, I am trying to complete a c++ Knight's tour program. I am getting full output but the tour stops after the first move so my output is this
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000200
00000000
00001000
00000000
00000000
00000000
00000000
I think my problem is my if else statement cluster but I can't seem to determine what went wrong. I have a sneaking suspicion it has something to do with syntax. Here is my code.
Code:
#include <iostream>
using namespace std;
const int rows = 8;
const int columns = 8;
void printArray( int[][columns]);
int main ()
{
int i, j;
int counter = 1;
int moveNumber = 1;
int currentRow = 3;
int currentColumn = 4;
int pastRow;
int pastColumn;
int chessBoard[rows][columns];
for (i = 0; i < 8; i++)
{
for (j = 0; j < 8; j++)
{
chessBoard[i][j] = 0;
}
}
printArray (chessBoard);
cout << endl;
chessBoard[currentRow][currentColumn] = counter;
counter++;
int horizontal [columns] = {2, 1, -1, -2, -2, -1, 1, 2};
int vertical [columns] = {-1, -2, -2, -1, 1, 2, 2, 1};
if (counter <= 64)
{
pastRow = currentRow;
pastColumn = currentColumn;
currentRow += vertical[moveNumber];
currentColumn += horizontal[moveNumber];
if ( chessBoard[currentRow][currentColumn] != 0)
{ currentRow = pastRow;
currentColumn = pastColumn;
moveNumber++;
}
else
{ chessBoard[currentRow][currentColumn] = counter;
counter++;
moveNumber = 1;
}
}
printArray (chessBoard);
return 0;
};
void printArray( int a[rows][columns])
{
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
cout << a[i][j] << ' ';
cout << endl;
}
}
-
September 25th, 2011, 12:15 AM
#2
Re: Knight's tour c++
Originally Posted by Seeshi_suin
I think my problem is my if else statement cluster but I can't seem to determine what went wrong. I have a sneaking suspicion it has something to do with syntax.
If it's a syntax problem the compiler will tell you and you're not going to be able to run the program at all.
The program stops after it has done what it's instructed to do. You first assign a 1 to the 3,4 position. Then you assign a 1+1 to the 3-2, 4+1 position. That's it. You don't have a loop or a recursive call or anything that would continue the program, so it terminates.
-
September 30th, 2011, 10:00 AM
#3
Re: Knight's tour c++
As nuzzle pointed out, this accomplishes nothing. What you probably want instead is a terminating base condition of counter == 64, and a for-loop that calls the method recursively for each legal move from the current position of the knight. By legal move I mean a position that is not outside the bounds of the board, and that you haven't already visited. The skeleton of a solution looks like this:
Code:
if ( counter == 64 )
{
// done, print solution
return;
}
for ( size_t i = 0; i < 8; ++i )
{
// compute newMoveRow by indexing into horizontal, adding value to currentRow
// compute newMoveCol by indexing into vertical, adding value to currentCol
if ( isLegalMove( board, newMoveRow, newMoveCol, i ) )
{
// record move on board: board[ newMoveRow, newMoveCol ] = count + 1
// recursive call, pass as parameters board, nextMoveRow, nextMoveCol, counter+1
// clear previous move: board[ newMoveRow, newMoveCol ] = 0
}
}
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|