Library

DFA · Regular

A 2 × 2 sliding puzzle

Three tiles and a gap; a move slides the gap up, down, left or right. Of the 24 ways to place three tiles and a gap, only 12 can be reached — and that is the 15-puzzle’s famous parity argument in miniature: every move is a swap, and the gap returns to its corner only after an even number of them.

123_1_3212_3_132_21331_22_13312_231_3_2123_1_321ULDLURDRDRURDLULULDLURDR
The machine as drawn — 12 states, 24 transitions.Every word up to length 4, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptLRUD → acceptLUDR → acceptULRD → acceptU → rejectURUD → rejectUUDR → rejectDLRD → reject