Check if the 15 puzzle is solvable The fifteen puzzle is peculiar in that only half the possible states of arrangement are solvable. If you flip the 14 and 15 tiles, there is no way you can slide the blocks so that they are flipped back.

Your task is to build a program that accepts a list of integers in the format of your choice (containing exactly one instance of each of the numbers from 0 to 15, with 0 being the blank space) representing the state of an arrangement of tiles in a 4x4 grid, and outputs a single boolean value determining whether the grid is solvable or not.

The shortest code to do this in any language wins.
J, 28 characters
((C.!.2=_1^i.&amp;0)&amp;.&quot;.&amp;.stdin''

The input order is row-major with rows read alternatingly left to right and right to left in a single path across the table. Assumes the zero belongs to the top left corner.
Usage on Windows:
&lt;nul set /p=&quot;0 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12&quot; | jconsole c:\...\15.jhs

Explanation:

&lt;nul set /p= is used to prevent a newline in the input, that echo produces that &quot;. doesn't like. Of course, Unix supports echo /n.
v&amp;.&quot;.&amp;.stdin'' reads &quot;v under parse under stdin&quot; meaning &quot;input, then parse the input, then do v, then undo parse (= format), then undo input (=output)&quot;. 1!:1]3 is one character shorter, but it does not have a defined inverse.
C.!.2 means &quot;permutation parity&quot;. It returns either 1 (even parity) or _1 (odd parity). That is, _1^inversions
_1^i.&amp;0 means &quot;-1 to the power of index of 0&quot;.
thus, C.!.2=_1^i.&amp;0 means &quot;does the permutation parity equal the hole position parity?&quot;

This works for a 4x4 board, but if the desired end position is row-major left-to-right, then the permutation for the solved position has an odd number of inversions, and thus odd parity. Also, the parity is reversed (for any input order) when the desired hole position moves from upper left to bottom right. In both cases, the fix is one character: add - after = to reverse the expected parity.
Proof of correctness:
After each move, the zero exchanges a position with some number, flipping the permutation parity. The zero also alternates between white and black checkerboard positions, indicated by odd and even positions in the input ordering. Thus, this condition is neccessary. It is also sufficient by the counting argument: it is common knowledge that exactly half of the positions is solvable. This condition filters out exactly half of the possible positions.