Thread: Knight's Tour

Hi,

I give up recursion. If possible provide maybe a link or two involving some simple recursion exercise to start me off pls. Here is my edited code. However i still get the 3 compile errors i got before:

Line 22: parse error before `)'
Line 32: `nextCol' undeclared (first use in this function)
Line 32: (Each undeclared identifier is reported only once
for each function it appears in)

my current code:

Code:

/* Knight's Tour ( recursive version ) */

#include <stdio.h>

/* 'col' = column */

int knights_tour( int startingRow, int startingCol, 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, 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 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 = startingRow;
   int currentCol = startingCol;
   int totalMoves = 0;
   int end = 0;
   int moveNumber;

   while ( end != 1 ) {
      for ( moveNumber = 0; moveNumber <= 7; moveNumber++ ) {
         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;
            break;
         }
         else { /* Next move not possible */
            if ( moveNumber == 7 )
               end = 1;             /* No more possible moves... */
            continue;
         }
      }
   }

   return totalMoves;
}

HI,

I think i've made it! Here is the code and pls tell me if it really works!!!!!!!! special thnx to Govtcheez for catchin the little bug and all others who've posted!

Code:

/* Knight's Tour ( recursive version ) */

#include <stdio.h>

/* 'col' = column */

int knights_tour( int startingRow, int startingCol, 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***\n\n" );

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

   getch();

   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 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 = startingRow;
   int currentCol = startingCol;
   int totalMoves = 0;
   int end = 0;
   int moveNumber;

   while ( end != 1 ) {
      for ( moveNumber = 0; moveNumber <= 7; moveNumber++ ) {
         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;
            break;
         }
         else { /* Next move not possible */
            if ( moveNumber == 7 )
               end = 1;             /* No more possible moves... */
            continue;
         }
      }
   }

   return totalMoves;
}

Code:

else { /* Next move not possible */
     if ( moveNumber == 7 )
         end = 1;  /* No more possible moves... */
         continue;
}

Your program gives up at this point when
it should go back in the tree of moves and
try another combination. As I understand it
you want the knight to touch every square on
the chess board without touching a square twice.

To come up with a recursive solution notice
that the number of knight paths from a given
position is the number of knight paths after
a move + the number of knight paths after another move ... + the number of knight paths after the 8 move. Once you get this all that is required is writing a base case which determines if a move is successful or the number of moves == 63. The actual code for this is simple.

oh, do u mean that the bit he posted only talks about the bit in my program when there're no moves left for the knight?

I don't really understand what he meant anyway? What will i get if i add all the possible moves for each move? Anyway how do i do it? WHich next move do i make to make another move if you know what i mean?

thnx

This is a bit long ...

If you study the fibonacci sequence you will
notice that
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)
As a function

int fib(int n)
{
if (n == 0 || n == 1)
return n; /* base case */

return fib(n-1) + fib(n-2);
}

If you look at the tree generated by this
function you will notice that the number of terminal nodes (or just end values in the tree)
is equivalent to
nodes_req(n) = nodes_req(n-1) + nodes_req(n-2)
Now all that is required to finish this is
the knowlege that the nodes required to compute
fib(0) is nodes_req(0) which is equal to 1.
What we have is
nodes_req(0) = 1
nodes_req(n) = nodes_req(n-1) + nodes_req(n-2)

This looks similar to fibnoccie sequence and it's
possible to show that
nodes_req(n) = fib(n+1)

With our problem we arn't really intrested in the
number of nodes, but we are interested
in a procedure which goes through all the nodes
until a certain condition is met.

You will also probaly want to create a function genmoves so that you can sort the moves so that the knight moves into the corners first as it's much faster.

To do this I did something like

Code:

void gen_point_value()
{
    int i, j;
    
    int center_row = NR_ROWS/2;
    int center_col = NR_COLS/2;

    for (i = 0; i < NR_ROWS; ++i) 
        for (j = 0; j < NR_ROWS; ++j) 
            point_value[i][j] = abs(i-center_row) + abs(j-center_col);
}

Which measures the difference from the center.
And then I sorted on point_value[row][col]. Though
your best off not sorting until you are finished with the rest of the program.

For the structure of your recursive function
will something like

Code:

knight_tour(row, col, count, final_path)
   make square dirty

   check base case
   n = genmoves(movelist, row, col)
  
   
   for i := 0; i < n; ++i
       check to see if 
       knight_tour(movelist[i].row,
                   movelist[i].col) ==
          SUCCESS;
           if success update final_path
           and return SUCCESS;
   if loop finishes with no success then
    clean square and return FAILURE

knight_tour(movelist[i].row,
movelist[i].col)

You only passed two arguments but in the function declaration you specified 4 parameters. Also, Where in the function evaluates if it's success or not. And what does the operator ':=' mean?

i know i don't know much but pls give a hand.

thnx