Problem with recursive solution of "Knight's Tour".-VBForums

# Thread: Problem with recursive solution of "Knight's Tour".

1. ## Problem with recursive solution of "Knight's Tour".

Hi,

I am working with the problem 'Knight's tour' and my program's meant to move the knight to as many squares as possible on a chess board while not re-visiting any squares. Can anoyone be kind enough to make my code work or simply post a better and simpler solution. I mean, i cna't learning anything without seeing examples, and i'm really stuck. I also tried the iterative version and still could'nt get it to work. Pls help.

Code:
```/* Knight's Tour ( recursive version ) */

#include <stdio.h>

/* 'col' = column */

int knights_tour( int startingRow, int startingCol, int moveNumber ); /* returns the number of moves made */

int out_of_bounds( int nextRow, int nextCol ); /* check if next move is off the board */

int visited( int nextRow, int nextCol, int board[][ 8 ] );       /* check if next square is visited already */

int main()
{
printf( "***Knight's Tour***" );

knights_tour( 0, 0, 0 );

return 0;
)

int out_of_bounds( int nextRow, int nextCol )
{
/* Returns 1 if out of bounds.
Returns 0 if O.K.          */

if ( nextRow < 0 || nextRow > 7 )
return 1;

if ( nextCol < 0 || nextCol > 7 )
return 1;

/* O.K. */
return 0;
}

int visited( int nextRow, int nextCol, int board[][ 8 ] )
{
/* Returns 1 if visited.
Returns 0 if not visited. */

if ( board[ nextRow ][ nextCol ] == 1 )
return 1;

return 0;
}

int knights_tour( int startingRow, int startingCol, int moveNumber )
{
int board[ 8 ][ 8 ] = { 0 };
/* moveNumbers:     0  1   2   3   4   5  6  7 */
int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[ 8 ]   = { -1, -2, -2, -1, 1, 2, 2, 1 };
int temp1, temp2;
int currentRow, currentCol;
int totalMoves = 0;

if ( moveNumber > 7 )
return 0;

temp1 = currentRow + vertical[ moveNumber ];
temp2 = currentCol + horizontal[ moveNumber ];

if ( out_of_bounds( temp1, temp2 ) != 1 || visited( temp1, temp2, board ) != 1 ) {
board[ currentRow ][ currentCol ] = 1;
currentRow += vertical[ moveNumber ];
currentCol += horizontal[ moveNumber ];
++totalMoves;
return knights_tour( currentRow, currentCol, moveNumber + 1 ) + totalMoves;
}

}```

2. 1. the board is local
2. moveNumber never gets incremented

3. for the 'board', can i fix the problem by adding a 'board' argument in the knights_tour function? but what do u mean moveNumber is never incremented, why?

i am very new to c can you pls post a sample knights_tour function if possible?

Code:
```/* Knight's Tour ( recursive version ) */

#include <stdio.h>

/* 'col' = column */

int knights_tour( int startingRow, int startingCol, int moveNumber, int board[][ 8 ] ); /* returns the number of moves made */

int out_of_bounds( int nextRow, int nextCol ); /* check if next move is off the board */

int visited( int nextRow, int nextCol, int board[][ 8 ] );       /* check if next square is visited already */

int main()
{
int board[ 8 ][ 8 ] = { 0 };

printf( "***Knight's Tour***" );

printf( "Number of moves made: %d \n\n", knights_tour( 0, 0, 0 , board));

return 0;
)

int out_of_bounds( int nextRow, int nextCol )
{
/* Returns 1 if out of bounds.
Returns 0 if O.K.          */

if ( nextRow < 0 || nextRow > 7 )
return 1;

if ( nextCol < 0 || nextCol > 7 )
return 1;

/* O.K. */
return 0;
}

int visited( int nextRow, int nextCol, int board[][ 8 ] )
{
/* Returns 1 if visited.
Returns 0 if not visited. */

if ( board[ nextRow ][ nextCol ] == 1 )
return 1;

return 0;
}

int knights_tour( int startingRow, int startingCol, int moveNumber, int board[][ 8 ] )
{
/* moveNumbers:     0  1   2   3   4   5  6  7 */
int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int vertical[ 8 ]   = { -1, -2, -2, -1, 1, 2, 2, 1 };
int temp1, temp2;
int currentRow, currentCol;
int totalMoves = 0;

if ( moveNumber > 7 )
return 0;

temp1 = currentRow + vertical[ moveNumber ];
temp2 = currentCol + horizontal[ moveNumber ];

if ( out_of_bounds( temp1, temp2 ) != 1 || visited( temp1, temp2, board ) != 1 ) {
board[ currentRow ][ currentCol ] = 1;
currentRow += vertical[ moveNumber ];
currentCol += horizontal[ moveNumber ];
++totalMoves;
return knights_tour( currentRow, currentCol, moveNumber + 1 , board) + totalMoves;
}
}```

4. Is this homework out of the Dietel & Dietel book? I've "helped" someone with this before and have several of the solutions, but I did it OO/C++ with a Knight class, and they didn't do OO in their class yet...

5. You can pass around board if you want, you can go functional all the way if you want but C++ is meant for object orientation. Don't you see what moveNumber not being incrementing means? I suppose you had an idea to start with otherways you wouldn't have come this far, maybe you've left this project for a good while like a half year or so?

6. Yes this problem is from the deitel book of C: How to Program.

IF possible i really need help with a recursive solution, i've already worked out the iterative solution yesterday.

thnx

7. Which is the recursive part? Its been a while, and I don't have the book anymore.

8. last line, recursion means: call itself

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured