Knight's Tour

This is a discussion on Knight's Tour within the C Programming forums, part of the General Programming Boards category; You have not yet told your ultimate goal This is not an easy path.. AI .. tough.....

  1. #16
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    532
    You have not yet told your ultimate goal

    This is not an easy path.. AI .. tough..
    [ Never code before desk work ]
    -------------------------------------:-->
    A man who fears Nothing is the man who Loves Nothing
    If you Love Nothing, what joy is there in your life.
    =------------------------------------------------------= - I may be wrong.

  2. #17
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    my ultimate goal is to write a program that move the knight around the chess board and touch as many squares as possible while not re-visiting any one of the squares. I've posted my codes but they do not work and i really want to know why.

    thnx very much

    here is the code ( changed some minor things ):

    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;
    
       ++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;
          return knights_tour( currentRow, currentCol, moveNumber , board) + totalMoves;
       }
    }
    Here are the compile errors i get:

    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)
    Last edited by Nutshell; 01-08-2002 at 06:26 AM.

  3. #18
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Here's basically what needs to happen when you make a move...
    You have a variable, totalMoves. You select which of the 8 possible moves gives you the highest return (and you use the function knights_tour to find this value).

    Your function just doesn't do this. Also, there really isn't any reason to pass the function the number of moves. All that the function really needs to be passed are the coordinates of the piece on the board (assuming that the board array is global, which it probably should be for this).

    Also, your current function makes no use of the coordinates passed to it. It seems you forgot to use the startingRow and startingCol variables.

    Following is a small code snippet. Don't worry, it isn't complete enough to give you the answer itself, but I think that this is reveals a bit about what your code needs to do...
    Code:
    totalMoves = 0; // This may have to change.
    for (moveNumber = 0; moveNumber < 8; moveNumber++)
    {
     totalMoves = max(totalMoves, knights_tour(startingRow + horizontal[i], startingCol + vertical[i])
    }
    This isn't complete, I mean, the function will have to handle setting/unsetting board flags, and testing for legal board positions.

    Also, it seems your code doesn't actually return any value when it gets to an illegal board position. You definately want to return a value for this. In general, you want to return a value, such that you don't have to really do any vodoo on the callee side of the function. For this problem, if the function detects that it is in an illegal board position (which should be the first thing it checks for), then it either needs to return a 0, or a -1, depending on how you are handling the function.
    Callou collei we'll code the way
    Of prime numbers and pings!

  4. #19
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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;
    }

  5. #20
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,825
    Your main function ends with a parenthesis, not a chicken lip...

  6. #21
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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;
    }

  7. #22
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,825
    It compiled, ran, and said 41 moves... Is that what you wanted?

  8. #23
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Recursion is the easier way to do this problem, but this is a difficult sort of problem to start off with. I suggest you try solving the following (not as difficult) problem instead:

    For an NxN square, divided into NxN cells, find the number of paths from the bottom left cell to the top right cell.
    Code:
    #include <stdio.h>
    
    #define ASPECT 3
    
    // Creates an ASPECTxASPECT array of 0s
    // Having this as global, and using a define as our aspect saves
    //  a lot of trouble, although it makes our progam less versatile.
    int cell[ASPECT][ASPECT] = {};
    
    // Gives the number of legal paths from x,y to ASPECT-1, ASPECT-1
    // On array cell[][]
    // paths (ASPECT - 1, ASPECT - 1) returns 1
    int paths (int x, int y); 
    
    // Returns 0 if the x, y is out of bounds or a marked spot.
    // Else, returns 1
    int isPosLegal(int x, int y);
    
    // Returns 1 if (x, y) == (ASPECT - 1, ASPECT - 1)
    // Else, returns 0
    int isPosEnd (int x, int y);
    
    int main (void)
    {
     int i = paths (0, 0);
     printf ("The number of paths is %d.\n", i);
     return 0;
    }
    
    paths (int x, int y)
    {
     //
    }
    
    int isPosEnd (int x, int y)
    {
     //
    }
    
    int isPosLegal (int x, int y)
    {
     //
    }
    It's not quite the same type of recursive problem as the Knight's Tour, but it is also a game state search, so it's somewhat similar.
    Callou collei we'll code the way
    Of prime numbers and pings!

  9. #24
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    thnx thnx thnx

    to govtcheez:
    the output results are getting to where they should be, you can
    read my previous post if you'[re unsure what my program's
    suppose to do. thnx a lot

    Yes i know many people say that recursion is easier and simpler. But i am a real newbie and really need to understand recursion. And i simply can't do such 'hard-for-me-at-the-moment' recursion stuff......
    Last edited by Nutshell; 01-08-2002 at 09:46 AM.

  10. #25
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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.

  11. #26
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    sorry but i dont fully really get your idea.

    Do you mean the no. of possible knight paths is the number of 'possible' knight paths the first move + the no. of possible knight paths after another move + the 8th move ?

    Can you maybe post a sample recursion example for me to study pls?

    thank you
    Last edited by Nutshell; 01-08-2002 at 10:51 AM.

  12. #27
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,825
    He means that just because the knight doesn't have any moves left, it doesn't mean he couldn't have taken a different path earlier in the series and gotten different results.

  13. #28
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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

  14. #29
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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

  15. #30
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    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

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. knight's tour!
    By Jasin14 in forum C Programming
    Replies: 13
    Last Post: 12-22-2010, 03:30 PM
  2. Knight's Tour: couting problems
    By Sektor in forum C++ Programming
    Replies: 3
    Last Post: 01-19-2004, 11:46 AM
  3. Knight's Tour Recursion Problem
    By thephreak6 in forum C++ Programming
    Replies: 1
    Last Post: 10-14-2003, 09:18 AM
  4. Knights Tour Trivia
    By shrestha in forum C++ Programming
    Replies: 2
    Last Post: 01-16-2003, 07:32 AM
  5. Knight's Tour Problem 2
    By Nutshell in forum C Programming
    Replies: 11
    Last Post: 01-09-2002, 08:32 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21