Level Design

Rooms are small; exhaustive BFS is cheap. CI audits every room on push: solvable, optimal depth, which mechanics the solution needs, forcedness. The level atlas animates those certificates.

Caught cheese. Clustered near-duplicates.

Why BFS is enough

Rush Hour (generalized n×n) is PSPACE-complete (Flake & Baum 2002; later results push hardness down to 1×1 cars + walls). Solutions can be exponentially long in the worst case. At play scale, Fogleman (2018) enumerated ~1.5M interesting 6×6 configs in ~3 hours of C++; hardest standard position: 51 moves.

EndWise rooms: typical ~100 unique states (median ~150), worst ~90,000, branching ~5. Full 69-level audit (baseline + four mechanic-off passes) ~5 minutes in CI. Plain BFS; every claim is a proof.

Move model

State = full placement of every piece + per-piece status (tipped/flat, pinned/free). The solver derives the player reachable region; it does not store it.

Heavy — endwise only; end-stance aware (where you can stand to push/pull). Pull required in much of the campaign.

Free — casters/dolly; four directions.

Pivot — pin on a corner lattice vertex; piece steps fully around it; sampled sweep includes the player on the swing.

Tip — 2×3 mattress → door-tall 1×3, one lane past the tip edge.

Pin, unpin, swing, tip, untip = one move each. Exit through a matching one-wide door. Solved when the door-in cell is reachable for everything that must leave.

Four panels showing heavy, free, pivot, and tip furniture movement classes on a grid — **Four verbs, one occupancy grid.** Heavy slides endwise from end stances; free slides any direction; pivot pins a lattice vertex and steps fully around it; tip lands a door-tall slab one lane past the edge.

State key

(pieces, pins, tipped, region_canon). Piece: (letter, sorted footprint cells, axis, move class, kind). Python hash set — no Zobrist, no bitboards. Player cell omitted from the key: same walkable region ⇒ same node. Flood fill each expansion; store lex-least cell of the region.

Pivot sweep: 45 samples / 90° (~2°), footprint + ride-along capsule vs grid. Worst-room memory: low hundreds of MB.

Depth and mechanic columns

Optimal depths: 1–22 (finale 22). Four extra runs per level: push-only, no-pivot, no-tip, all-heavy.

Solver audit table row for cart-and-couch with push-only, no-pivot, no-tip, and all-heavy columns annotated — **Each column turns a mechanic off.** Unsolvable without pulling means the level teaches pull; same depth without tip means tip was never required.

no-pivot solvable at same depth → couch corner unused. push-only unsolvable → level teaches pull. Pull strictly required in 32 of 69.

Cheese: “don’t corner yourself” solved in one unanticipated pull.

Forcedness

How much of the optimal path admits alternatives vs forced march. Hand tier labels correlate poorly with depth. Pacing uses depth + mechanic columns + forcedness.

Duplicates

Cluster by solver signature (depth + required mechanics + solution structure) → near-duplicate groups, same puzzle in different furniture. Knock-over can always restore a dead state — verified by the audit.

Refs: Flake & Baum, TCS 270 (2002) · Hearn & Demaine, TCS 343 (2005) · Brunner et al., FUN 2021 · Fogleman 2018 · Gardner, Sixth Book of Mathematical Diversions.