Chicago Traffic

Chicago Traffic is the classic sliding-car puzzle (Rush Hour), under David’s name for it. Cars and trucks are parked tight in a 6×6 tray, and each slides only along its own lane. Get the red car out through the gap on the right in as few moves as you can.

The box had forty cards; here a code makes a puzzle, at the box’s four levels, so the supply never runs out. It’s one of the site’s brainteasers (ADR 0042): it runs on the pencil-puzzle kit in the toy-box look, is scored on moves first and then time, and is endless, with no daily (ADR 0043). See The pencil-puzzle kit and Brainteasers for what the kit does. docs/chicago-traffic.md has the full design notes and measurements.

At a glance#

Decisions: ADR 0042 (brainteasers), ADR 0043 (endless, no daily), ADR 0023 (the kit), ADR 0030 (ratings).

The rules in code#

The red car, X, lies across the third row, with the exit at that row’s right end. Cars are two cells long and trucks three. The box’s set is the most a puzzle has: eleven cars, A to K, and four trucks, O to R (ABCDEFGHIJK and OPQR). A move is one vehicle sliding any distance one way. The puzzle is solved when the red car reaches the last two columns.

An answer is a list of slides, [vehicle, distance]. A run of slides by one vehicle counts as one move:

/**
 * How many moves an answer takes, as a player is scored: each run of slides
 * by one vehicle is one move (a drag recorded as several slides is still
 * one). Null if it isn't a list. It counts; check() says whether it's legal.
 */
export function movesOf(answer) {
  if (!Array.isArray(answer)) return null;
  let moves = 0, last;
  for (const move of answer) {
    const id = Array.isArray(move) ? move[0] : undefined;
    if (moves === 0 || id !== last) moves++;
    last = id;
  }
  return moves;
}

/**
 * Whether an answer gets the red car out: a list of legal slides, [id,
 * delta], from the puzzle's start, the last of them the one that reaches
 * the exit. Refuses anything else, whatever its shape: an id the puzzle
 * hasn't got, a slide of nothing, through another vehicle or off the lot,
 * slides after the red car is out, an answer that stops short, or one
 * longer than MOST_SLIDES.
 */
export function check(puzzle, answer) {
  const got = boardAt(puzzle);
  if (!got || !Array.isArray(answer) || answer.length < 1 || answer.length > MOST_SLIDES) return false;
  const { b } = got;
  const index = new Map(got.at.map((v, i) => [v.id, i]));
  const at = Int8Array.from(b.at), grid = new Int8Array(N * N);
  for (let s = 0; s < answer.length; s++) {
    const move = answer[s];
    if (!Array.isArray(move) || move.length !== 2) return false;
    const [id, delta] = move;
    if (typeof id !== 'string' || !index.has(id) || !Number.isInteger(delta) || delta === 0) return false;
    // (a solved board takes no more slides: the red car has gone)
    if (at[0] === OUT) return false;
    const i = index.get(id);
    const [min, max] = reach(b, at, fill(b, at, grid), i);
    if (delta < min || delta > max) return false;
    at[i] += delta;
  }
  return at[0] === OUT;
}

Making a puzzle#

The four levels are the box’s, each a range of fewest moves:

A code picks a target distance evenly from its level’s range, then finds a board that reaches that far. Because sliding is reversible, a board’s vehicles can reach a whole cluster of positions. One breadth-first search back from all of the cluster’s solved positions gives every position’s distance from the exit. A puzzle is any position exactly the target distance out, with every vehicle removed that doesn’t change the count:

/**
 * The puzzle for a code:
 *   { engine, slug, code, size, difficulty, n: 6, exit: 2, vehicles, best },
 * vehicles[0] the red car X; best the fewest moves out. Throws if the code
 * or tier isn't one the game makes. `stats`, if given, is told how the
 * making went (for tools/puzzles/): boards surveyed, whether it came from a
 * seed, and how many changes the seed kept.
 */
export function generate(code, size, difficulty = SIZES[size]?.difficulty, stats = {}) {
  if (!Object.hasOwn(SIZES, size) || SIZES[size].difficulty !== difficulty || !CODE_RE.test(code)) throw new Error('Not a puzzle the game makes.');
  const [lo, hi] = SIZES[size].best;
  const r = stream(`${SLUG}|${ENGINE_VERSION}|${size}|${code}`);
  const want = lo + r.int(hi - lo + 1);
  Object.assign(stats, { want, attempts: 0, seeded: false, shakes: 0 });
  let board = null;
  for (let attempt = 0; attempt < FRESH && !board; attempt++) {
    stats.attempts++;
    const vehicles = fresh(r);
    if (survey(vehicles) >= want) board = vehicles;
  }
  if (!board) {
    stats.seeded = true;
    const pool = SEEDS.filter(line => Number(line.split(' ')[0]) >= want);
    if (!pool.length) throw new Error(`No ${difficulty} puzzle came of ${code}.`);
    board = seedBoard(pool[r.int(pool.length)]).vehicles;
    for (let tries = 0; tries < SHAKE_TRIES && stats.shakes < SHAKES; tries++) {
      stats.attempts++;
      const next = change(r, board);
      if (next && survey(next) >= want) { board = next; stats.shakes++; }
    }
  }
  const at = placed(r, board, want);
  if (!at) throw new Error(`No ${difficulty} puzzle came of ${code}.`);
  return { engine: ENGINE_VERSION, slug: SLUG, code, size, difficulty, n: N, exit: EXIT, vehicles: letter(tow(at, want)), best: want };
}

