N-Puzzle pseudo-random shuffling?

Question

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

Answer 1

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.