Check if the 15 puzzle is solvable

Question

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.

Answer 1

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.

Answer 2

Jelly, 9 bytes

Œc>/€;TSḂ

A monadic Link accepting a list of the integers reading in row-major order alternating between left-right and right-left which yields 0 if solvable and 1 if not (to invert this add ¬ to the right of the code).

Try it online! (this example is a board where 12 just needs to slide into place)

How?

Similar to John Dvorak's answer we calculate parities and utilise a snake-like input order to simplify checker-board parity, although instead of checking equality of parity we sum the out-of-order count with the non-zero indices and test whether that is odd:

Œc>/€;TSḂ - Link: list of integers
Œc        - unordered pairs
    €     - for each:
   /      -   reduce with:
  >       -     greater than?
      T   - truthy indices (i.e. [1..16] without 1-indexed index of 0)
     ;    - concatenate
       S  - sum
        Ḃ - is odd?