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