0

I am trying to achieve week 3 game of fifteen with the hacker edition of the problem set. I did some research about randomizing the tiles of the game of fifteen and found an interesting web page written by Bruce Alderman who advised that the best method was implementing the Fisher-Yates algorithm in order to initialize the board to a pseudorandom but solvable configuration.

However I face some issues when implementing it. I don't understand perfectly how does the algorithm works but I have a segmentation fault. This is due to the fact that when trying to swap the tile of coordinate xi,yi with xj,yj, yj takes a too big value wich is always: 516471058. Furthermore the others always have a value of 2.

Yet, I don't know what to change from this code as far as I don't perfectly understand the algorithm...

This is the relevant part of the code:

/**
 * Initializes the game's board with tiles numbered 1 through d*d - 1
 * (i.e., fills 2D array with values but does not actually print them).  
 */
void init(void)
{
    nombre = d*d-1;
    for(int ligne = 0; ligne<d; ligne++){
        for (int colonne= 0;colonne<d;colonne++){
            board[ligne][colonne]=nombre;
            nombre = nombre-1;
        }
    }

        if(d%2==0){
            printf("we got an even number");
            board[d-1][d-3]=1;
            board[d-1][d-2]=2;
        }

}
/**
 * Swap tiles given their positions
 */
void swapTiles(i, j, k, l) {
    printf("We entered swapTiles\n");
    printf("tiles values:\n");
    printf("xi: %i\n",i);
    printf("yi: %i\n",j);
    printf("xj: %i\n",k);
    printf("yj: %i\n",l);
    int temp = board[i][j];
    board[i][j] = board[k][l];
    board[k][l] = temp;
  }

/**
 * Prints the board in its current state.
 */
void draw(void)
{
    for(int ligne = 0;ligne<d;ligne++){
        for (int colonne= 0;colonne<d;colonne++){
            //add place for one digit number to allow all number to be correctly indent
            if(board[ligne][colonne]<10){
                printf(" %i ",board[ligne][colonne]);
            }
            else{
                printf("%i ",board[ligne][colonne]);
            }

        }
        printf("\n");
    }

        int i = d * d - 1;
    while (i > 0) {
      int j = rand() * i;
      int xi = i % d;
      int yi = i / d;
      int xj = j % d;
      int yj = j / d;
      swapTiles(xi, yi, xj, yj);
      --i;
    }


}

The output is:

 8  7  6 
 5  4  3 
 2  1  0 
We entered swapTiles
tiles values:
xi: 2
yi: 2
xj: 2
yj: 516471058
Segmentation fault

I didn't used Math.floor and Math.random() given in the webpage as far as it created issues in my program.

By the way, if you know any better way to randomize the position of the tiles, I would be glad to hear about it!

Thanks in advance!

1

The problem lies here:

  int j = rand() * i;

The call to rand() returns a very large number. From there on, it just gets propogated through the code, used in other calculations, and pushed further on. Anywhere downstream that uses j or another var based on j, is getting a really large integer. Finally, when the code tries to use one of those downstream numbers as an index for the board array, it seg faults because the index is sooooo far outside the limits, it just blows up. If all you're trying to do is get a random number in an acceptable range for an index, x % d will cure this, even for a very large integer.

As a side note, you say that you're using this code to randomize the initialization of the board. If so, the place to do this is in init(), not draw(). By doing it in draw, you're just going to scramble the board after every move.

As for the concept/algorithm itself, I'm offering no opinion as that's something for you to sort out. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • I understand, changed, moved it two draw(). Yet why are xi,yi, xj,yj always the same value? Now my tiles look like: 0 -1 6 for the first row 3 5 2, for the second 0 7 8, for the last in a 3*3 matrix. What should I do to have them all? Oct 5 '16 at 11:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .