Introduction

Rush Hour is the plastic puzzle on a 6×6 grid where cars and trucks can only slide along their own lane. One car is red, and your single goal is to slide everything else out of its way so the red car can drive out the exit on the right.

Each individual move is laughably simple: a car shifts one square forward or back, if nothing blocks it. There is no scoring, no hidden information, no randomness — you can see the whole board.

And yet a packed board can leave you stuck for an hour. Every car you nudge forces three others to move first, which forces others still. The question "can the red car ever get out?" turns out to have no shortcut — answering it is as hard as any problem that fits in a reasonable amount of memory.

Free the Red Car

Here is a small Rush Hour board. The red car wants to reach the exit on the right edge. Click a car to select it, then use the arrows to slide it along its lane. A car can only move into empty squares, and only along the direction it is oriented.

<p class="hint">The <b>red</b> car must reach the exit (the gap on the right edge of its row). Click a car to select it, then use the arrows to slide it along its lane. Each move is trivial — but knowing whether the red car can <i>ever</i> get out means searching every reachable board.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Select a car and slide it.</div>
<div class="btns">
  <button id="left"  type="button">◀</button>
  <button id="right" type="button">▶</button>
  <button id="up"    type="button">▲</button>
  <button id="down"  type="button">▼</button>
  <button id="solve" type="button">Solve</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { position: relative; width: 280px; height: 280px; background: #e8eef3;
         border: 2px solid #cdd9e3; border-radius: 10px; margin: .4rem 0; }
.exit { position: absolute; right: -2px; width: 6px; height: 46px; background: #0a7d33;
        border-radius: 3px; }
.car { position: absolute; border-radius: 8px; cursor: pointer; transition: all .12s ease;
       border: 2px solid rgba(0,0,0,.18); }
.car.sel { outline: 3px solid #1d3557; outline-offset: 1px; z-index: 2; }
.car.red { background: #e63946; }
.car.c1 { background: #4895ef; } .car.c2 { background: #f4a261; }
.car.c3 { background: #8d99ae; } .car.c4 { background: #b5838d; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 15px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; min-width: 42px; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Generalized Rush Hour is PSPACE-complete (Flake & Baum, 2002). On a fixed board
// we just search: every legal slide leads to a new board STATE, and the only sure
// way to know if the red car can escape is a breadth-first search over all reachable states. Watch the explored-states counter climb even on this tiny 5x5 board.
const N = 5, CELL = 56, GAP = 2; // logical grid N x N
// Cars: id, orientation h/v, length, row, col (top-left). ’red’ is horizontal, exits right.
const START = [
  { id:'red', o:'h', len:2, r:2, c:0, cls:'red' },
  { id:'A',   o:'v', len:2, r:1, c:2, cls:'c1'  },
  { id:'B',   o:'v', len:2, r:0, c:3, cls:'c2'  },
  { id:'C',   o:'h', len:2, r:4, c:0, cls:'c3'  },
  { id:'D',   o:'v', len:2, r:2, c:4, cls:'c4'  },
];
let cars = clone(START), sel = 'red';
function clone(cs){ return cs.map(c => ({...c})); }

// Occupancy grid for a configuration (excluding optionally one car).
function grid(cs, skip){
  const g = Array.from({length:N}, () => Array(N).fill(null));
  for(const c of cs){ if(c.id===skip) continue;
    for(let i=0;i<c.len;i++){ const r=c.r+(c.o==='v'?i:0), col=c.c+(c.o==='h'?i:0); g[r][col]=c.id; } }
  return g;
}
// Can car `id` move by step (-1/+1) along its lane? Returns the moved car list or null.
function move(cs, id, step){
  const c = cs.find(x=>x.id===id); if(!c) return null;
  const g = grid(cs, id);
  let nr=c.r, nc=c.c;
  if(c.o==='h') nc+=step; else nr+=step;
  // the single new leading cell that gets occupied
  const lead = step>0
    ? (c.o==='h' ? [c.r, c.c+c.len] : [c.r+c.len, c.c])
    : (c.o==='h' ? [c.r, c.c-1]     : [c.r-1, c.c]);
  const [lr,lc] = lead;
  if(lr<0||lr>=N||lc<0||lc>=N) return null;
  if(g[lr][lc]!==null) return null;
  const out = clone(cs); const m = out.find(x=>x.id===id); m.r=nr; m.c=nc; return out;
}
// Solved iff red’s right edge touches the exit column (col N-1 occupied by red’s tail).
function solved(cs){ const red=cs.find(x=>x.id==='red'); return red.c+red.len-1 === N-1; }
function key(cs){ return cs.map(c=>c.id+c.r+','+c.c).sort().join('|'); }

// BFS over board states; returns {steps, path} where steps = states explored.
function bfs(cs){
  const start=key(cs); const seen=new Set([start]);
  const q=[{cs:clone(cs), path:[]}]; let explored=0;
  while(q.length){
    const cur=q.shift(); explored++;
    if(solved(cur.cs)) return {explored, path:cur.path, win:true};
    for(const car of cur.cs){
      for(const step of [-1,1]){
        const nxt=move(cur.cs, car.id, step);
        if(!nxt) continue;
        const k=key(nxt);
        if(seen.has(k)) continue;
        seen.add(k);
        q.push({cs:nxt, path:[...cur.path, [car.id, step]]});
      }
    }
  }
  return {explored, path:null, win:false};
}

const boardEl=document.getElementById('board');
function render(){
  boardEl.innerHTML='';
  const exit=document.createElement('div'); exit.className='exit';
  exit.style.top=(2*CELL+GAP)+'px'; boardEl.appendChild(exit);
  for(const c of cars){
    const el=document.createElement('div');
    el.className='car '+c.cls+(c.id===sel?' sel':'');
    const w=(c.o==='h'?c.len:1), h=(c.o==='v'?c.len:1);
    el.style.left=(c.c*CELL+GAP)+'px'; el.style.top=(c.r*CELL+GAP)+'px';
    el.style.width=(w*CELL-2*GAP)+'px'; el.style.height=(h*CELL-2*GAP)+'px';
    el.addEventListener('click',()=>{ sel=c.id; render(); });
    boardEl.appendChild(el);
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }
function tryMove(step, vertical){
  const c=cars.find(x=>x.id===sel); if(!c) return;
  if((vertical && c.o!=='v') || (!vertical && c.o!=='h')){ setStatus('That car can’t move that way.','bad'); return; }
  const nxt=move(cars, sel, step);
  if(!nxt){ setStatus('Blocked — something is in the way.','bad'); return; }
  cars=nxt;
  if(solved(cars)){ render(); setStatus('✓ The red car escaped!','ok'); return; }
  render(); setStatus('Keep sliding to free the red car.','');
}
document.getElementById('left').addEventListener('click',()=>tryMove(-1,false));
document.getElementById('right').addEventListener('click',()=>tryMove(1,false));
document.getElementById('up').addEventListener('click',()=>tryMove(-1,true));
document.getElementById('down').addEventListener('click',()=>tryMove(1,true));
document.getElementById('reset').addEventListener('click',()=>{ cars=clone(START); sel='red'; render(); setStatus('Select a car and slide it.',''); });
document.getElementById('solve').addEventListener('click',()=>{
  const res=bfs(cars);
  if(!res.win){ setStatus(fmt('No escape exists — explored %explored% states.', { explored: res.explored }),'bad'); return; }
  // replay the solution path
  let i=0;
  setStatus(fmt('Solved in %length% moves — explored %explored% board states.', { length: res.path.length, explored: res.explored }),'ok');
  console.log('Solution:', res.path.map(p=>p[0]+(p[1]>0?'+':'-')).join(' '), '| explored', res.explored, 'states');
  const timer=setInterval(()=>{
    if(i>=res.path.length){ clearInterval(timer); return; }
    const [id,step]=res.path[i++]; const nxt=move(cars,id,step); if(nxt){ cars=nxt; sel=id; render(); }
  }, 350);
});
render(); setStatus('Select a car and slide it.','');
Result
Console

Try to free the red car by hand — then press Solve and watch the computer do a breadth-first search over every reachable arrangement of cars. The counter shows how many distinct board states it had to explore. Even on this tiny board the number is surprising; on a full 6×6 board it explodes, because the only known way to be sure a board is unsolvable is to walk the whole state space.

The Real Complexity

How hard is Rush Hour, really? Not sliding one car — deciding whether the red car can escape at all.

  • Each move is trivial. Sliding a single car is instant, and checking whether a given board is already solved is just looking at the red car's row.
  • Brute force walks the state space. The honest method is breadth-first search over every reachable arrangement of cars. On an n×n board the number of states grows exponentially, so this is hopeless at scale.
  • It's PSPACE-complete. In 2002, Gary Flake and Eric Baum proved that generalized Rush Hour (on boards of arbitrary size) is PSPACE-complete. They built sliding "logic" gadgets out of cars and showed that any computation using polynomial memory can be encoded as a Rush Hour board whose red car escapes exactly when that computation accepts.
  • So PSPACE-complete means Rush Hour is at least as hard as every problem solvable with a polynomial amount of memory — a class that contains all of NP and is widely believed to be even larger.

That is the punchline. Unlike a one-shot puzzle like SAT, Rush Hour's difficulty comes from the long sequence of moves you must plan ahead — the hallmark of PSPACE. Many two-player games and reachability puzzles share exactly this flavor of hardness, where the challenge is not one clever guess but a whole reachable space you cannot shortcut. It is a cousin of the questions behind P vs NP.

Where It Matters

"Can I reach a goal configuration by a long chain of legal moves?" is one of the most common shapes a real problem takes, and Rush Hour is its friendly face:

  • Motion and rearrangement planning: a robot shuffling boxes in a cluttered warehouse, or parking cars in a tight lot, faces exactly this sliding-block reachability question.
  • Model checking: verifying that software or hardware can never reach a bad state is a giant reachability search over configurations — the heart of PSPACE.
  • Logistics and routing: moving containers, train cars or aircraft on the ground often reduces to "clear the blockers, in the right order."
  • Teaching complexity: because the rules fit on a card, Rush Hour is one of the clearest ways to feel why sequential planning can be harder than a single yes/no puzzle.

Learn why Rush Hour is hard and you've met reachability in a configuration space — the engine under motion planning, automated verification, and countless logistics problems, and a relative of the puzzles around P vs NP.

Conclusion

Rush Hour hides a beautiful secret: the same little cars that you nudge one square at a time can be wired into logic gadgets, and through them into any computation that fits in polynomial memory. Making one move stays trivial; deciding whether the red car can ever escape is PSPACE-complete — as hard as anything in that vast class.

So the next time a board has you gridlocked, take comfort. You are not bad at puzzles. You have run straight into PSPACE-completeness, a hardness deeply tangled with P vs NP, and there may simply be no shortcut to planning your way out.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rush-hour/Content licensed under CC BY-NC 4.0.