Galaxies

Galaxies (also called Tentai Show or Spiral Galaxies) is a grid puzzle. You draw walls along the grid lines to cut it into galaxies. Each galaxy holds exactly one dot and looks the same when turned halfway around that dot.

It runs on the pencil-puzzle kit (ADR 0023), which handles everything around the board (how a puzzle plugs in). Unlike the kit’s other puzzles, the dots are the only clues, so nothing is removed from an answer to make the puzzle, and the player draws walls between cells instead of marking cells.

At a glance#

The rules in code#

Dots in half-cells#

A puzzle is { n, dots }. Each dot is [y, x] in half-cell units, where the cell at row r, column c has its center at (2r + 1, 2c + 1). Both coordinates odd puts a dot in a cell’s middle, one odd on the side between two cells, both even on a corner. The cells a dot touches (one, two or four) are its core. Dots are listed in reading order, and a dot is known by its place in that list. Turning a cell around a dot is whole-number arithmetic:

/** Cell i turned half way round dot [y, x], or -1 if that's off the grid. */
export function mirrorOf(n, i, [y, x]) {
  const r = y - 1 - Math.floor(i / n), c = x - 1 - (i % n);
  return r >= 0 && c >= 0 && r < n && c < n ? r * n + c : -1;
}

An answer is each cell’s dot, row by row: [0, 0, 1, 2, …].

The rules, as check() holds them#

/**
 * Whether `answer` (each cell's dot, row by row) solves the puzzle: every
 * dot's own cells are its, each galaxy is joined up side to side, and turned
 * half way round its dot it lands on itself. Any answer that does counts.
 */
export function check(puzzle, answer) {
  if (!wellFormed(puzzle)) return false;
  const own = ownersOf(puzzle, answer);
  if (!own) return false;
  const sh = shape(puzzle);
  if (sh.cores.some((core, d) => core.some(i => own[i] !== d))) return false;
  for (let i = 0; i < sh.cells; i++) {
    const j = sh.mirror[i * sh.D + own[i]];
    if (j < 0 || own[j] !== own[i]) return false;
  }
  // Joined up: from its dot, a galaxy reaches all its cells.
  const seen = new Uint8Array(sh.cells);
  let reached = 0;
  for (let d = 0; d < sh.D; d++) {
    const todo = sh.cores[d].slice();
    for (const i of todo) seen[i] = 1;
    for (let k = 0; k < todo.length; k++) for (const j of sh.sides[todo[k]]) if (!seen[j] && own[j] === d) { seen[j] = 1; todo.push(j); }
    reached += todo.length;
  }
  return reached === sh.cells;
}

A grid passes when every dot owns its core, every cell’s mirror around its dot is on the grid and has the same dot, and each galaxy is joined side to side from its core. Symmetry and joined-up are separate checks: a symmetric pair cut off from the core fails the second. One-cell galaxies, holes and spirals are all allowed. wellFormed() refuses overlapping cores, a dot on the frame, dots out of order, or no dots.

What the board keeps#

The board keeps no answer, only the player’s marks: walls (as edge ids, 2 × cell for a cell’s right side, +1 for its lower side), crosses (sides marked as not walls), and paint (each cell’s color, a note that affects nothing). It saves as { w: [...], x: [...], c: [...] }, with c only once a cell is painted. A move lists [id, from, to] changes under the same three keys. The walls cut the grid into regions (regionsOf()), and standing() reports each region’s dots, whether it’s a finished galaxy, and what’s wrong. When every region is a galaxy, standing() has the answer.

Making a puzzle#

From a code#

The seed string is galaxies|<ENGINE_VERSION>|<size>|<difficulty>|<code> (the engine pieces), so a code always makes the same puzzle. generate(code, size) refuses any difficulty but the size’s own.

/**
 * The puzzle for a code:
 *   { engine, slug, code, size, difficulty, n, dots: [[y, x], …] }.
 * Throws if the code or size isn't one the game makes, or the difficulty
 * isn't the size's. `stats`, if given, is told how the making went (for
 * tools/puzzles/): attempts, how each tiling tried rated, and how many the
 * plain search refused (`ambiguous`, none so far).
 */
