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.

thnx in advance

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


}

---

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

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?

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

---

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

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?

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

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

last line, recursion means: call itself