3

I am working on the N-Puzzle game (also known as 15-puzzle...) where you split an image on a square grid, remove one piece, and shuffle. I am not so interested in the solutions to the puzzle, as that is up to the user. But I would like to pseudo-randomly shuffle the board.

I know that 1/2 of all possible shuffles would make the board unsolvable. Is there an easy way to psuedo-randomly to generate a shuffled state, assuming I have some rand()-esc function and I know the board size?

I have a game board in memory, a multi-dimensional array of integers. My method simply places the images in opposite order, switching the last with the second to last image on even boards. My current function is below, and I am working in Java.

private void shuffle()
{
    gameState = new int[difficulty][difficulty];
    int i = 0, N = (difficulty * difficulty) -1;

    while (i < N)
        gameState[(int)(i / difficulty)][i % difficulty] = N - ++i;
    gameState[difficulty-1][difficulty-1] = N;

    // N id even when the remainder of N/2 is 0
    if ((difficulty % 2) == 0)
    {
        // swap 2nd to last and 3rd to last element
        int tmpEl = gameState[difficulty-1][difficulty-2];
        if (difficulty == 2)
        {
            gameState[1][0] = gameState[0][1];
            gameState[0][1] = tmpEl;
        }
        else
        {
            gameState[difficulty-1][difficulty-2] = gameState[difficulty-1][difficulty-3];
            gameState[difficulty-1][difficulty-3] = tmpEl;
        }
    }
}
1

3 Answers 3

6

This problem basically boils down to doing a standard shuffle algorithm with a small twist.

The key observation is that for the 15-puzzle to be solvable the parity of the permutation and the parity of the blank square must be the same.

First create a random permutation using a standard algorithm for that purpose. For example the Knuth shuffle algorithm: Random Permutations

The advantage of using Knuth's shuffle ( or Fisher-Yates shuffle ) is that it involves swapping numbers, so you can easily keep track of the parity of the permutation. Each swap either keeps the parity ( if you swap 1 & 3 ), or changes the parity ( if you swap 1 & 2 ).

Place the blank square on the same parity as the parity of the permutation, and you are done. If the permutation has odd parity then place the blank an odd square (1,3,5,... chosen at random ). If the permutation has even parity then place the blank on an even square.

1
  • 2
    i'm sorry to ask such a stupid question but what does this sentence mean? "the parity of the permutation and the parity of the blank square must be the same"? what is the parity of the permutation and what is the parity of the blank square?
    – user151496
    Apr 13, 2016 at 8:38
3

My suggestion would be to keep track of an empty square in the array (the piece that you have removed).
Then, pick a random side of this empty square (making sure to do the necessary bounds checks) and "swap" the piece on that side with the empty square. This simulates the sliding action that the player would do.
Repeat this action a number of times (easy difficulty setting - the difficulty sets the number of iterations you make), "sliding" the empty square throughout the array each time.

With this method, you simply have to keep track of where the empty square is, and then pick a random side to move to.

Hope this helps you out a bit - I'm not providing any code here, just a simple algorithm for you to work with.

4
  • 3
    -1. This doesn't give you a random shuffle though which is what the question was asking for. May 24, 2011 at 2:14
  • @Himadri Why not? You're picking a random side, and basically doing the reverse of what the user will be doing, so as far as I can tell it should work.
    – a_m0d
    May 24, 2011 at 21:28
  • Say you just do 1 move, then clearly the resulting position isn't random right? There are only up to 4 possible new positions with just 1 move. May 25, 2011 at 4:55
  • Dunno, I'd still say that the result was random, just that it was a random choice of the four possibilities. Don't forget you can also place your starting square randomly.
    – a_m0d
    May 25, 2011 at 13:12
2

Just generate random puzzles until you generate one with an even parity. http://heuristicswiki.wikispaces.com/N+-+Puzzle

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.