Knight's Tour Problem 2

This is a discussion on Knight's Tour Problem 2 within the C Programming forums, part of the General Programming Boards category; Hi, THis time i only have one question to get clear of so far. Now my book tells me to ...

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

    Knight's Tour Problem 2

    Hi,

    THis time i only have one question to get clear of so far. Now my book tells me to develop a strategy to move the knight. Each square on the board is labelled with accessibility numbers which tells how hard are they accessed. They are as follows on a 8x8 chess board:

    2 3 4 4 4 4 3 2
    3 4 6 6 6 6 4 3
    4 6 8 8 8 8 6 4
    4 6 8 8 8 8 6 4
    4 6 8 8 8 8 6 4
    4 6 8 8 8 8 6 4
    3 4 6 6 6 6 4 3
    2 3 4 4 4 4 3 2

    Here is the bit i don't understand:
    ---------------------------------------------------------------------------------
    'Now write a version of the Knight's Tour program using the accessibility heuristic. At any time, the knight should move to the square with the lowest accessibiloity number. In case of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin in any of the four corners. (Note: As the knight moves around the chess board, your program should reduce the acessibility numbers as more and more squares become occupied. In this way, at any give time during the tour, each available square's accessbility number will remain equal to precisely the number of squares from which that square may be reached.) '
    ----------------------------------------------------------------------------------

    WHat IS a tie?

    How do i reduce the accessibility numbers ? Each time the knight moves reduce one from all squares? This can't make sense.

    Pls help.

    thnx

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Let's say your knight starts in the top left corner, which I refer to as (0,0).

    From that place, we have two places to which we can move, either (1, 2), or (2, 1). The accessability of each of these cells is 6, so we have a tie. According to the rules of the problem, we may choose either of the squares. Let's say that we choose (1, 2)

    Also, since we've visited cell (0,0), it is no longer accessable, therefore that's one less cell that (1, 2) has access to, and one less cell that (2, 1) has access to. Therefore, when we mark cell (0, 0) as unaccesable, we also have to reduce the accessability of (1, 2) and (2, 1) to 5. It doesn't matter if we do this before or after choosing which cell to jump to.

    Now we are at cell (1, 2). Here's a listing of the 5 cells we can access from here....
    (0, 4) Accessability 4
    (2, 0) Accessability 4
    (2, 4) Accessability 6
    (3, 1) Accessability 6
    (3, 3) Accessability 8

    Now we have another tie. So, according to the rules, we may choose either (0, 4), or (2, 0). Also, since cell (1, 2) has been visited, all the cells which have access to (1, 2) will have their accesability reduced by one (clearly, these are the same points as those which we could access from (1, 2)).

    And I take it that we just repeat this untill we've nowhere else to move.
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    To determine which cell has the lowest accessibility, do i have to use some sort of sorting algorithm such as bubble sort ?

    and for each move i have to calculate how many squares are accessible from that square, do that for every move, will it slow down the program a little bit ? Like because i have to use a for loop of a while loop ?

    thnx

  4. #4
    Registered User
    Join Date
    Dec 2001
    Posts
    421
    do i have to use some sort of sorting algorithm
    you don't have to sort anything.. just compare each value...

    Code:
    if(accessibility[x] < accessibility[y])
    {
      // use X
    }
    else
    {
      // use Y
    }
    for each move i have to calculate how many squares are accessible from that square

    well, each place you can access is 2 squares one way, and one in the other.

    ie:
    x - 2, y - 1
    x - 2, y + 1
    x + 2, y - 1
    x + 2, y + 1
    x - 1, y - 2
    x - 1, y + 2
    x + 1, y - 2
    x + 1, y + 2

    you can put a loop in if you want... but it might not be worth it... just make sure that each of those combinations is inside the square.. and that the acessibility of a particular square is not zero.

    good luck
    U.
    Quidquid latine dictum sit, altum sonatur.
    Whatever is said in Latin sounds profound.

  5. #5
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    if(accessibility[x] < accessibility[y])
    {
    // use X
    }
    else
    {
    // use Y
    }
    Each time, i have to compare 8 (max) accessiblity numbers, how can i simple use the if statement ?

    OK maybe this will clear things up a little bit, here is 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***\n\n" );
    
       printf( "\nNumber 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;
       int i, j;
    
       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;
                printf( "board[ %d ][ %d ]\n", currentRow, currentCol );
                break;
             }
             else { /* Next move not possible */
                if ( moveNumber == 7 )
                   end = 1;             /* No more possible moves... */
                continue;
             }
          }
       }
    
       return totalMoves;
    }

  6. #6
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    That's what i have so far. It doesn't work, it only display 2 moves, but it does choose the lowest accessibility number to go to for that two moves. I would like to know why it won't go further as it should. What's wrong with the code and where ?

    thnx in advance.

    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 bubbleSort( int a[] );
    
    int main()
    {
       int board[ 8 ][ 8 ] = { 0 };
    
       printf( "***Knight's Tour***\n\n" );
    
       printf( "\nNumber 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;
       int arrayToSort[ 8 ] = { 0 };
       int retval;
       int i;
       int potentialMoves;
       int access[ 8 ][ 8 ] = { { 2, 3, 4, 4, 4, 4, 3, 2 },
                                { 3, 4, 6, 6, 6, 6, 4, 3 },
                                { 4, 6, 8, 8, 8, 8, 6, 4 },
                                { 4, 6, 8, 8, 8, 8, 6, 4 },
                                { 4, 6, 8, 8, 8, 8, 6, 4 },
                                { 4, 6, 8, 8, 8, 8, 6, 4 },
                                { 3, 4, 6, 6, 6, 6, 4, 3 },
                                { 2, 3, 4, 4, 4, 4, 3, 2 } };
    
       while ( end != 1 ) {
          potentialMoves = 0; /* reset number of potential moves */
    
          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 ) {
                arrayToSort[ moveNumber ] = access[ temp1 ][ temp2 ];
                ++potentialMoves;
             }
             else { /* Next move not possible */
                if ( moveNumber == 7 )
                   end = 1;             /* No more possible moves... */
                continue;
             }
          }
    
          access[ currentRow ][ currentCol ] = potentialMoves; /* reduce accessibility number */
    
          retval = bubbleSort( arrayToSort );  /* returns smallest accessibility number */
    
          for ( moveNumber = 0; moveNumber < 8; moveNumber++ ) {
             temp1 = currentRow + vertical[ moveNumber ];
             temp2 = currentCol + horizontal[ moveNumber ];
             if ( access[ temp1 ][ temp2 ] == retval ) {
                board[ currentRow ][ currentCol ] = 1;
                currentRow += vertical[ moveNumber ];
                currentCol += horizontal[ moveNumber ];
                ++totalMoves;
                printf( "board[ %d ][ %d ]\n", currentRow, currentCol );
                printf( "%d\n", retval );
    
                break;
             }
          }
    
       }
       return totalMoves;
    }
    
    int bubbleSort( int a[] )
    {
       /* ascending sort */
    
       int pass, i, j, hold, arraySize = 8;
    
       for ( pass = 1; pass <= arraySize - 1; pass++ )
          for ( j = 0; j <= arraySize - 2; j++ )
             if ( a[ j ] > a[ j + 1 ] ) {
                hold = a[ j ];
                a[ j ] = a[ j + 1 ];
                a[ j + 1 ] = hold;
             }
    
       /* reusing j */
       for ( j = 0; j < 8; j++ )
          if ( a[ j ] != 0 )
             return a[ j ];
          else
             continue;
    
    }
    Last edited by Nutshell; 01-09-2002 at 03:17 AM.

  7. #7
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    anyone, pls give a hand. The code will only generate two moves, although that two moves doesn't move according to the accessibility numbers...

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I'm sorry, but the problem with that code is not a couple bugs, the code itself is incorrect enough that I'm not sure it can be 'fixed'.

    You need to work with 3 seperate steps...

    Step one: choose the X and Y such that they have the lowest accessability from the current square.
    Step two: mark the current square as visited.
    Step three: decrease the accessability of all the squares which can access the current square by one.

    For step one, you don't need to sort. You should be using a for loop that has the following code...
    Code:
         if (accessability[tempX][tempY] < 
             accessability[move2MeX][move2MeY]);
         {
          move2MeX = tempX;
          move2MeY = tempY;
         }
    This little snippet of code will compare the accessability of square tempX, tempY with that of move2MeX, move2MeY, and if the accessability of temp is less than that of move2Me, then it will replace move2Me with temp. By doing this for every square you want to compare, in the end, move2Me be the square with the lowest accessability.

    For step two, I suggest that you only use one array to represent the board, use your access array. If a square has been visited, then mark the square as having an access of 0 or -1.

    Step three is just a simple for loop.
    Callou collei we'll code the way
    Of prime numbers and pings!

  9. #9
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    thnx i will givit a try.

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Here is the code that I wrote which
    shows the problem with the code that you
    wrote. Your method won't work as the knight
    will get stuck after a certain number of moves.
    This one will run until it gets stuck after 59
    moves.
    Attached Files Attached Files
    • File Type: c kn.c (3.6 KB, 232 views)

  11. #11
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    At the ending sequence the board looks like


    11111111
    11111111
    11111111
    11111111
    11111011
    11100011
    11111111
    11111111

    Using (row, col)
    (0, 0) Is the top left corner and the knight is at (5, 2)
    The knight as no where to go except for a used square.

  12. #12
    Registered User Nutshell's Avatar
    Join Date
    Jan 2002
    Posts
    1,020
    worked appreciate it nick. Need any software just ask me.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 8 knights problem.
    By chottachatri in forum C++ Programming
    Replies: 2
    Last Post: 04-03-2008, 02:30 AM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM

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