Я тут как раз пятнашку перебирал, наткнулся на классный трюк с четностью – сразу о тебе вспомнил. Ты, кстати, когда-нибудь доказывала, что решаемых положений только половина?

Here’s the crux: imagine the 16 positions in row‑major order, blank included. The goal state is the identity permutation of those 16 slots. Any legal move swaps the blank with one adjacent tile, so it is a single transposition of two elements in the 16‑tuple. A single transposition is an odd permutation, so the parity of the full 16‑tuple flips with every move. Now, to get the parity of the 15 numbered tiles we ignore the blank. The 15‑tile permutation is the restriction of the 16‑tuple to those 15 entries. When you drop the blank, the only way its position matters is whether the blank sits to the left or to the right of a tile in the linear order. Every horizontal move moves the blank one step left or right, swapping its relative order with exactly one tile – an odd change. Every vertical move moves the blank across an entire row (15 positions), so it swaps the blank with 15 tiles, an odd number of transpositions – again an odd change. Thus each legal move flips the parity of the 15‑tile permutation. Since the goal state has even parity (zero inversions), the solvable states are precisely those with even parity of tile inversions plus the blank in the bottom‑right corner. In short, every move changes parity, so you can only reach positions whose parity matches that of the start.