export function generate(code, size, difficulty = SIZES[size]?.difficulty, stats = {}) {
  size = Number(size);
  if (!Object.hasOwn(SIZES, size) || SIZES[size].difficulty !== difficulty || !CODE_RE.test(code)) throw new Error('Not a puzzle the game makes.');
  const { n } = SIZES[size];
  const tier = TIERS[difficulty];
  const r = stream(`${SLUG}|${ENGINE_VERSION}|${size}|${difficulty}|${code}`);
  Object.assign(stats, { attempts: 0, ambiguous: 0, rated: {} });
  for (let attempt = 0; attempt < ATTEMPTS; attempt++) {
    stats.attempts++;
    const { own, dots } = tile(r, n);
    const crumbs = dots.length - new Set(own.filter((d, i) => own.indexOf(d) !== i)).size;
    if (crumbs > CRUMBS * dots.length) { stats.crumbly = (stats.crumbly || 0) + 1; continue; }
    const puzzle = { engine: ENGINE_VERSION, slug: SLUG, code, size, difficulty, n, dots };
    const sh = shape(puzzle);
    const got = solve(puzzle, 3, { sh });
    const rated = got.solved ? DIFFICULTIES[got.tier - 1] : null;
    stats.rated[rated] = (stats.rated[rated] || 0) + 1;
    if (rated !== difficulty) continue;
    if (deep(got.used, tier) < DEPTH[difficulty]) { stats.shallow = (stats.shallow || 0) + 1; continue; }
    // The kit's contract (docs/puzzles.md): kept only if a plain search,
    // sharing no code with the solver, finds this answer and no other, so a
    // solver step that wasn't sound can't ship a puzzle with two answers.
    if (!unique(puzzle, got.answer)) { stats.ambiguous++; continue; }
    stats.steps = got.steps;
    stats.used = got.used;
    stats.dots = dots.length;
    return puzzle;
  }
  throw new Error(`No ${n}×${n} puzzle came of ${code}.`);
}

Each attempt tiles the grid, drops a crumbly tiling, and asks the solver to rate the rest, up to ATTEMPTS = 400 times.

1. Tile the grid#

// A tiling of the n × n grid: { own (each cell's galaxy), dots ([y, x] each) }.
function tile(r, n) {
  const N = n * n, sides = sidesOf(n);
  const own = new Int16Array(N).fill(-1);
  const dots = [];
  const free = i => i >= 0 && own[i] < 0;
  const freeSides = i => sides[i].reduce((k, j) => k + (own[j] < 0 ? 1 : 0), 0);
  // Galaxies run from 1 to about half a grid's side squared... mostly small to middling.
  const most = Math.max(4, Math.round(n * n / 4));
  for (;;) {
    // The tightest free spot first, so few cells are left stranded.
    let tight = 5, spots = [];
    for (let i = 0; i < N; i++) {
      if (own[i] >= 0) continue;
      const k = freeSides(i);
      if (k < tight) { tight = k; spots = [i]; } else if (k === tight) spots.push(i);
    }
    if (!spots.length) break;
    const i = r.pick(spots), y = 2 * Math.floor(i / n) + 1, x = 2 * (i % n) + 1;
    // Where the dot goes: anywhere within REACH cells whose own cells are
    // free and that turns this cell onto a free one, so the tight spot can
    // be the tip of a galaxy whose dot lies further in. It's joined to its
    // dot by a path of free cells whose mirrors are free too.
    let dot = [y, x], path = [i];
    const places = [];
    for (let dy = -2 * REACH; dy <= 2 * REACH; dy++) for (let dx = -2 * REACH; dx <= 2 * REACH; dx++) {
      const p = [y + dy, x + dx];
      if (p[0] < 1 || p[1] < 1 || p[0] > 2 * n - 1 || p[1] > 2 * n - 1) continue;
      if ((dy || dx) && free(mirrorOf(n, i, p)) && coreOf(n, p).every(free)) places.push(p);
    }
    // A dot in the spot's own middle (a lone cell, unless it grows) last.
    r.shuffle(places).push(dot);
    for (const p of places) {
      const found = route(n, sides, own, p, i);
      if (found) { dot = p; path = found; break; }
    }
    const d = dots.length;
    dots.push(dot);
    const cells = [];
    const add = j => { if (own[j] < 0) { own[j] = d; cells.push(j); } };
    for (const j of [...coreOf(n, dot), ...path]) { add(j); add(mirrorOf(n, j, dot)); }
    // Grow, a cell and its mirror at a time, to a size drawn at random
    // (squared, so small and middling galaxies outnumber big ones).
    const want = 2 + Math.floor(r.next() * (0.4 + 0.6 * r.next()) * most);
    while (cells.length < want) {
      const edge = [];
      for (const a of cells) for (const j of sides[a]) {
        if (own[j] >= 0) continue;
        const m = mirrorOf(n, j, dot);
        if (m >= 0 && (own[m] < 0) && !edge.includes(j)) edge.push(j);
      }
      if (!edge.length) break;
      const j = r.pick(edge);
      add(j);
      add(mirrorOf(n, j, dot));
    }
  }
  // Dots in reading order, the galaxies renumbered to match.
  const order = dots.map((p, d) => [p, d]).sort((a, b) => a[0][0] - b[0][0] || a[0][1] - b[0][1]);
  const renum = new Int16Array(dots.length);
  order.forEach(([, d], k) => { renum[d] = k; });
  return { own: Array.from(own, d => renum[d]), dots: order.map(([p]) => p) };
}

