2
\$\begingroup\$

I have code which returns whether or not a sliding tile puzzle state is solvable. I was wondering whether there is any way I could either make the code a bit more readable or increase the performance in any way.

  public boolean isSolvable(int[] puzzle) {
        int parity = 0;
        int gridWidth = (int) Math.sqrt(puzzle.length);
        int row = 0; // the current row we are on
        int blankRow = 0; // the row with the blank tile

        for (int i = 0; i < puzzle.length; i++) {
            if (i % gridWidth == 0) { // advance to next row
                row++;
            }
            if (puzzle[i] == 0) { // the blank tile
                blankRow = row; // save the row on which encountered
                continue;
            }
            for (int j = i + 1; j < puzzle.length; j++) {
                if (puzzle[i] > puzzle[j] && puzzle[j] != 0) {
                    parity++;
                }
            }
        }

        if (gridWidth % 2 == 0) { // even grid
            if (blankRow % 2 == 0) { // blank on odd row; counting from bottom
                return parity % 2 == 0;
            } else { // blank on even row; counting from bottom
                return parity % 2 != 0;
            }
        } else { // odd grid
            return parity % 2 == 0;
        }
    }
\$\endgroup\$
1
  • \$\begingroup\$ Do you represent the puzzle as a int[] only because the algorithm requires this? (Since int[][] 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 an int[][] without transforming it first. \$\endgroup\$ – Imus Apr 14 '17 at 13:50
3
\$\begingroup\$

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:

  1. Start with a puzzle in the solved state.
  2. Let m be a random positive even integer.
  3. 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.

\$\endgroup\$
11
  • \$\begingroup\$ "… You just need to verify it's an even permutation of the solved state" — is that not what the code in the question is doing? Could you be more specific about what your recommendations are, or how your solution is better? \$\endgroup\$ – 200_success Apr 13 '17 at 21:22
  • \$\begingroup\$ @200_success, I think it's pretty clear that my recommendation is to calculate the value of the permutation symbol. I updated my answer with an explanation on how it's an improvement. \$\endgroup\$ – user132961 Apr 13 '17 at 21:38
  • \$\begingroup\$ Thank you for the answer, you didn't actually use gridWidth, did you just leave that in there by mistake? \$\endgroup\$ – user3667111 Apr 14 '17 at 10:57
  • \$\begingroup\$ The code doesn't actually work, I'm getting false positives \$\endgroup\$ – user3667111 Apr 14 '17 at 11:04
  • \$\begingroup\$ @user3667111, yes, I think I thought I'd need it but by the time I was done I forgot to take it out. Can you provide an example of a false positive? I'll see if I can debug. \$\endgroup\$ – user132961 Apr 14 '17 at 11:16
1
\$\begingroup\$

I don't think the algorithm itself can be improved. So let's look at improvements to your current implementation.

The first thing I noticed is that for the parity we only care if it's even or not. So we should be able to represent it with a boolean instead.

boolean parity = true;
...
    for (int j = i + 1; j < puzzle.length; j++) {
        if (puzzle[i] > puzzle[j] && puzzle[j] != 0) {
            parity = !parity;
        }
    }
...
if (gridWidth % 2 == 0) { // even grid
    if (blankRow % 2 == 0) { // blank on odd row; counting from bottom
        return parity;
    } else { // blank on even row; counting from bottom
        return !parity;
    }
} else { // odd grid
    return parity;
}

Now I noticed that the result only changes if it's an even grid and an even row. Otherwise we just return the parity. So let's combine those nested if's:

// even grid with blank on even row; counting from bottom
if (gridWidth % 2 == 0 && blankRow % 2 != 0) {
    return !parity;
}
return parity;

Now the same reasoning can be applied to the row and blankRow variables. We're actually only interested in whether the row containing the blank square is even or odd. So this could be a boolean too.

After a little bit of trial and error I ended up with this formula:

...
    if (puzzle[i] == 0) { // the blank tile
        blankRowOdd = (i / gridWidth) % 2==0;
        continue;
    }
...
// even grid with blank on even row; counting from top
if (gridWidth % 2 == 0 && blankRowOdd) { 
    return !parity;
}

Note also that we now check if it's an even row (in java starting with 0) from the top.

This results in the following final version. Note that I also made the method static since it doesn't depend on any state in the class.

public static boolean isSolvable(int[] puzzle) {
    boolean parity = true;
    int gridWidth = (int) Math.sqrt(puzzle.length);
    boolean blankRowEven = true; // the row with the blank tile

    for (int i = 0; i < puzzle.length; i++) {
        if (puzzle[i] == 0) { // the blank tile
            blankRowEven = (i / gridWidth) % 2==0;
            continue;
        }
        for (int j = i + 1; j < puzzle.length; j++) {
            if (puzzle[i] > puzzle[j] && puzzle[j] != 0) {
                parity = !parity;
            }
        }
    }

    // even grid with blank on even row; counting from top
    if (gridWidth % 2 == 0 && blankRowEven) { 
        return !parity;
    }
    return parity;
}

I don't think it will get much more readable than this. Except maybe finding a slightly better name for the parity variable. But I don't have the inspiration at the moment.

\$\endgroup\$
1
  • \$\begingroup\$ Actually there is an O(n) implementation. See my fixed answer. \$\endgroup\$ – user132961 Apr 14 '17 at 16:45
1
\$\begingroup\$

Some small things about commenting:

You can nearly remove all the comments. The common rule of comments (well it's not an universal rule, it is at least my rule): Do not write them at all. If you need a comment, you might want to rewrite the part, so you can read it without having to comment it.

The open source / linux rule is: Do not comment what you are doing, but why are you doing something.

int row = 0; // the current row we are on Why not call it currentRow? The problem is, on top, 'row' is declared, but if you use it later in the method, you have to have remembered, that it is the currentRow. And the more complex a method is, and the more stuff you have to remember, the harder it will be to understand.

And that part:

if (i % gridWidth == 0) { // advance to next row
    row++;
}

That's quite obvious. If a comment at all, write why you have to advance to the next row. If you have that question, you can mostly wrap it into another method, example: If you check if the heaven's blue and write something like heaven.getColor() == 12) // check if heaven is blue you can easily go with a method isHeavenBlue().

if (puzzle[i] == 0) { // the blank tile - more like "find the blank tile"? That part can be extracted to a separate method 'getBlankTile' as well, I guess...

And I think the 'top part', the calculation of the parity, can be extracted to a separate method 'calculateParity'. The lower part, too, I think. The goal should be, that a method tells the summary of a story or a book, and you can understand the story within a few lines, if you want the detail, jump into the private method. If you understand the story from its summary, it's much easier to understand the details.

\$\endgroup\$
2
  • \$\begingroup\$ Funny you should mention this, I've just read a book on commenting and how the programmer, the more experienced he got the less he commented \$\endgroup\$ – user3667111 Apr 21 '17 at 12:15
  • \$\begingroup\$ :-) ... That's one thing, another thing is: You can have code, you can have a comment and you can have specification - so basically, three different statements, but only one is true. Just had that problem last week and it took me about two to three hours to figure out, what's going on, which included calling the customer, study the changes of the classes involved and the corresponding issues in the tracker. And it was just a - but a very important - if-elseif block... If you like to read books, read 'Clean Code', there should be a free pdf version on the interwebs, too. \$\endgroup\$ – slowy Apr 21 '17 at 13:36

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.