Sliding Puzzle

The frame holds fifteen numbered tiles and one empty square, and the only legal move is to push a tile sideways into the gap beside it. Putting them back in order looks like a shuffling problem, but underneath it is a parity problem: exactly half of the ways those tiles can sit in the frame cannot be reached from a finished board at all, however long you push. The board below is never one of those, and what follows is what it does instead of scrambling.

Every page in this section

Half of all tile arrangements have no solution

Sixteen squares holding fifteen tiles and a gap can be arranged in 20,922,789,888,000 ways. Exactly half of those – 10,461,394,944,000 – can be reached from the finished board by sliding tiles one at a time. The other half are not hard, they are impossible, and there is nothing on the face of a frame that tells you which half you are holding.

The dividing line is a count called inversions. Read the tiles in reading order, ignore the gap, and count the pairs that come out in the wrong order relative to each other. A sideways slide leaves that count untouched. A vertical slide on a four-wide board jumps a tile over three others, changing the count by an odd number, and it also moves the gap up or down one row. So the inversion count plus the gap’s row measured from the bottom is a quantity no legal move can ever flip: on a finished board it is odd, and on every board you can finish it is still odd.

The neatest demonstration is one exchange. Take a frame you could finish, lift two tiles out and put them back the other way round, and you have made a puzzle nobody can finish – that single swap changes the inversion count by an odd number and drops you in the other half. It is the old cruelty of the physical toy: two tiles, prised out and replaced backwards, and the thing will never come out again.

Why this board shuffles by playing, not by scrambling

A board built by shuffling its tile array hands an unsolvable frame to roughly every second visitor, who pushes at the last two tiles for ten minutes and leaves. So this one never shuffles the tiles. It starts from the finished position and makes 192 random legal moves, which is a walk through the reachable half that cannot possibly leave it, so there is no parity repair afterwards to get wrong. The walk also declines to reverse the move it has just made, because a walk allowed to step back and forth spends most of its moves standing still and hands you a board three slides from home.

What the frame gives you while you play

Tap any tile touching the gap, or steer with the arrow keys – the arrow names the direction the tile travels, not the direction the gap travels. The whole grid is one tab stop rather than sixteen, so reaching the buttons underneath does not mean tabbing across the board first. There is no dragging anywhere, because a drag on a touch screen fights the page scroll the frame is sitting in.

The move count and the clock sit above the frame, and the clock starts on your first move rather than on page load, so scrolling past and coming back ten minutes later costs you nothing. A tile already sitting in its home square is tinted and carries a small dot in its corner – the dot is there because the tint disappears under a picture. Hint marks one tile with a dashed outline and names it below the board. The Picture button re-cuts the tiles from a drawing made inside the page rather than downloaded, and every slice keeps its number printed in the corner, so a tile that happens to be a patch of flat sky is still identifiable.

This frame and the 15 puzzle page are the same four rows

Said plainly, because the two look like a size and a variant and they are not. Both draw a four-by-four frame holding fifteen numbered tiles, scrambled by the same walk from the same finished position. What differs is what each page is for. This one is about why the scramble has to be a walk at all: the parity argument above is the whole reason, and it is the single fact about this puzzle that changes what you do with a physical set on a shelf. The 15 puzzle page takes the frame as given and sets out the order that finishes it, tile by tile, including the pair at the end of every row that cannot be placed one at a time. If you want three rows rather than four, the eight-tile frame is small enough that every reachable position has been measured, which is why its hints can promise you a number on every single move, where this frame only begins printing one over the last twenty-two. All three are the same sliding tile puzzle underneath, and a sliding puzzle online is worth having as three pages only because there are three separate things worth saying about it.