Until no cell is free:

1. Find the tightest spot: a random free cell among those with the fewest free neighbors. Starting where cells would be stranded keeps one-cell crumbs rare.
2. Place a dot near it, within REACH = 3 cells, with its core free and the spot’s mirror free. Candidates are shuffled, the spot’s own middle last. The first whose core route() (a breadth-first search) can join to the spot through free cells with free mirrors wins. So the spot can be the tip of a galaxy whose dot lies further in.
3. Claim the core, the path and every mirror.
4. Grow toward want = 2 + ⌊u₁ · (0.4 + 0.6 · u₂) · most⌋ cells (u₁, u₂ random from 0 to 1, most a quarter of the grid, at least 4), so most galaxies are small or middling and a few reach twenty cells. Each step adds a free neighbor whose mirror is free, and the mirror.

The dots are then sorted into reading order. The tiling is valid by construction.

2. Keep it only if it’s good#

• Not crumbly. At most CRUMBS = 20% of galaxies may be single cells.
• Rated as asked. The solver must decide every cell and need exactly the size’s tier.
• Deep enough. It must use at least DEPTH steps of that tier:

// How many steps of its own tier a puzzle must need, so a medium isn't an
// easy one with a single medium step.
const DEPTH = { easy: 0, medium: 3, hard: 2 };

With nothing to remove, a tiling either is a puzzle at its tier or isn’t. That’s why Galaxies tries far more tilings than Yin-Yang or Fillomino lay answers.

Uniqueness#

Every solver step is sound, so a grid the solver decides has exactly one answer. The solver’s answer must also pass check().

games/static/games/galaxies/engine/count.js, a search sharing no code with the solver, proves it a second way. As the kit’s contract asks (The engine pieces), generate keeps a puzzle only if the search finds exactly the solver’s answer within its budget, else counts it in stats.ambiguous and moves on:

// Whether the plain search (count.js) finds exactly one answer, the one given
// (in its written form), within its budget.
export function unique(puzzle, answer) {
  const found = count(puzzle, 2);
  return found.count === 1 && !found.gaveUp && JSON.stringify(found.answers[0]) === JSON.stringify(answer);
}

An unsound solver step then costs a candidate instead of shipping a two-answer puzzle, whose referee would refuse a correct but different solve. The gate has never refused one in 1,500 codes a size, so ENGINE_VERSION stayed 1. It adds at most a seventh to the making time.

The solver’s ladder#

games/static/games/galaxies/engine/solver.js keeps, for every cell, the dots it could still belong to (cand). A cell can’t be dot d’s unless its mirror around d can be too, so drop() and give() always carry the mirror.

// Cell i is dot d's (and so is its mirror). True if anything changed.
function give(sh, s, i, d) {
  if (s.own[i] === d) return false;
  if (s.own[i] >= 0 || !s.cand[i * sh.D + d]) throw new Contradiction();
  s.own[i] = d;
  for (let e = 0; e < sh.D; e++) if (e !== d) drop(sh, s, i, e);
  const j = sh.mirror[i * sh.D + d];
  if (j < 0) throw new Contradiction();
  give(sh, s, j, d);
  return true;
}

// Suppose cell i were dot d's: if techniques up to `upto` then reach a
// contradiction, it isn't.
function suppose(sh, s, upto, technique) {
  for (let i = 0; i < sh.cells; i++) {
    if (s.own[i] >= 0) continue;
    for (let d = 0; d < sh.D; d++) {
      // Only a galaxy the cell is beside: "if this one grew into it…".
      if (!s.cand[i * sh.D + d] || !sh.sides[i].some(j => s.own[j] === d)) continue;
      const t = copy(s);
      try {
        give(sh, t, i, d);
        while (!done(t) && step(sh, t, upto));
      } catch (e) {
        if (!(e instanceof Contradiction)) throw e;
        drop(sh, s, i, d);
        return note(s, technique, true);
      }
    }
  }
  return false;
}

