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

[iflash]

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.

thnx in advance

/* 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;
   }


}

[kedaman]

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

[iflash]

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?

how about this 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;
   }
}

[JoshT]

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

[kedaman]

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?

[iflash]

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

[JoshT]

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

[kedaman]

last line, recursion means: call itself