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?

Planetoid

What did you learn when you stepped through this with a debugger? – Basie

Define "odd parity". There are 2 moves that are required to solve that puzzle. Is that not "even parity"? – Shredding

If I'm not mistaken, the position of the empty square is also relevant. It needs to go into the parity somehow. – Metz

@cricket_007 OP is referring to "amount of choosable pairs where the left value is greater than the right one, and neither are zero". – Barnum

@Metz Could it be the row the empty square is in...? – Barnum

Rearrange the squares so that the free position is in the lower right hand corner, and then compute even/odd for the permutation. – Tinker

@Tinker It does not matter where the blank square is located. – Farias

Would making the parity be 1 if it is not in the bottom right help? – Shredding

@cricket_007 It is not about manipulating the parity. The parity is calculated and its value is used to determine if the puzzle can be solved. – Farias

@nautical You contradict yourself since "these conditions" you found and your code both take heed of the location of the blank square. Note that my "rearrange" merely eliminates the need to consider its position in the even/odd computation, which the rearrangement does not affect. – Tinker

@Tinker Poorly phrased on my part. What I mean is, that the algorithm is not about a possible way to solve it or making any rearrangements. The algorithm must only determine if it is solvable at all. In order to determine this the blank tile may be in any position that could be reached from its initial position; by legal moves only. The algorithm must yield the same result for any of those legal positions without the need of rearranging the tiles. So to render my previous statement more precisely: The applicability of the algorithm does not depend on the tile being in a particular position. – Farias

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

Farias

Would this still apply to an N x M puzzle? – Dibbuk

The parity also depends on the goal state here. There are 2 common goal states used, one has the 0 in the top left hand corner and the other has the 0 in the bottom right hand corner. You have to swap the parity depending on which goal state you choose when the number of columns is even. For odd number of columns it does not matter. – Hickson

@NickLarsen what do you mean by swap the parity? If the goal state has 0 in the top left corner does the above function change? If yes, what must be changed. Can you elaborate more on swap parity? – Enidenigma

Answer 2

What am I doing wrong?

For your regular 15-puzzle, you have to arrange the tiles such that the blank space is in the lower right corner. For example, in your case,

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

(I removed the 0 tile.)

In this way, you can check the parity of this permutation:

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

which is not the same one you are using. This permutation is even, thus solvable, as you may check. In this way, your intuition is right, it should be even parity.

This is true for square puzzles of any dimension. Consider, for example, a game not solvable of only 3 tiles (2 by 2):

2 
3  1

You may say the permutation 2 3 1 is even (which is true). But it is not the right permutation for

2  1
3

which is 2 1 3 and this, in fact, is odd, and so not solvable.

Duren

Answer 3

The existing answer should work but does not address the question

What am i doing wrong?

You have the right idea. The parity of the permutation of the 15 numbered tiles should indicate solubility (if even) or insolubility (if odd) regardless of the position of the "blank"/0 tile - see [1].

The problem is that the solved state of the puzzle should be numbered such that you can trace a continuous path from low to high, e.g.

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

This makes it more obvious why the position of the blank tile is unimportant - it can be moved along the path from beginning to end without changing the order of the other tiles.

After your two moves, the puzzle will look like this:

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

which has 6 inversions (only the 9 is out of place) and so even parity.

You'd have to either change how the puzzle is displayed in two dimensions or change the order in which you check tiles to count inversions. This solution should extend to any MxN rectangular grid where M >= 2 and N >= 2, and any position of the blank tile.

[1] Archer, Aaron F. (1999), "A modern treatment of the 15 puzzle", The American Mathematical Monthly, 106 (9): 793–799

Glee