Problem with recursive solution of "Knight's Tour".-VBForums
Results 1 to 8 of 8

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

  1. #1

    Thread Starter
    Hyperactive Member
    Join Date
    Aug 2001
    Posts
    484

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

  2. #2
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221
    1. the board is local
    2. moveNumber never gets incremented
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  3. #3

    Thread Starter
    Hyperactive Member
    Join Date
    Aug 2001
    Posts
    484
    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;
       }
    }
    Last edited by iflash; Jan 8th, 2002 at 05:32 AM.

  4. #4
    Black Cat JoshT's Avatar
    Join Date
    Nov 2000
    Location
    WNY, USA
    Posts
    4,032
    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...
    Josh
    Get these: Mozilla Opera OpenBSD
    I have books for sale: "MCSD in a Nutshell" and "VB Distributed Exam Cram" - PM me for details. Will also trade for a decent ATX Pentium 2 MB/CPU/RAM combo.

  5. #5
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221
    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?
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  6. #6

    Thread Starter
    Hyperactive Member
    Join Date
    Aug 2001
    Posts
    484
    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. #7
    Black Cat JoshT's Avatar
    Join Date
    Nov 2000
    Location
    WNY, USA
    Posts
    4,032
    Which is the recursive part? Its been a while, and I don't have the book anymore.
    Josh
    Get these: Mozilla Opera OpenBSD
    I have books for sale: "MCSD in a Nutshell" and "VB Distributed Exam Cram" - PM me for details. Will also trade for a decent ATX Pentium 2 MB/CPU/RAM combo.

  8. #8
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221
    last line, recursion means: call itself
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

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


Click Here to Expand Forum to Full Width

Survey posted by VBForums.