Check if 15 puzzle is solvable

Question

I'm trying to test whether a 15 puzzle is solvable. I wrote a method which is working for most puzzles, but for some not.

For example this puzzle can be solved with two moves (0, 11), (0, 12)

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 11, 13, 14, 15, 12

Here is the puzzle better visualized:

1   2   3   4   

5   6   7   8   

9   10  0   11  

13  14  15  12  

But the puzzle has a odd parity of 3 and so should not be solvable.

public boolean isSolvable(int[] puzzle)
{
    int parity = 0;

    for (int i = 0; i < puzzle.length; i++)
    {
        for (int j = i + 1; j < puzzle.length; j++)
        {
            if (puzzle[i] > puzzle[j] && puzzle[i] != 0 && puzzle[j] != 0)
            {
                parity++;
            }
        }
    }

    if (parity % 2 == 0)
    {
        return true;
    }
    return false;
}

What am i doing wrong?

Answer 1

I found these conditions that need to be checked for any N x N puzzle in order to determine if it is solvable.

Apparently, since your blank tile is on an even row (counting from the bottom), parity is odd and your grid-width is even, this puzzle is solvable.

This is the algorithm that checks according to the rules in the link:

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