basin / commit
Guarantee puzzle solutions are unambiguous
src/model/puzzle.test.ts | 31 ++++++++++ src/model/puzzle.ts | 156 +++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 160 insertions(+), 27 deletions(-) diff --git a/src/model/puzzle.test.ts b/src/model/puzzle.test.ts index 745ecbc..fbffa72 100644 --- a/src/model/puzzle.test.ts +++ b/src/model/puzzle.test.ts @@ -76,6 +76,37 @@ describe('generatePuzzle', () => { expect(p.targetOutflow.length).toBeGreaterThan(0); } }); + + it('yields an unambiguous solution: no other spring set reproduces the target', () => { + // Brute-force every size-`springCount` set of interior cells and confirm the + // generator's solution is the *only* one whose outflow matches the target — + // i.e. the gold-edge hint pins down a single answer. + const size = 9; + const springCount = 2; + for (const seed of [1, 7, 55, 1000, 999999, 271828]) { + const p = generatePuzzle(cfg({ size, springCount, edges: ALL_OCEAN, terrainSeed: seed })); + const target = new Set(p.targetOutflow.map((c) => `${c.x},${c.y}`)); + + const interior: Array<{ x: number; y: number }> = []; + for (let y = 1; y < size - 1; y++) { + for (let x = 1; x < size - 1; x++) interior.push({ x, y }); + } + + const matches: Array<Set<string>> = []; + for (let a = 0; a < interior.length; a++) { + for (let b = a + 1; b < interior.length; b++) { + const set = [interior[a], interior[b]]; + const out = simulateFlows(p.hm, set).outflow.map((c) => `${c.x},${c.y}`); + if (out.length === target.size && out.every((k) => target.has(k))) { + matches.push(new Set(set.map((c) => `${c.x},${c.y}`))); + } + } + } + + expect(matches).toHaveLength(1); + expect(matches[0]).toEqual(new Set(p.solution.map((c) => `${c.x},${c.y}`))); + } + }); }); describe('isSolutionSpring', () => { diff --git a/src/model/puzzle.ts b/src/model/puzzle.ts index 9b8a49d..c928e4e 100644 --- a/src/model/puzzle.ts +++ b/src/model/puzzle.ts @@ -50,8 +50,12 @@ export interface Puzzle { * placement, so a board is fully reproducible from its config (hence its code). * * Springs are drawn from interior land cells, kept a minimum gap apart so their - * watersheds stay distinct, and re-rolled until they yield a reasonably rich - * edge signature — a larger target is less ambiguous to hunt for. + * watersheds stay distinct, and re-rolled until they yield a signature that is + * both reasonably rich (a wider target is easier to read) and, above all, + * *unambiguous*: the chosen set must be the only set of that size reproducing it, + * so the gold-edge hint actually pins down a single answer (see + * {@link isUniqueSolution}). Boards that can't be made unique fall back to the + * richest set found, so generation never fails. */ export function generatePuzzle(config: Config): Puzzle { const norm = normalizeConfig(config); @@ -68,31 +72,62 @@ export function generatePuzzle(config: Config): Puzzle { } } + // A candidate's outflow footprint is fixed by the terrain, so precompute each + // one once as a bitmask over border-cell indices. Because wet sets (and hence + // outflow) union across springs, a spring set's target signature is simply the + // OR of its members' masks — which is what makes the uniqueness check cheap. + const sig = candidates.map((c) => outflowMask(simulateFlows(hm, [c]).outflow, size)); + const wanted = Math.max(3, springCount); // prefer a signature at least this wide - let best: { solution: Cell[]; outflow: Cell[] } | null = null; + let bestUnique: Candidate | null = null; + let bestAny: Candidate | null = null; for (let attempt = 0; attempt < 128; attempt++) { // Relax the spacing requirement if the board is too cramped to satisfy it. const minGap = attempt < 96 ? 3 : attempt < 112 ? 2 : 1; - const picked = pickSprings(candidates, springCount, rng, minGap); - if (picked.length < springCount) continue; + const idx = pickSpringIdx(candidates, springCount, rng, minGap); + if (idx.length < springCount) continue; + + let target = 0n; + for (const i of idx) target |= sig[i]; + if (target === 0n) continue; // must reach an ocean edge - const flow = simulateFlows(hm, picked); - if (flow.outflow.length === 0) continue; // must reach an ocean edge + const richness = popcount(target); + const pick: Candidate = { solution: idx.map((i) => candidates[i]), richness }; + if (!bestAny || richness > bestAny.richness) bestAny = pick; - if (!best || flow.outflow.length > best.outflow.length) { - best = { solution: picked, outflow: flow.outflow }; + // Only accept a pick whose signature no *other* size-k spring set reproduces. + if (isUniqueSolution(sig, target, springCount)) { + if (!bestUnique || richness > bestUnique.richness) bestUnique = pick; + if (richness >= wanted) break; // unique *and* rich enough — good to go } - if (flow.outflow.length >= wanted) break; // rich enough — good to go } - // `best` is set once any attempt yields springs; normalizeConfig guarantees the - // board has at least `springCount` interior candidates, so that always happens. - const solution = best!.solution; - const targetOutflow = best!.outflow; + // Prefer an unambiguous board; fall back to the richest set otherwise. `bestAny` + // is always set: normalizeConfig guarantees at least `springCount` interior + // candidates, and every interior cell drains to an ocean edge, so some attempt + // always yields a non-empty signature. + const chosen = bestUnique ?? bestAny!; + const targetOutflow = simulateFlows(hm, chosen.solution).outflow; const target = borderSignature(targetOutflow, size, size); - return { config: norm, hm, width: size, height: size, edges, solution, target, targetOutflow }; + return { + config: norm, + hm, + width: size, + height: size, + edges, + solution: chosen.solution, + target, + targetOutflow, + }; +} + +/** A spring set under consideration during generation, with its signature width. */ +interface Candidate { + solution: Cell[]; + /** Number of border cells the set wets — how rich (readable) its signature is. */ + richness: number; } /** Is `cell` one of the puzzle's hidden spring positions? */ @@ -197,29 +232,96 @@ function rollEdges(rng: Rng): Edges { } /** - * Sample `k` distinct candidates that are pairwise at least `minGap` apart - * (Chebyshev distance). Returns fewer than `k` only if the spacing can't be met. + * Sample the indices of `k` distinct candidates that are pairwise at least + * `minGap` apart (Chebyshev distance). Returns fewer than `k` only if the spacing + * can't be met. Indices (not cells) so callers can look up precomputed per-cell + * data — notably each candidate's outflow signature. */ -function pickSprings(candidates: Cell[], k: number, rng: Rng, minGap: number): Cell[] { - const pool = candidates.slice(); - for (let i = pool.length - 1; i > 0; i--) { +function pickSpringIdx(candidates: Cell[], k: number, rng: Rng, minGap: number): number[] { + const order = candidates.map((_, i) => i); + for (let i = order.length - 1; i > 0; i--) { const j = Math.floor(rng() * (i + 1)); - [pool[i], pool[j]] = [pool[j], pool[i]]; + [order[i], order[j]] = [order[j], order[i]]; } - const chosen: Cell[] = []; - for (const c of pool) { - const spaced = chosen.every( - (o) => Math.max(Math.abs(o.x - c.x), Math.abs(o.y - c.y)) >= minGap, - ); + const chosen: number[] = []; + for (const i of order) { + const c = candidates[i]; + const spaced = chosen.every((o) => { + const p = candidates[o]; + return Math.max(Math.abs(p.x - c.x), Math.abs(p.y - c.y)) >= minGap; + }); if (spaced) { - chosen.push(c); + chosen.push(i); if (chosen.length === k) break; } } return chosen; } +// --------------------------------------------------------------------------- +// Uniqueness: is the chosen spring set the only one reproducing its signature? +// --------------------------------------------------------------------------- + +/** + * A signature is *unambiguous* iff exactly one size-`k` set of candidates + * reproduces it. Any candidate whose footprint isn't wholly inside the target + * can't belong to such a set (it would wet a non-target edge), so only those need + * be considered — usually a small pool. We then count size-`k` exact covers of + * the target, stopping at the first duplicate; the chosen set is always one of + * them, so "unique" means the count is exactly 1. + */ +function isUniqueSolution(sig: bigint[], target: bigint, k: number): boolean { + const compat: bigint[] = []; + for (const s of sig) if (s !== 0n && (s | target) === target) compat.push(s); + return countCovers(compat, target, k, 2) === 1; +} + +/** + * Count size-`k` subsets of `masks` whose bitwise-OR equals `target`, stopping + * once `cap` is reached. A bounded node budget guards against pathological pools; + * exhausting it reports `cap` (treat as ambiguous) rather than falsely claiming + * uniqueness. + */ +function countCovers(masks: bigint[], target: bigint, k: number, cap: number): number { + let count = 0; + let budget = 200_000; + const n = masks.length; + + const dfs = (start: number, chosen: number, acc: bigint): void => { + if (chosen === k) { + if (acc === target) count++; + return; + } + if (n - start < k - chosen) return; // too few candidates left to reach k + for (let i = start; i < n; i++) { + if (--budget < 0) { + count = cap; // give up — conservatively treat as ambiguous + return; + } + dfs(i + 1, chosen + 1, acc | masks[i]); + if (count >= cap) return; + } + }; + + dfs(0, 0, 0n); + return count; +} + +/** Bitmask of a flow's wet border cells, one bit per row-major cell index. */ +function outflowMask(outflow: Cell[], width: number): bigint { + let m = 0n; + for (const c of outflow) m |= 1n << BigInt(c.y * width + c.x); + return m; +} + +/** Number of set bits in `m` (the width of a signature, in border cells). */ +function popcount(m: bigint): number { + let n = 0; + for (let v = m; v > 0n; v >>= 1n) n += Number(v & 1n); + return n; +} + /** Mark the wet border cells of a flow as a row-major signature mask. */ function borderSignature(outflow: Cell[], width: number, height: number): Uint8Array { const sig = new Uint8Array(width * height);