Check if the 15 puzzle is solvable

J, 28 characters

((C.!.2=_1^i.&0)&.".&.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:

<nul set /p="0 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12" | jconsole c:\...\15.jhs

Explanation:

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

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.