Look ahead is one step’s immediate effect, never a chain of guesses. check:puzzles fails any puzzle that needs trial.

What separates the sizes#

Measured for this chapter: 300 codes a size on a desktop (Node 24), before generate ran the search (Uniqueness). All 900 had exactly one answer by count().

Mean uses of each technique per puzzle:

How every tiling tried fared:

A 10×10 tiling is hard about one time in thirty, a 13×13 about one in eight, which is why the sizes are 7, 10 and 13.

The daily#

KIND = Kind(
    slug="galaxies",
    title="Galaxies",
    engine_file="games/static/games/galaxies/engine/generate.js",
    sizes={"7": "7×7", "10": "10×10", "13": "13×13"},
    # The bigger the grid, the deeper the reasoning: a size is a difficulty.
    size_difficulty={"7": "easy", "10": "medium", "13": "hard"},
    daily=(("7", "easy"), ("10", "medium"), ("13", "hard")),
    # Roughly the time it takes just to paint the galaxies with the answer in
    # front of you, a dragged stroke each: about 12, 20 and 29 of them.
    min_seconds={"7": 10, "10": 20, "13": 35},
    clean=clean,
    wrong="Those galaxies don’t solve this puzzle.",
    since=date(2026, 10, 13),
    # 10×10 was a bit much for a daily: from the 23rd it's 7×7 (David,
    # 2026-10-22; docs/adr/0037). Today's 10×10 stays today's.
    moved=((date(2026, 10, 23), ("7", "easy")),),
)

A day’s code is an HMAC of galaxies|<date>|<size>|<difficulty>, a hash only the server can make because it uses a secret key (the kit’s dailies). The one daily was the 10×10 from 2026-10-20, and the 7×7 from 2026-10-23, after David found the 10×10 too hard (moved, ADR 0037). A move starts at midnight and never changes a day already posted, and each size keeps its codes. From 2026-10-26 the weekday picks the size (ADR 0041, the week climbs): 7×7 Monday and Tuesday, 10×10 Wednesday to Saturday, 13×13 Sunday.

Your move#

firstMove gives the kit’s first-move prompt (Your first move) its words: Draw your first wall (“Tap near a line between two cells, or drag along the lines”).

Secrets#

None in play. The engine runs in the browser, and solution() is a console call away. The server keeps tomorrow’s code and each puzzle’s answer to itself (What a cheater could and couldn’t do). The tints on finished galaxies come from the dots alone (below), so they leak nothing.

Posting and the referee#

A solve posts { code, size, difficulty, engine, answer, seconds } to the kit’s view (the kit’s referee). clean() checks shape only, n × n whole numbers each under n², and leaves the dot count to the referee.

def clean(answer, size):
    """An answer is each cell's dot (its place in the puzzle's list of dots),
    row by row: [0, 0, 1, 2, …], n × n whole numbers. Whether there are that
    many dots is the referee's to say."""
    n = GRIDS[size]
    if not isinstance(answer, list) or len(answer) != n * n:
        raise ValueError("not a dot for every cell")
    if not all(type(v) is int and 0 <= v < n * n for v in answer):
        raise ValueError("not a dot for every cell")
    return answer

Then come the size’s minimum time and the answer, checked against the one the referee kept.

Each minimum is roughly the time to paint the answer with one dragged stroke per galaxy (about 12, 20 and 29 strokes).

Rating#

Rated by Kit("galaxies") (timed puzzles), with par set by size. Endless and archive solves are rated against par when posted, at weight 0.5. The day’s daily is rated as a field at midnight.

Worked: an endless 13×13. A settled 1550 ± 80 player in 13:40, par 16:00: the time scores 0.578 and moves them +0.4. Yesterday’s 7×7 daily from the archive in 2:30, par 3:00: +0.5.

Worked: today’s 7×7, four solvers, each meeting the others at 0.50 of a game:

guide/worked/galaxies.py computes these through ratings.sources.Kit and ratings.service.compute. The fastest 7×7 the referee believes, 10 seconds, would score 0.9969 against a 3:00 par.

Leaderboards and the account#

The kit’s: Daily, All-time by size and Ratings, at /games/galaxies/leaderboard/ (puzzles/views.py), plus best times on the account page.

The interface#

Drawing walls#

