Gridlocked · what makes a puzzle hard

A bigger maze isn't a harder maze.

We solved 14,163 sliding-block puzzles — every one of them exhaustively, to the last reachable position. The obvious measure of difficulty turns out to be worthless. Something less obvious predicts it almost perfectly. Every board on this page is a real puzzle from that set.

scroll
First, the game

Get the red car out.

Cars slide along their own axis only — horizontal cars left and right, vertical cars up and down. Nothing jumps, nothing rotates. The red car escapes through the gap on the right edge.

Drag the cars. This one takes six moves.

Try it — drag a car6 moves optimal
Moves: 0
The measurement

Every puzzle contains a hidden map.

From the starting position you might have eight legal moves. Each leads to a position with its own eight. Follow that outward and you get every arrangement the puzzle can ever reach — its state space.

That number is the puzzle's size. It's the first thing anyone measures, because it feels like it should mean something: a puzzle with 11,000 possible positions has to be harder than one with 400.

Here's every puzzle in the set, sorted by size. The scale is logarithmic — each step right is ten times bigger.

Distribution of puzzle size · 12,500 square puzzles bars = how many puzzles · line = how hard they were
Puzzle size spans four and a half orders of magnitude — from 11 positions to 293,765. If size drove difficulty, the amber line would climb steeply from left to right. It barely moves: a puzzle a thousand times larger takes about two more moves.
The problem

Size is a liar.

First, what “difficulty” means here: the fewest moves a perfect solver needs. More moves, harder puzzle. It's a proxy for human struggle, not the same thing — but it's objective, and we can compute it exactly for every puzzle.

So compare two real puzzles. The left one can reach 11,487 positions; the right one only 422 — twenty-seven times smaller. If size drove difficulty, the left should be far harder.

The big one

11,487 positions6 moves

The small one

422 positions17 moves
It's the other way round. The puzzle with 27× less room to move takes nearly three times as many moves to solve.

That's not a cherry-picked pair. Across all 14,163 puzzles, size and difficulty are statistically unrelated. Flip the axis below and watch a shapeless cloud snap into a line.

square hex sparse hex medium hex dense Y axis = moves to solve
550 real puzzles. Size tells you nothing — ρ = 0.03.
The thing that works

What has to move before what.

When a car moves into space another car just left, the second one depended on the first. Trace those hand-offs and every puzzle reveals a structure.

Two real puzzles below. Both take exactly six moves — by solution length they're identical. Step them together and watch the hand-offs form.

Separate hand-offs

6 movesdepth 2

One long chain

6 movesdepth 6
Press Step to play both solutions at once.
Left: three separate two-car hand-offs. Nothing waits on more than one thing, so you can work them in almost any order. Right: a single chain six cars long, where each car is waiting on the one before it — you have to see the whole sequence before the first move makes sense. Same six moves, and that's the difference dependency depth measures.

Now the same measurement on two puzzles that are identical in length — both exactly 11 moves. One has a depth of 3. The other, 11: every single move is a prerequisite for the next.

Depth 3 — shallow

11 movesdepth 3states 1,123

Depth 11 — one long chain

11 movesdepth 11states 47
Same solution length. The right-hand puzzle has one forced chain with no slack — and only 47 reachable positions, making it one of the smallest and hardest in the set.
The second thing that works

Sometimes you have to drive away from the exit.

The instinct is to shrink the gap between the red car and the exit on every move. In hard puzzles that instinct is a trap: the winning move often makes the position look worse.

We count the fraction of moves in the optimal solution that fail to make greedy progress. In the puzzle below, 9 of 11 moves — 82% — go the "wrong" way. Watch the distance meter climb.

Distance from red car to exitstep 0/11
82% of these moves make the position look worse.
The experiment

So we changed the shape of the world.

If dependency depth really governs difficulty, it should hold on a board that isn't a square grid at all. So we built one: a hexagonal board where pieces slide along three axes instead of two.

Nobody, as far as we can tell, has run Rush Hour on a hex grid before. It's not a reskin — the third axis genuinely changes the game.

Three axes of movementaxis 1 of 3
On a square grid a piece has 2 directions. Here it has 3.

Here's a real hex puzzle from the corpus — same rules, same red-piece-to-exit goal, but pieces now slide along whichever of the three axes they're laid on.

Real hex puzzle — drag a piecesolves in 5
Moves: 0
The hex result

The third axis drains the tension.

More freedom means fewer traps. Hex puzzles solve in 4.3 to 7.5 moves on average, against square's 12.2 — and their dependency chains are shorter at every density we tried. Give pieces an escape route and gridlock stops being gridlock.

But pack the board tighter and structure reasserts itself. As hex density rises, dependency depth predicts difficulty better and better — 0.66, then 0.76, then 0.83. Crowding is what manufactures depth.

Each bar: how strongly dependency depth predicts difficulty, by board type. The denser the hex board, the more structure matters.
Everything we measured

The scoreboard.

Five metrics, four board types, 14,163 puzzles. Each dot is how strongly that metric tracked difficulty on one board type — further right means a stronger relationship.

square hex sparse hex medium hex dense clustered dots = holds on every board type
dependency depthρ 0.61 – 0.83
The longest chain of “this must move before that.”
How many consequences deep you have to plan. Strongest predictor on every board type we tested, and it gets stronger as boards get crowded. Two puzzles of identical length can differ by 8 in depth — and it's the depth you feel.
−0.6no relationship+0.9
counterintuitive fractionρ 0.44 – 0.75
Share of moves that make the position look worse.
Greedy play — always close the gap to the exit — is how people get stuck. Puzzles that punish that instinct measure as harder. We use the fraction rather than the raw count, because longer solutions rack up more of them for free.
−0.6no relationship+0.9
optimal solutionsρ 0.46 – 0.68
How many genuinely different shortest solutions exist.
The surprise: harder puzzles have more, not fewer. The median Rush Hour puzzle has 484 distinct optimal solutions — one in our set has 640,980. The romantic idea of “the one clever line” is mostly a myth; difficulty lives in the size of the forest, not the rarity of the path.
−0.6no relationship+0.9
tightest momentρ −0.35 – −0.18
Fewest legal moves available at any point in the solution.
A promising idea — the pinch point where the puzzle allows only one move — that mostly didn't pan out. It leans the right way (tighter is harder) but weakly and inconsistently. Included because not every structural metric worked, and pretending otherwise would be dishonest.
−0.6no relationship+0.9
puzzle sizeρ −0.11 – 0.15
Total positions the puzzle can reach.
The intuitive answer, and the one this whole study set out to test. On two different geometries and four densities it hovered at zero — sometimes negative. A vast state space can hide a six-move solution. A 47-position puzzle can take eleven moves and be brutal.
−0.6no relationship+0.9
What "difficulty" means here. We measure against the minimum number of moves a perfect solver needs — an objective proxy, not human struggle. Whether people feel these puzzles as harder is the obvious next experiment, and it needs human-labelled puzzles.
The square numbers are externally verified. Our solver's move counts matched an independent 2.5-million-puzzle reference database on every puzzle we sampled. The hex numbers have no such reference — no one has built one — so they rest on our solver alone.
Method. 12,500 square puzzles sampled from Fogleman's complete 6×6 database; 1,663 hex puzzles generated across three densities. Every puzzle solved exhaustively. Spearman rank correlation. Dependency depth averaged over 8 sampled optimal solutions per puzzle, because most puzzles have many.

Play it yourself.

Gridlocked is the game these puzzles come from — square and hex, both playable in the browser.

PLAY THE FULL GAME
Square and hex, both playable in the browser — free on itch.io.
Play on itch.io

Gridlocked · Orbitope