You can use a fun fact from abstract algebra. It's a group theory fact, to be more specific. Read all about it here or here or, better yet, here. I actually used this in my own sliding tile puzzle I created for the App Store in 2013. But I used it to generate puzzles, not to verify solvability.
I see now where my original intended answer went wrong. The math behind it requires the empty space be in the bottom right corner, and I missed that at first. From the Wiki link:
In particular if the empty square is in the lower right corner then the puzzle is solvable if and only if the permutation of the remaining pieces is even.
A permutation of numbers 1 through n is even if and only if it's obtained by performing an even number of swaps. For example, the permutation 2 1 4 3
is an even permutation of 1 2 3 4
because it's obtained from two swaps: swapping 1 and 2, and swapping 3 and 4. And the permutation 1 3 2 4
is not an even permutation (a so-called odd permutation) because it's obtained from one swap: swapping 2 and 3. Note that the number of swaps is not unique for a given permutation, but the parity of the number of swaps is unique.
If you want to keep things as simple as possible then my recommendation to you is to use the following general process:
- Start with a puzzle in the solved state.
- Let
m
be a random positive even integer.
- Swap
m
pairs of non-empty tiles (That is, leave the empty space where it is, in the bottom right corner).
Of course, you'll need some checks to make sure you don't swap the same pair several or even m
times. But this is by far the most efficient way to do this unless you consistently choose massively huge values of m
. This is what I did in my own app.
But anyway, if you want to stick with your original process of randomly generating a puzzle and seeing if it's solvable, then you can still use permutations to check solvability in O(n)
time, where n = puzzle.length
.
We already know the following:
A puzzle is solvable if and only if the empty space is in the bottom right corner and the permutation is even.
Therefore for a randomly created puzzle we also need to figure out the Manhattan distance between the empty space and the bottom right corner. This is equal to the number of rows the empty space is away from the last row plus the number of columns the empty space is away from the last column. For simplicity I'll assume your board will always be square, and I think that's a reasonable assumption based on your original code. Then with this Manhattan distance between where the empty square is and where it's supposed to be, a distance which I'll denote x
, we have the following fact:
A puzzle is solvable if and only the parity of the permutation equals the parity of x
.
I won't rigorously prove this, but the basic idea is that every move you make will move the empty square and therefore can be thought of as a swap with the empty square. And the empty square is an even Manhattan distance away (i.e., x
is even) if and only if it takes an even number of swaps to get the empty square where it belongs. Also, a composition of two permutations is even if and only if those two permutations have the same parity.
And, finally, here's the code:
public boolean isSolvable(int[] puzzle) {
int [] myPuzzle; // Copy puzzle because we'll be swapping elements.
int [] indexArr; // indexArr[0] is index of blank space in puzzle[].
// indexArr[1] is index of space #1 in puzzle[].
// indexArr[2] is index of space #2 in puzzle[], etc.
int n = puzzle.length;
int swapCount = 0; // Number of swaps to get from shuffled state to solved state.
int manDist = 0; // Manhattan distance between shuffled empty space and bottom right corner.
int gridWidth = (int) Math.sqrt(puzzle.length);
int row, col; // Row and column of the empty space in the shuffled puzzle.
myPuzzle = new int[n];
indexArr = new int[n];
// Make a deep copy so we don't modify the original.
// Also store indexes of the shuffled tiles.
// This loop runs in O(n) time.
for (int i = 0; i < n; i++) {
myPuzzle[i] = puzzle[i];
indexArr[puzzle[i]] = i;
}
// First get the Manhattan distance between where the empty space is and where it should be.
row = indexArr[0] / gridWidth + 1; // Row of empty space's shuffled position. Add 1 to account for 0-based index.
col = indexArr[0] % gridWidth + 1; // Column of empty space's shuffled position. Add 1 to account for 0-based index.
manDist = 2*gridWidth - row - col; // (gridWidth-row) + (gridWidth-col)
// Count how many swaps we need to get to the solved state.
// This loop runs in O(n) time.
for (int i = 0; i < n; i++) {
// Swap tile #i with whatever tile is in tile #i's correct position.
// The current position for tile #i is indexArr[i].
// The correct position for tile #i is (i+n-1) % n
// because the blank space #n is actually tile #0.
// Thus we want to swap puzzle[indexArr[i]] with puzzle[(i+(n-1)) % n],
// but only if the swap is needed.
// Note that we must also swap the corresponding stored indexes in
// indexArr so future loop iterations will work correctly.
if (myPuzzle[indexArr[i]] != myPuzzle[(i+n-1) % n]) { // If we need to swap
// Swap the tiles, i.e., put tile #i in its proper place.
swap(myPuzzle, indexArr[i], (i+n-1) % n);
// Now swap their stored positions in indexArr.
swap(indexArr, i, myPuzzle[indexArr[i]]);
swapCount++;
}
}
// Puzzle is solvable if and only if the permutation and manDist have the same parity.
return (swapCount % 2 == manDist % 2);
}
private void swap(int[] arr, int a, int b) {
arr[a] += arr[b];
arr[b] = arr[a] - arr[b];
arr[a] -= arr[b];
}
This runs in O(n)
time overall. I tested with a few samples and this agrees with your original implementation in all cases.
int[]
only because the algorithm requires this? (Sinceint[][]
is more logical to represent a grid of numbers). If so I might be tempted to look at how to adapt the algorithm to work with anint[][]
without transforming it first. \$\endgroup\$