games/static/games/galaxies/js/board.js meets the kit’s board contract on gridSurface, and is the one board that draws along the lines between cells, using the surface’s trace(x, y) (the board’s surface). An early version painted and locked galaxies cell by cell; walls alone proved clearer, so an older save keeps its walls and drops the rest.

The sides between two dots’ own cells are walls from the start (givenWalls()), since two dots can’t share a galaxy, and can’t be rubbed out.

The paint tool#

Paint lets a player note which galaxy a cell belongs to. The board hands the kit a tools element for the tray under the board: Lines | Paint, the house kit’s segmented control (seg(), the front end). Every puzzle opens on Lines. The eight colors and a rubber show only in Paint mode, keeping their space when hidden (visibility and inert) so nothing shifts.

/**
 * The paint box: eight colors a player marks cells with, to say which
 * galaxy a cell belongs to. The Okabe-Ito colors, which most color-blind
 * eyes tell apart, with a gray for the eighth (galaxies.css, --gx-paint-1…8).
 */
export const PAINTS = ['orange', 'sky blue', 'green', 'yellow', 'blue', 'red', 'pink', 'gray'];

A tap paints a cell, or clears it if it already has the color. A drag paints every cell crossed, one Undo per stroke, using the surface’s over(j); a drag that starts on the picked color rubs it out. Press and hold or right-click clears.

// A drag across cells, painting: each cell takes the color, or, begun on
// a cell of the color picked (or with the rubber), that color comes off.
function paintStroke(from) {
  const ch = gather();
  const v = color && paint[from] !== color ? color : 0;
  const only = color && !v ? color : null;
  return {
    over(j) {
      if (only && paint[j] !== only) return;
      setPaint(ch, j, v);
      draw();
    },
    end() {
      const k = commit(ch);
      if (k) ctx.say(undefined, `${v ? `Painted ${k} ${k === 1 ? 'cell' : 'cells'} ${paintName(v)}` : `Cleared ${k} ${k === 1 ? 'cell' : 'cells'}`}. ${status()}`);
    },
    cancel() {
      for (const [i, from_] of ch.c.values()) paint[i] = from_;
      draw();
    },
  };
}

The colors are the Okabe-Ito set (which most color-blind eyes can tell apart) plus a gray, at 58% strength (--gx-paint-strength) so walls and dots stay clear. The answer, helpers and solve read only the walls, so paint can’t help or hinder. Restart clears paint with the walls, and solving fades it.

Helpers (assists)#

Each has its own switch, all on by default. All three read the walls, never the answer.

A one-dot region can only be that galaxy whole, so a lopsided one is always a mistake. A region with several dots is usually work in progress, which is why the crowded flag waits for the last region.

tintsOf() gives each dot, in order, the least-used of the kit’s seven tints that no earlier dot within three and a half cells has. It uses the dots alone, so neighbors can rarely share a tint.

Mirror walls (drawing a wall’s twin automatically) were left out on purpose. Mid-puzzle a wall could belong to any dot beside it, so a guess would draw walls the player didn’t mean.

Solved, sharing and saving#

When the walls cut the grid into galaxies and check() passes, the kit takes over (the kit’s step 7). The frame turns green, galaxies wash in outward from the last wall, and the dots light gold. A stray wall that doesn’t split a galaxy doesn’t block the solve. Share result reads “Galaxies · Daily 7×7 · Friday, October 23 / Solved in 2:42” plus the address. Saves live under uo:galaxies:p:<size>/<difficulty>/<code>.

Accessibility#

The grid is one tab stop. A cell reads as “Row 3, column 4.”, and each wall drawn names its side. The status line names the broken rule, else how many galaxies are closed. Flags use shapes as well as colors.

Its look#

Galaxies’ personality, in the design system’s personality sheet. Everything else is the puzzle book’s (Puzzles).

Testing#

Known issues and open questions#

Found while writing this chapter; those fixed since are gone.

1. Most 10×10 tilings are wasted. Of 3,693 tilings tried for 300 puzzles, 1,427 rated easy and 588 medium ones were too shallow. Generation is still fast (73 ms at worst), but a tiling that leaned harder would waste less.
2. Open questions: 12×12 or 15×15 sizes; crosses on by default; whether paint should remember the last tool, or offer fewer colors on a 7×7; whether the given walls between touching dots help too much; the crowded flag’s timing; hard’s depth; the minimum times.

Changing it#

Then npm run check:guide, and npm run guide:stamp galaxies.