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

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

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

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.

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.