rand() function not acting very random

This is a discussion on rand() function not acting very random within the C Programming forums, part of the General Programming Boards category; I'm doing the "Knights Tour" exercise. It's where I have one knight piece on a chessboard. I'm supposed to see ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    182

    rand() function not acting very random

    I'm doing the "Knights Tour" exercise. It's where I have one knight piece on a chessboard. I'm supposed to see how far it can get when it's allowed to only touch a square once. I'm using rand() to generate the moves and I run the tour 1000 times. My problem is when I run it through the loop it seems to go through the exact same moves every single tour. What gives?


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int checkMovability( int[][ 8 ], int, int );
    void printBoard( int[][ 8 ] );
    
    
    int main()
    {
    
    int currentRow = rand() % 8, currentColumn = rand() % 8, moveNumber, counter = 1;
    int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 }, horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int board[ 8 ][ 8 ] = { 0 };
    int tourLength[ 65 ] = { 0 };
    int tour, i;
    
       srand( time(NULL) );
    
    
    for (tour = 1; tour <= 1000; ++tour) {
       while ( checkMovability( board, currentRow, currentColumn ) == 1 && counter <= 64 ) {
          moveNumber = rand() % 8;
     
          if ( board[ currentRow + vertical[ moveNumber ] ][ currentColumn + horizontal[ moveNumber ] ] == 0 ) {
    //         printf("inner if 1\n");
             if ( ( currentRow + vertical[ moveNumber ] ) <= 7 && ( currentRow + vertical[ moveNumber ] ) >= 0 ) {
    //            printf("inner if 2\n");
                if ( (currentColumn + horizontal[ moveNumber ]) <= 7 && ( currentColumn + horizontal[ moveNumber ] ) >= 0 ) {
                   currentRow += vertical[ moveNumber ];
                   currentColumn += horizontal[ moveNumber ];
                   board[ currentRow ][ currentColumn ] = counter;
                   ++counter;
    //               printBoard( board );
    //               printf("Knight at %d %d\n", currentRow, currentColumn);
                }
    
             }
    
          }
       }
    
    //   printBoard( board );
    //   printf("No more moves can be made\n");
       ++tourLength[ counter - 1];
    }
    
       for (i = 0; i <= 64; ++i) {
          printf("%d: %d\n", i, tourLength[ i ] );
       }
    
    return 0;
    }
    
    
    
    
    
    int checkMovability( int grid[][ 8 ], int row, int column )
    {
       int h[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
       int v[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
       int move;
     
       for (move = 0; move <= 7; ++move) {
    
    
          if ( grid[ row + v[ move ] ][ column + h[ move ] ] == 0 ) {
             if ( ( row + v[ move ] ) <= 7 && ( row + v[ move ] ) >= 0 ) {
                if ( (column + h[ move ]) <= 7 && ( column + h[ move ] ) >= 0 ) {
    //               printf("checkMovability returned 1\n");
    //               printf("checkMovability says you can move v: %d h: %d\n", v[ move ], h[ move ] );
    //               printBoard( grid );
                   return 1;
                }
             }
          }
       }
    
       return 0;
    }
    
    
    
    
    
    
    void printBoard( int grid[][ 8 ] )
    {
       int i, j;
    
       printf("\n\n");
    
       for (i = 0; i <= 7; i++) {
          for (j = 0; j <= 7; j++) {
          printf("%4d", grid[ i ][ j ] );
             if ( (j + 1) % 8 == 0 )
                printf("\n\n");
          }
       }
    
    return;
    }

  2. #2
    Registered User
    Join Date
    Aug 2007
    Posts
    42
    You called srand after rand.
    Last edited by bean66; 08-28-2007 at 02:05 PM.

  3. #3
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    That's what happens when you don't seed your random number generator.
    Use this once (and only once) before any calls to rand():
    Code:
    srand( time( NULL ) );

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You may want to move your currentrow and currentcolumn initialization to after the srand, to make the initial position more random. That probably don't solve your current problem, of course.

    This bit
    Code:
          if ( board[ currentRow + vertical[ moveNumber ] ][ currentColumn + horizontal[ moveNumber ] ] == 0 ) {
    will overflow if this check fails:
    Code:
             if ( ( currentRow + vertical[ moveNumber ] ) <= 7 && ( currentRow + vertical[ moveNumber ] ) >= 0 ) {
    //            printf("inner if 2\n");
                if ( (currentColumn + horizontal[ moveNumber ]) <= 7 && ( currentColumn + horizontal[ moveNumber ] ) >= 0 ) {
    You may not notice it in your current code, but it's a bad idea to index outside the valid range of an array.

    Once you have run one tour, do you think it would make sense to start over at a random place on the board?

    Also, you may want to reset the tourLength for each run... And counter... and board, perhaps?

    You have two arrays of "moves" that are (I presume) identical. Make that a single global and make it a const too, as I presume the knights movement pattern isn't going to change any time soon.

    --
    Mats

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    182
    Thanks guys,

    This was essentially a stripped down version of the "heuristics" version, that's why it's all over the place. I'll get back here as soon as I get a chance to try it all out.

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    random() is also not the best random number generator out there. For your purposes it should be sufficient.

    You can do a search for better random number generators on google.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. random to int?
    By psyadam in forum C# Programming
    Replies: 7
    Last Post: 07-22-2008, 08:09 PM
  2. Lesson #3 - Math
    By oval in forum C# Programming
    Replies: 2
    Last Post: 04-27-2006, 08:16 AM
  3. Another brain block... Random Numbers
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 01-23-2005, 04:51 PM
  4. How do I restart a random number sequence.
    By jeffski in forum C Programming
    Replies: 6
    Last Post: 05-29-2003, 02:40 PM
  5. Best way to generate a random double?
    By The V. in forum C Programming
    Replies: 3
    Last Post: 10-16-2001, 04:11 PM

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