Rush Hour is the little plastic grid with the traffic jam: a 6×6 board, a dozen cars and trucks that can only slide along the direction they point, and one red car that has to get out through the gap on the right. It looks like a toy. It is actually the friendliest introduction to state-space search I know, because the puzzle is small enough to hold in your head and the search is small enough to run on every single move.
I built a playable version in vanilla JavaScript on one canvas, with drag-to-slide, a generator that verifies its own puzzles, and a solver that returns the provably shortest escape. Here is how the pieces fit.
The board is a list of pieces, not a picture
The tempting model is a 6×6 array of characters. It quietly ruins everything downstream, because the thing that actually exists in this puzzle is about a dozen vehicles, and each one is fully described by four facts.
const N = 6, EXIT_ROW = 2;
const pieces = [
{ id:0, row:2, col:0, len:2, orient:"H" }, // the red car, always on the exit row
{ id:1, row:0, col:2, len:2, orient:"V" },
{ id:2, row:2, col:3, len:3, orient:"V" },
];
function cellsOf(p) {
const out = [];
for (let k = 0; k < p.len; k++)
out.push(p.orient === "H" ? [p.row, p.col + k] : [p.row + k, p.col]);
return out;
}
That is the whole board: eleven records, forty-four numbers. You still need to answer "who is standing on this cell" constantly, so build the grid — but build it fresh from the list every time and throw it away.
function occupancy(pieces) {
const g = new Int8Array(N * N).fill(-1); // -1 = empty
for (let i = 0; i < pieces.length; i++)
for (const [r, c] of cellsOf(pieces[i]))
g[r * N + c] = i; // store WHO, not just "taken"
return g;
}
Caching that grid looks like an optimisation and is really an invitation for the two representations to disagree after some move you forgot to update. Rebuilding costs about thirty writes. Store the piece index rather than a boolean, because "which vehicle is blocking me" turns out to be the more useful answer.
The entire rulebook is one function
A vehicle is axis-locked: horizontal pieces change only their column, vertical pieces only their row. Nothing rotates, nothing lifts over anything. So there is exactly one degree of freedom per piece, and the only question is how far it can travel each way.
function slideRange(pieces, i, grid) {
const g = grid || occupancy(pieces), p = pieces[i];
let back = 0, fwd = 0;
if (p.orient === "H") {
let c = p.col - 1; while (c >= 0 && g[p.row*N + c] === -1) { back--; c--; }
c = p.col + p.len; while (c < N && g[p.row*N + c] === -1) { fwd++; c++; }
} else {
let r = p.row - 1; while (r >= 0 && g[r*N + p.col] === -1) { back--; r--; }
r = p.row + p.len; while (r < N && g[r*N + p.col] === -1) { fwd++; r++; }
}
return { min: back, max: fwd };
}
Twelve lines, and two properties fall out for free. Because you stop at the first occupied cell, a piece can never pass through traffic. Because you stop at the wall, it can never leave the board. There is no separate collision test anywhere in the codebase — the range is the collision test.
I fuzzed this: 400 random boards, every legal move applied, checking for overlaps and off-board placements. Zero. And the range is tight — one cell past either end is always illegal, in every position tested.
A move is a delta, not a swap
Tile puzzles teach you to think in swaps: exchange the blank with a neighbour. That instinct is wrong here, because a vehicle covers two or three cells and can travel several cells at once. A move is a pair — which piece, by how much — and a slide of any distance counts as one move. That is the standard Rush Hour metric, and it is what makes "optimal 8" mean something.
function legalMoves(pieces) {
const g = occupancy(pieces), out = [];
for (let i = 0; i < pieces.length; i++) {
const { min, max } = slideRange(pieces, i, g);
for (let d = min; d <= max; d++) if (d !== 0) out.push({ i, d });
}
return out;
}
function applyMove(pieces, i, d) {
const next = pieces.map(p => ({ ...p })); // immutable: the search depends on it
if (next[i].orient === "H") next[i].col += d; else next[i].row += d;
return next;
}
Copying instead of mutating is what lets the search hold thousands of boards at once without them corrupting each other. It also makes undo embarrassingly cheap: push a snapshot before the move, pop it after. No inverse move to derive, no edge cases when the auto-solver is halfway through a run.
Squashing a board into one canonical string
To search a puzzle you must be able to say "I have been here before", and comparing lists of objects is both slow and wrong. Slow because it is a deep comparison. Wrong because the same picture written in a different array order would look like a brand new position.
So paint the 36 cells instead, and label each by what kind of thing sits on it.
function key(pieces) {
const s = new Array(N * N).fill(".");
for (const p of pieces) {
const ch = p.id === 0 ? "X"
: p.orient === "H" ? (p.len === 2 ? "h" : "H")
: (p.len === 2 ? "v" : "V");
for (const [r, c] of cellsOf(p)) s[r * N + c] = ch;
}
return s.join("");
}
Shuffle the piece array and the key comes out byte-for-byte identical, because it is built from the grid. Two identical trucks are genuinely interchangeable in this puzzle, so merging them is not a lossy shortcut — it is a real collapse of duplicate states that shrinks the search.
BFS finds the shortest escape; DFS finds only an escape
Once positions are nodes and moves are edges, solving is graph search, and the container decides what you get. A queue explores in rings: everything one move from the start, then everything two moves away. Because a ring finishes before the next begins, the first winning board you touch is reached in the fewest possible moves. That is a proof, not a hope.
function solve(pieces, cap = 400000) {
const start = pieces.map(p => ({ ...p }));
const q = [start], parent = [-1], moveOf = [null];
const seen = new Set([key(start)]);
let head = 0, explored = 0;
while (head < q.length && explored < cap) {
const cur = q[head], idx = head++; explored++;
if (isWin(cur)) { // first hit = shortest, by construction
const moves = [];
for (let k = idx; parent[k] !== -1; k = parent[k]) moves.push(moveOf[k]);
return { solvable: true, moves: moves.reverse(), states: explored };
}
for (const m of legalMoves(cur)) {
const nx = applyMove(cur, m.i, m.d), kk = key(nx);
if (seen.has(kk)) continue; // already reached, never on a shorter path
seen.add(kk); q.push(nx); parent.push(idx); moveOf.push(m);
}
}
return { solvable: false, moves: null, states: explored };
}
Swap the queue for a stack and you have depth-first search, which dives down one branch until it dead-ends and will happily hand back a wandering hundred-move solution to a twelve-move puzzle. Both find an answer. Only one finds the answer worth showing a player next to their own move count.
Two details matter more than they look. The visited set must key on the whole board — beginners try to prune on "where is the red car", and two boards with the red car in the same place can be completely different puzzles, so that throws away solutions. And you mark a key when you push a child, not when you pop it, or the same position gets queued a dozen times by different parents before any of them is examined.
I checked the results against two independent searches — a level-synchronous BFS written separately, and an iterative-deepening DFS — and all three agree on every built-in puzzle. The hardest one on the page is 22 moves and takes 1,695 popped states.
Generate, then verify
Scattering vehicles at random almost never produces a puzzle worth playing. Most boards are trivially open and plenty are impossible. Rather than being clever about placement, be honest about verification: scatter, run the solver, throw away anything unsolvable or easier than you asked for.
for (let t = 0; t < tries; t++) {
const pieces = [{ id:0, row:EXIT_ROW, col:ri(3), len:2, orient:"H" }];
while (pieces.length < want) {
const cand = randomVehicle();
if (cand.orient === "H" && cand.row === EXIT_ROW) continue; // a permanent wall
if (!fits(pieces, cand)) continue;
pieces.push(cand);
}
const res = solve(pieces, 200000); // VERIFY — do not hope
if (res.solvable && res.moves.length >= minMoves) return pieces;
}
Rejection sampling sounds wasteful and is not, because each solve takes milliseconds. One placement rule removes most of the failures for free: a horizontal vehicle parked on the exit row can never leave that row, so any one of them sitting to the right of the red car makes escape impossible by construction.
The nice consequence is that "this puzzle has no solution" becomes impossible by design. Every jam the Generate button hands you has already been solved by the thing that handed it to you.
An honest hint
The lazy hint stores the solution at load time and reads the next move off it. It breaks the moment the player deviates — which is the exact moment they wanted help. Since a solve is a couple of milliseconds, just run it again from wherever the board actually is:
function doHint() {
const res = solve(pieces); // from HERE, not from the start
hint = res.solvable && res.moves.length ? res.moves[0] : null;
remaining = res.solvable ? res.moves.length : -1;
render();
}
The same call gives a second, more interesting number: how many moves remain if you now play perfectly. Watch it go up after a careless slide and the page stops being a walkthrough and starts being a teaching tool, because you can see exactly which move cost you and how much.
Dragging, snapped and clamped
A drag feels continuous but the model is discrete, so convert at the earliest possible moment rather than carrying pixels around.
canvas.addEventListener("pointermove", e => {
if (!drag) return;
const p = toCanvas(e), pc = pieces[drag.i];
const raw = pc.orient === "H" ? (p.x - drag.x) / CELL : (p.y - drag.y) / CELL;
const d = Math.max(drag.range.min, Math.min(drag.range.max, Math.round(raw)));
if (d !== drag.off) { drag.off = d; render(); } // snapped AND clamped
});
The clamp is the half players actually feel: the vehicle visibly refuses to pass through a car while your finger keeps travelling, which teaches the rule better than any message could. Release with a delta of zero and it was just a tap that selected the piece. And set touch-action: none on the canvas, or a phone reads the drag as a scroll and the game is unplayable.
Why the brute force works here, and where it stops
A 6×6 jam has twenty to thirty moves available per position and a few thousand reachable positions, so plain BFS wins outright. That comfort is an accident of the board size. Generalise to an n×n grid and the configurations grow exponentially, solutions themselves can be exponentially long, and the generalised problem is PSPACE-complete — the same class as generalised sliding-block puzzles. Nobody has a shortcut that scales.
For bigger boards you switch to A* with an admissible heuristic. The obvious one never overestimates and is three lines:
function blockers(pieces) {
const g = occupancy(pieces), red = pieces.find(p => p.id === 0);
const set = new Set();
for (let c = red.col + red.len; c < N; c++) {
const i = g[EXIT_ROW * N + c];
if (i >= 0) set.add(i);
}
return set.size; // at least one move per distinct vehicle in the way
}
A list of {row, col, len, orient} records, one function that counts empty cells ahead and behind, and a queue. Everything else — legal moves, undo, an honest hint, a trustworthy generator, a provably optimal auto-solve — falls out of those three.
Play it, hit Generate for a jam nobody has ever seen, and copy the nine build blocks here: https://dev48v.infy.uk/game/day60-rush-hour.html
Top comments (0)