Thread: Knight's Tour

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

    Knight's Tour - need help

    Hi,

    My program's suppose to move the knight around the chess board touching the each square only once. It's starting off at (0, 0) and there are eight possible moves for the knight depending on its position. The program tests each potential move and if that move is not off the board or it has been visited yet then that move is made. However my program's output only say that the knight make 8 moves. i tried out by hand and it's sure more than that. Pls help , what's wrong ?

    thnx


    Code:
    /* Knight's Tour */
    
    #include <stdio.h>
    
    int main()
    {
       int board[ 8 ][ 8 ] = { 0 };                 /* Chess board */
       int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
       int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
       int totalMoves = 0;                      /* Total of all moves made */
       int currentRow = 0, currentColumn = 0;   /* Current position of knight */
       int moveNumber;                          /* Move type */
       int i, j;                                /* Loop counters */
       int newPos;                              /* Test next possible move for validity */
       int tryNextMoveType = 0;                        /* Flag to see if try next move number */
       int end = 0;
    
       while ( end != 1 ) {
    
          moveNumber = 0;
    
          for ( i = 0; i <= 7; i++ ) {
    
             tryNextMoveType = 0;
    
             newPos = currentRow + vertical[ moveNumber ];
             if ( newPos < 0 || newPos > 7 )
                tryNextMoveType = 1;
    
             newPos = currentColumn + horizontal[ moveNumber ];
             if ( newPos < 0 || newPos > 7 )
                tryNextMoveType = 1;
    
             if ( board[ currentRow + vertical[ moveNumber ] ][ currentColumn + horizontal[ moveNumber ] ] == 1 )
                tryNextMoveType = 1;
    
             if ( tryNextMoveType == 0 ) {
                currentRow += vertical[ moveNumber ];
                currentColumn += horizontal[ moveNumber ];
                board[ currentRow ][ currentColumn ] = 1;
                ++totalMoves;
                break;
             }
             else
                moveNumber++;
    
             if ( i == 7 && tryNextMoveType == 1 ) /* No more possible moves */
                end = 1;
          }
       }
    
       printf( "Total moves made by the knight: %d", totalMoves );
    
       return 0;
    }
    Last edited by Nutshell; 01-08-2002 at 12:07 AM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What a swell code example. Why did you post it? Do you need help? Does it work? Do you want comments? Are you showing your coding prowess? What exactly?

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531
    Make your question more specific.

    Anyway.. You will never know what happened after visiting your post -Thanks a lot.
    Last edited by zahid; 01-08-2002 at 12:48 AM.
    [ 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.

  4. #4
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    I just want to know what's wrong with my program that keeps limiting the number of possible moves to eight, which should be more than that for sure.

    thnx

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I think the best way to do this is
    to use recursion. I'll just use psudocode
    as I don't want to solve it completly for
    you.

    int knight_tour(row, col, count)
    if out_of_bounds(row, col) or position
    is dirty then return failure.

    else
    make position dirty
    check if count >= 64

    call knight_tour with succesive
    positions until one returns success.
    if none returns success then
    return failure.

  6. #6
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    thnx for the suggestion.

    But can anyone tell me what is wrong with my original code that i keep getting the number of moves made is 8 which should be more than that?

    thnx

  7. #7
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531
    Originally posted by Nutshell
    I just want to know what's wrong with my program that keeps limiting the number of possible moves to eight, which should be more than that for sure.

    thnx
    In any position a knight has no more than 8 possible moves. Check it in chess Board.
    [ 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.

  8. #8
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    I know. Sorry I think i have to make myself more clear. My program is suppose to move the knight so that it touches as many squares as possible ( max 64 ) while not re-visiting any square.

    and my program doens't do that at the moment though i worked very hard to find out why. I need help.

    Also, now, i don't even know if my program works or not. When i changed the currentRow to 3 and currentColumn to 4 in declaration i get 33 moves made by the knight. SO my another question can be: DOes my program achieve its purpose ?

    thnx a lot
    Last edited by Nutshell; 01-08-2002 at 01:45 AM.

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Eventually it's possible to have a sequence
    of moves where the knight is trapped with only
    used squares to hop onto. You automaticaly give up in that situation.

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    You will have to find a heuristic to make the
    algorithm that I gave faster on a 8x8 board but I've been able to test it on a 5x5 board.
    On 8x8 it just stands still

  11. #11
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531
    Now I got the point..
    I have to study your code more for details.

    But pseudo is

    get_possible_positions();
    check_if_not_traveled_and_empty();
    do_it_intill_get_new_possition();

    if (got_one) { go_there(); turn_on_flag; do_it_again(new_position); }

    if(end_of_possible_positions) break;

    Little complicated to explain within few lines... I guess you have got the idea.

    I'm not sure if you can visit all over(64) the board this way (Without visiting second time)....

    Yeah.. you can not do that if you include that rule.
    [ 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.

  12. #12
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    Originally posted by Nick
    Eventually it's possible to have a sequence
    of moves where the knight is trapped with only
    used squares to hop onto. You automaticaly give up in that situation.
    isn't that good ? I mean, isn't that what my program's suppose to do ?

    but when i tried it by hand on a piece of paper i can have more than eight moves if i start on row 0 and column 0. How come?

    thnx

  13. #13
    Registered User zahid's Avatar
    Join Date
    Aug 2001
    Posts
    531

    Is it your goal to create a chess engine?

    Is it your goal to create a chess engine?
    structure will help here.

    But Class: Object is circling on my head.
    [ 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.

  14. #14
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    sorry i havne't learnt up to that stage in my book yet...

  15. #15
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    SIgh. Now i took Zahid's advice and tried to re-write the program using recursive functions, which i'm not good at. Here is my code and it has compile errors and i bet it needs still need debugging even if it compiles successfully. Pls help out, before i learn how to do stuff myself i need somebody to give me examples. 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;
       }
    
    
    }

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, 04:30 PM
  2. Knight's Tour: couting problems
    By Sektor in forum C++ Programming
    Replies: 3
    Last Post: 01-19-2004, 12:46 PM
  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, 08:32 AM
  5. Knight's Tour Problem 2
    By Nutshell in forum C Programming
    Replies: 11
    Last Post: 01-09-2002, 09:32 PM