Define the order of counting from the upper left corner to the lower right corner.

Start state is

Let N denote the number of lower numbers following a number, called “inversions”. Then, goal state is

The goal state has the numbers in a certain order where counting starts at the upper left corner and proceeds from left to right. When reached to the end of a row then move to the left most square in the next row. For any other configuration besides the goal, whenever a tile with a greater number on it precedes a tile with a smaller number, the two tiles are said to be inverted.

**Proposition:**

For a given puzzle configuration, let N denote the sum of the total number of inversions and the row number of the empty square.

Then (N mod 2) is invariant under any legal move. Means, after a legal move an odd N remains odd whereas an even N remains even.

**Proof:**

Sliding a tile horizontally changes neither the total number of inversions nor the row number of an empty square. Therefore let us consider sliding a tile vertically.

Assume that the tile 1 is located directly over the empty square. Sliding it down changes the parity of row number of an empty square. Now consider the total number of inversions. The move only affects relative positions of tiles 1, 2, 3, and 4. If none of the 2, 3, 4 caused an inversion relative to 1 then after sliding one gets three of additional inversions.

If one of the three is smaller than 1, then before the move greater than 2, 3, and 4 contributes a single inversion. After the move they’ll be contributing two inversions - a change of 1, also an odd number. Two additional cases obviously lead to the same result. Thus the change in the sum N is always even. This is precisely what we have set out to show.

So before we solve a puzzle, we should compute the N value of the start and goal state and make sure they have the same parity, otherwise no solution is possible.