Short distances turn up on random boards in milliseconds. Long ones don’t: about one random board in 500 reaches 20 moves, and one in 7,000 reaches 30. So Advanced and Expert (and some Intermediate) start from a seed, a hard board found ahead of time by long searches (seeds.mjs). The seed is shaken by changes that keep its cluster reaching the distance, so each code makes its own puzzle, a cousin of its seed. Everything comes from the kit’s seeded stream and counted loops, never timers, so a code makes the same puzzle in every browser and in the referee. ENGINE_VERSION is 1; bump it if any code would make a different puzzle, remade seeds included.

The puzzle carries its fewest moves, best, and the game shows it from the start (David’s call): the bar counts toward it (“3 / 14 moves”).

Secrets#

The browser makes the puzzle, so it knows the fewest moves and can find a shortest way out (hint, solution). That’s fine: as for every solo game, the boards are family boards (ADR 0003).

Posting and the referee#

The server checks the answer’s shape:

def clean(answer, size):
    """An answer is the slides, in order: [vehicle, distance] pairs, the
    distance a whole number of cells, + right or down, − left or up.
    [["A", -1], ["X", 3]]"""
    if not isinstance(answer, list) or not 0 < len(answer) <= MOST_MOVES:
        raise ValueError("not a list of slides")
    for move in answer:
        if not (isinstance(move, list) and len(move) == 2 and isinstance(move[0], str) and VEHICLE.fullmatch(move[0])
                and type(move[1]) is int and 0 < abs(move[1]) < 6):
            raise ValueError("not a slide")
    return answer

Then the referee replays every slide on the puzzle the code makes and returns the move count (Referees and anti-cheat). The solve keeps it (Solve.moves), and the boards rank fewest moves, then time. No legal answer can beat best.

Rating#

Like any endless kit puzzle (Ratings): a solve is rated on its time against par, at half weight. With no dailies there are no day fields; moves are ranked on the boards.

The interface#

The tray is its own SVG: a 6×6 block of asphalt in a molded rim, with the gap on the right opening onto a short street under a green “LAKE SHORE DR” sign. paints() gives each vehicle its look by its place in the puzzle (a Checker cab among the cars, a CTA bus among the trucks), so a vehicle keeps its paint.

• Dragging. A vehicle follows the finger along its lane, within the open stretch either side (range), and settles in the nearest cell when let go. A helper, on by default, washes the open stretch while it moves. Vehicles are moved, never redrawn, so slides glide.
• Out through the gap. With a clear path, the red car doesn’t stop at the tray’s edge but slides on into the gap as far as its solved position (David’s call: stopping a cell short felt wrong). Let go past halfway into the last cell, or pushed 0.6 of a cell into the gap (handOff), it’s at the exit. That’s still one slide and one move, so the answer and the referee’s count are unchanged. Every other vehicle, and a blocked red car, stops at the edge.
• Keys. Arrows along the picked vehicle’s lane slide it a cell; arrows across it pick the nearest vehicle that way; Tab picks the next.
• Counting. Each slide is an Undo step, but the count is the answer’s, written as each vehicle’s net slides since the last Restart, so moving a car there and back costs nothing:

// The moves since the last Restart as the answer writes them: slides of
// one vehicle in a row are one move, and one that ends where it began is
// none (so a car taken there and back between two slides of another
// leaves those two as one).
function moves() {
  const out = [];
  for (const m of history) {
    if (m.reset) { out.length = 0; continue; }
    const top = out[out.length - 1];
    if (top && top.v === m.v) {
      top.d += m.to - m.from;
      if (!top.d) out.pop();
    } else out.push({ v: m.v, d: m.to - m.from });
  }
  return out;
}

• Solved. The red car pulls onto the street, a sticker says “Solved · 14 moves”, and the result sheet leads with the count and says when it matched the fewest possible. The drive-off starts from wherever the car is: after a drag it rolls straight on (celebrate, --ct-roll); after a key or a replayed move it pulls away from a standstill in 800ms. Under reduced motion it’s there at once.
• Given up (the dock’s Give up, or the row’s in “Pick up where you left off”), the shortest way out from the current position plays itself a slide at a time (reveal, from the engine’s hint), and a sticker says “Gave up”.
• Your move. firstMove gives the kit’s first-move prompt (Your first move) its words: Clear the red car’s way (“Drag a car or truck along its lane to make room. Every slide counts as a move.”).

Its look#

Chicago Traffic’s personality, in the design system’s personality sheet. Everything else is the toy box’s (Brainteasers), on the pencil-puzzle kit.

Changing it#

• Bump ENGINE_VERSION if a code would make a different puzzle, including after remaking seeds.js (node tools/chicago-traffic/seeds.mjs --climbs=800 --jobs=5).
• npm run check:puzzles re-proves fixed codes’ best with its own search, refuses tampered answers, and re-proves every seed.