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?

What did you learn when you stepped through this with a debugger? — Oliver Charlesworth
Define "odd parity". There are 2 moves that are required to solve that puzzle. Is that not "even parity"? — OneCricketeer
If I'm not mistaken, the position of the empty square is also relevant. It needs to go into the parity somehow. — Codo
@cricket_007 OP is referring to "amount of choosable pairs where the left value is greater than the right one, and neither are zero". — Siguza

Unknown Unknown · Accepted Answer · 2016-01-02T20:41:23

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

Check if 15 puzzle is solvable

1 Answers