Loop(一筆書きの輪)の生成ロジックを読むその2

結論。Loopは「マスの数字・格子点の次数(0本か2本)・すでに確定した輪が閉じていないかの3種類の制約を伝播させ、絞り切れない箇所だけを最大20,000ノードまで探索して解の数を数える」ことで一意解を確認する。数字の間引きは、ランダムな順で1マスずつ数字を消し、消しても一意解が保てる場合だけ確定させる貪欲法であり、消す順序に依存する(=最大限に間引ける保証はない)。探索が打ち切られた問題(truncated: true)や複数解の問題は、生成にも間引きにも使われない。

制約伝播(propagate): 3種類のルールをすべて変化が止まるまで

前編で見た全辺(H・V)は、それぞれ[0](選ばれていない確定)・[1](選ばれている確定)・[0, 1](未確定)のいずれかの候補集合(domain)を持ちます。propagate(domains, n, geo, clues)は、この候補集合を3種類のルールでくり返し絞り込みます。

function propagate(domains, n, geo, clues) {
  domains = domains.map((d) => d.slice());
  let changed = true;
  while (changed) {
    changed = false;
    // 1. マス制約: 4辺のon確定数・未確定数と、クルーの数字を突き合わせる
    for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) {
      const clue = clues[r * n + c];
      if (clue == null) continue;
      const edges = geo.cellEdges(r, c);
      let onCount = 0; const unknown = [];
      for (const e of edges) { if (domains[e].length === 1) { if (domains[e][0] === 1) onCount++; } else unknown.push(e); }
      if (onCount > clue || onCount + unknown.length < clue) return { domains, valid: false };
      if (unknown.length && onCount === clue) { for (const e of unknown) domains[e] = [0]; changed = true; }
      else if (unknown.length && onCount + unknown.length === clue) { for (const e of unknown) domains[e] = [1]; changed = true; }
    }
    // 2. ドット制約(格子点の次数は0本か2本): 未確定辺の全パターンを列挙して可否を判定
    for (let r = 0; r <= n; r++) for (let c = 0; c <= n; c++) {
      const edges = geo.vertexEdges(r, c);
      let onCount = 0; const unknown = [];
      for (const e of edges) { if (domains[e].length === 1) { if (domains[e][0] === 1) onCount++; } else unknown.push(e); }
      if (onCount > 2) return { domains, valid: false };
      if (!unknown.length) { if (onCount !== 0 && onCount !== 2) return { domains, valid: false }; continue; }
      const m = unknown.length, feasiblePer = unknown.map(() => new Set());
      let anyFeasible = false;
      for (let mask = 0; mask < (1 << m); mask++) {
        let extra = 0; for (let k = 0; k < m; k++) if (mask & (1 << k)) extra++;
        const total = onCount + extra;
        if (total === 0 || total === 2) { anyFeasible = true; for (let k = 0; k < m; k++) feasiblePer[k].add((mask >> k) & 1); }
      }
      if (!anyFeasible) return { domains, valid: false };
      unknown.forEach((e, k) => { if (feasiblePer[k].size === 1) { domains[e] = [...feasiblePer[k]]; changed = true; } });
    }
    // 3. 早すぎる閉路の検出: 確定onの辺だけで、すでに閉じた輪ができていないか
    const forcedOn = [];
    for (let e = 0; e < domains.length; e++) if (domains[e].length === 1 && domains[e][0] === 1) forcedOn.push(e);
    if (forcedOn.length) {
      const comp = closedComponent(forcedOn, geo);
      if (comp) {
        if (comp.edges.size !== forcedOn.length) return { domains, valid: false };
        let any = false;
        for (let e = 0; e < domains.length; e++) if (domains[e].length !== 1) { domains[e] = [0]; any = true; }
        if (any) changed = true;
      }
    }
  }
  return { domains, valid: true };
}

3つのルールを順に説明します。

マス制約。 マス(r,c)にクルー(数字)があれば、その4辺のうち確定on本数(onCount)・未確定本数(unknown.length)とクルーを突き合わせます。onCountがクルーを超えていたり、未確定分をすべてonにしてもクルーに届かない場合はvalid: false。未確定分がなくてもクルーに一致するなら残り全部を0に、onCount + unknown.lengthがちょうどクルーに一致するなら残り全部を1に確定させます。
ドット制約(格子点の次数は0本か2本)。 輪は各格子点を「通らない(0本)」か「通過する(2本)」かのどちらかで、3本以上集まったり1本だけで終わったりしてはいけません。その格子点につながりうる最大4本の辺のうち、未確定なm本すべてのon/offの組み合わせ(2^m通り、最大16通り)を総当たりで試し、「合計本数が0か2になる」組み合わせが存在しない値は候補から除外します。
早すぎる閉路の検出。 確定onの辺だけを取り出してclosedComponent(後述)に渡し、それが「ちょうどそのエッジ集合と同じ大きさの閉じた輪」になっていれば、他の未確定な辺はすべて輪の外(0)に確定させます。輪は1本だけなので、確定部分だけで既に閉じているなら、それ以外の辺は輪に参加できないからです。

3つのどれかで矛盾(valid: false)が起きるか、どのマス・どの格子点の候補も変化しなくなるまで(changedが立たなくなるまで)、このループ全体をくり返します。擬似コードと実装の差: マス制約とドット制約はどちらも制約充足問題(CSP)の弧無矛盾(arc consistency)に相当しますが、教科書的なAC-3のようにキューで変化のあった箇所だけを再チェックするのではなく、毎ラウンド全マス・全格子点を走査し直す素朴な実装です。結果(到達する不動点)は同じですが、計算量はAC-3より多くなりえます。マス数36程度の規模なので実用上の問題にはなっていません。

closedComponent(forcedOnEdges, geo)は、確定onの辺だけでグラフを作り、連結成分ごとに「全頂点の次数が2」かつ「辺数=頂点数」(=単純な閉路)になっている成分を探します。

function closedComponent(forcedOnEdges, geo) {
  const adj = new Map();
  for (const e of forcedOnEdges) {
    const [a, b] = geo.endpoints(e);
    if (!adj.has(a)) adj.set(a, []); if (!adj.has(b)) adj.set(b, []);
    adj.get(a).push([b, e]); adj.get(b).push([a, e]);
  }
  const seen = new Set();
  for (const v of adj.keys()) {
    if (seen.has(v)) continue;
    const vertices = new Set([v]), edges = new Set(), queue = [v];
    seen.add(v);
    for (let i = 0; i < queue.length; i++) {
      const cur = queue[i];
      for (const [nb, e] of adj.get(cur)) {
        edges.add(e);
        if (!vertices.has(nb)) { vertices.add(nb); seen.add(nb); queue.push(nb); }
      }
    }
    const allDegree2 = [...vertices].every((u) => adj.get(u).length === 2);
    if (allDegree2 && edges.size === vertices.size && vertices.size > 0) return { vertices, edges };
  }
  return null;
}

これはsolveが最終的な完成盤を検証するisClosedLoop・validateLoop(後述)でも同じ関数がそのまま再利用されている、盤面判定の共通部品です。

伝播の動作例(実行して確認)

n=2の最小盤で、マス(0,0)のクルーだけを0にすると、マス制約だけでそのマスの4辺(H(0,0)・H(1,0)・V(0,0)・V(0,1))が即座に0へ確定します。

const clues = [0, null, null, null];
const state = E.propagate(Array(12).fill(0).map(() => [0, 1]), 2, E.makeGeo(2), clues);
// state.domains[9] (格子点(1,0)につながる辺V(1,0)) も [0] に確定する

実行すると、マス制約で確定した4辺に加えて、格子点(1,0)につながる辺V(1,0)(辺番号9)も[0]に確定します。これはマス制約では説明できません。格子点(1,0)にはH(1,0)(=辺2、マス制約で0に確定済み)・V(0,0)(=辺6、同じく0に確定済み)・V(1,0)(=辺9、未確定)の3本が接続しており、ドット制約が「確定分が0本の状態で残り1本をonにすると合計1本になり、0本にも2本にもならない」と判定してV(1,0)を0に強制するためです。マス制約とドット制約が互いの確定結果を使ってさらに絞り込む、という相互作用の一例です。

前編で示したn=4の全数字入り盤面(clues = [1,3,2,2, 0,2,1,2, 0,1,1,1, 0,1,2,2])に対してpropagateを1回実行すると、分岐探索を一切行わずに40本全辺が確定し、前編で示した答えの輪と完全一致します(実行して確認)。この例では、後述のsolveが候補選択・バックトラックに入る前の段階で解が一意に定まっています。

一意解の判定(solve): 探索打ち切り付きバックトラック

solve(clues, n, nodeLimit = 20000)は、propagateで絞り込んだ上で、それでも未確定な辺が残る場合にバックトラック探索で解の数を数えます。

function solve(clues, n, nodeLimit = 20000) {
  const geo = makeGeo(n);
  const solutions = [];
  let nodes = 0, truncated = false;
  function visit(domains) {
    if (solutions.length >= 2 || truncated) return;
    if (++nodes > nodeLimit) { truncated = true; return; }
    const state = propagate(domains, n, geo, clues);
    if (!state.valid) return;
    let choice = -1;
    state.domains.forEach((d, i) => { if (d.length > 1 && (choice < 0 || d.length < state.domains[choice].length)) choice = i; });
    if (choice < 0) {
      const on = state.domains.map((d) => d[0]);
      if (validateLoop(on, n, geo, clues)) solutions.push(on);
      return;
    }
    for (const v of state.domains[choice]) visit(state.domains.map((d, i) => (i === choice ? [v] : d)));
  }
  const initial = Array(geo.total).fill(0).map(() => [0, 1]);
  const init = propagate(initial, n, geo, clues);
  if (init.valid) visit(init.domains);
  return { solutions, nodes, truncated };
}

要点はSignal後編のsolveと同じ3つです。

MRV(最小残余値)ヒューリスティック。 候補が2つ([0,1])のまま残っている辺のうち、最初に見つかったもの(d.length > 1の中で最小、同点なら辺番号の若い方)から分岐します(辺は必ず0か1の2値なので、Loopでは「候補数が最小の辺」は常に「まだ未確定な辺のうち最初のもの」と同義です。この点は3値以上の候補を持つSignalとの違いです)。
2解で打ち切り。 solutions.length >= 2になった時点で探索をやめます。一意解かどうかの判定に3つ目以降の解は不要だからです。
ノード数上限で打ち切り。 探索ノード数がnodeLimit(既定20,000。generate内では明示的に20,000、tests.cjsの一部テストでは30,000を指定)を超えるとtruncated = trueにして探索を止めます。truncatedが立った場合、solutions.lengthが実際の解の総数を表す保証はありません。

候補がすべて確定した葉ノードでは、isSolvedのような単純な整合性チェックではなくvalidateLoopを呼びます。

function validateLoop(on, n, geo, clues) {
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) {
    const clue = clues[r * n + c];
    if (clue == null) continue;
    const [t, b, l, ri] = geo.cellEdges(r, c);
    if (on[t] + on[b] + on[l] + on[ri] !== clue) return false;
  }
  return isClosedLoop(on, geo);
}
function isClosedLoop(on, geo) {
  const forcedOn = [];
  on.forEach((v, e) => { if (v === 1) forcedOn.push(e); });
  if (!forcedOn.length) return false;
  const comp = closedComponent(forcedOn, geo);
  return !!comp && comp.edges.size === forcedOn.length;
}

validateLoopは「全クルーと一致するか」に加えてisClosedLoopで「onの辺すべてが単一の閉じた輪を構成しているか」を確認します。closedComponentは最初に見つかった閉路成分だけを返すため、comp.edges.size === forcedOn.lengthという比較は「onの辺が、複数の輪に分かれておらず、かつ分岐(次数3以上の格子点)も無く、全部がその1つの閉路に含まれている」ことを保証します。前編で触れた「輪は1本だけ」というルールは、答えの構築段階(isSimplyConnected)だけでなく、この検証段階でも独立にチェックされています。

実測での確認。 tests.cjsには、このvalidateLoopが「特定の1つの答え」だけでなく「クルーを満たす任意の輪」を受理することを示すテストがあります。手作業で選んだクルー集合(n=4)が実際に2つの異なる輪を許すことをsolveで確認し、両方がvalidateLoopを通ることを検証しています(node --test loop/tests.cjsで実行し、20件のテストすべて成功を確認済み)。また、開いた経路(輪が閉じていない)・分岐点(次数3の格子点)・互いに素な2つの輪、といった「輪として不正な形」をvalidateLoopが正しくfalseと判定することも、それぞれ専用のテストで確認できます。

プレイ中の途中チェックとの違い。 clueViolations(on, n, geo, clues)という別の関数もありますが、これは「現在選ばれている辺の本数がクルーと矛盾しているマス」を列挙するだけで、輪が閉じているかは見ません。生成・一意解判定には使われず、loop/app.jsがプレイ中に「数字を超過しています」といった警告を出すためだけに使う、UI側の便宜関数です(生成ロジックの一部ではありません)。

ヒントの間引き(generate内): ランダムな順で1マスずつ、消せる数字だけ消す

前編で見たfullCluesは全マスに数字が入った状態です。実際にプレイヤーへ出題する問題は、この数字の一部をnull(非表示)にしたものです。この間引きはgenerate(n, seed)の内部で行われます。

const order = shuffle([...Array(n * n).keys()], random);
for (const idx of order) {
  const backup = clues[idx];
  clues[idx] = null;
  const check = solve(clues, n, 20000);
  if (check.truncated || check.solutions.length !== 1) clues[idx] = backup;
}

手順は次のとおりです。

全マスの番号(0〜n²-1)をFisher–Yates風のシャッフルでランダムな順に並べる。
その順で1マスずつ、数字をnullにしてみる。
solveを実行し、それでも一意解が保てるならnullのまま確定。探索が打ち切られたか、解が0個・2個以上になったなら、その数字を元に戻す。
全マスを1回ずつ試し終えたら終了。

これは典型的な貪欲(greedy)アルゴリズムです。「今消せるなら消す、消せないなら諦めて次へ進む」という判断を1マスずつ確定させ、一度確定した判断(消した・戻した)はやり直しません。そのため、この手順が返す間引き結果は、消せる数字の最大数を保証しません。消す順序が異なれば、最終的に残る数字の個数や配置が変わりうるという性質があります(README・コードのどちらにも「最大限間引く」という主張はなく、実装上もそのような探索は行われていません)。

ヒントの間引きの再現可能な具体例

前編と同じn=4・シード"notes-example"で、generate内部と同じ手順(growRegion→solve(全数字での事前確認)→シャッフル→間引きループ)を再現した結果です。

シャッフル後の間引き試行順: [6, 0, 8, 4, 11, 15, 5, 14, 1, 7, 10, 9, 2, 13, 12, 3]
実際に消せた(nullのまま確定した)マス番号: [6, 0, 8, 4, 11, 15, 5, 7, 13]

16マス中9マスがnullになり、最終的なクルー配列は次のとおりです(行優先、nullは空欄)。

+   +---+---+   +
  . | 3   2 | 2
+   +---+   +---+
  .   . | .   . |
+   +   +   +   +
  .   1 | 1   . |
+   +   +   +   +
  0   . | 2   . |
+   +   +---+---+

試行順のうち[6, 0, 8, 4, 11, 15, 5, 7, 13]は最後までnullのまま残り、[14, 1, 10, 9, 2, 12, 3]は一度nullにした後、一意解が崩れる(または探索が打ち切られる)ため元の数字に戻されています。同じn・同じシードでgenerate(4, 'notes-example')を再度呼ぶと、試行順・最終的な間引き結果を含めすべてのフィールドが1回目と完全一致します(実行して確認済み)。

tests.cjsには、この間引き結果が「一意解を保つために本当に必要な最小限の情報を持っている」ことを裏付けるテストがあります。nullになっている各マスへ、元の(正しい)数字を1つずつ戻しても、解は変わらず一意のままであることを25シード分検証しています(blank clues never drop below the number needed for a unique solution)。これは「間引き後の数字だけで一意解が確認済み」であることの直接的な帰結であり、情報を足しても壊れないという一貫性の確認であって、「間引きが最大限行われている」ことの証明ではありません。

生成ループ(generate): 最大500試行、失敗時は例外

前編・この記事で見た各部品を組み合わせるのがgenerate(n, seed)です。

function generate(n, seed) {
  if (![4, 5, 6].includes(n) || typeof seed !== 'string' || seed.length > 80) {
    throw new Error('サイズは4〜6、シードは80文字以内で指定してください。');
  }
  const random = rng(seed), geo = makeGeo(n);
  for (let attempt = 1; attempt <= 500; attempt++) {
    const region = growRegion(n, random);
    if (!region) continue;
    const answer = loopEdges(region, n, geo);
    const clues = fullClues(answer, geo, n);
    const fullCheck = solve(clues, n, 20000);
    if (fullCheck.truncated || fullCheck.solutions.length !== 1) continue;
    const order = shuffle([...Array(n * n).keys()], random);
    for (const idx of order) {
      const backup = clues[idx];
      clues[idx] = null;
      const check = solve(clues, n, 20000);
      if (check.truncated || check.solutions.length !== 1) clues[idx] = backup;
    }
    const finalCheck = solve(clues, n, 20000);
    if (finalCheck.truncated || finalCheck.solutions.length !== 1) continue;
    return { n, seed, version: 1, answer, clues, attempt, blanks: clues.filter((c) => c == null).length, cells: n * n };
  }
  throw new Error('500試行で成立する問題が見つかりませんでした。サイズやシードを変更してください。');
}

重要な点は次の3つです。

random(乱数関数)が試行をまたいで使い回される。 rng(seed)はgenerateの先頭で1回だけ呼ばれ、以後のgrowRegion呼び出しや間引きのシャッフルは、この同じ乱数列を順番に消費していきます。growRegionがnullを返した試行や、全数字入りの時点で一意解にならなかった試行では、その時点までに消費した乱数は「捨てられて」次の試行に引き継がれません(次のgrowRegionはその時点のrandomの続きから新しい領域を作ります)。
間引きループの後にもう一度solveで確認する(finalCheck)。 間引きループ自体が、1マス処理するたびに現在のクルー集合でsolveを呼んで一意性を確認しているため、ループが正常に終わった時点で状態はすでに「一意解を保っている」はずです。コードを読んだ限り、finalCheckはこの不変条件を最後にもう一度検証する防御的な二重チェックであり、間引きループの実装が正しい限り失敗しないと考えられますが、finalCheckが実際に失敗するケースを意図的に再現する検証は行っていません。
500試行すべてで条件(サイズ・一意解)を満たす問題が見つからなければ、generateは明示的に例外を投げます。 README・AGENTS.mdが明記する「一意解の探索打ち切りを合格にしない」という方針どおり、この失敗時に「一意解が未確認の問題」を代わりに返すことはありません。loop/worker.jsはこの例外をcatchし、{ id, error: error.message }としてメインスレッドへ送り返すだけで、UI側(app.js)はこのエラーメッセージをそのまま表示します。

性能の実測値

node --test loop/tests.cjsにはn=4,5,6それぞれ25シードずつ、合計75回generateを呼ぶテストが含まれます。手元の実行では、このテストを含む全20件が約3.2秒で完了しました(generated puzzles are uniquely solvable...単体は約2.8秒)。1問あたり平均すると数十ミリ秒程度ですが、これは特定の実行環境・シード集合での実測値であり、あらゆるサイズ・シードでの分布を保証するものではありません。

この記事が確認していないこと

ヒントの間引き(貪欲法)が、理論上消せる最大数にどれだけ近いかは検証していません。試行順序を変えた場合にどの程度残る数字の個数が変わるかの統計的な分布も、この記事の範囲では調べていません。
500試行・ノード上限(一意解確認20,000、tests.cjsの一部は30,000)という具体的な数値が、どの盤サイズでも十分な余裕を持つかどうかの統計的な検証(たとえば6×6で実際に何回目の試行で成功する分布か)は行っていません。
Loopには難易度判定(easy/medium/hardのような分類)を行う関数が存在しないことをエクスポート一覧の確認により把握していますが、「なぜ実装されていないか」という設計判断の理由までは、コード・README・AGENTS.mdのいずれにも記載がなく、この記事でも推測していません。

この結果が言っていないこと

検証はloop/engine.js(エンジンv1)を対象にしています。将来の版で数値・手順が変更される可能性があります。
この記事で示したJSON・テキスト出力は、記事執筆時点で手元のNode.js環境からloop/engine.jsを直接requireして実行した結果です。ブラウザ実行(Web Worker経由、loop/worker.js)と処理内容は同一のはずですが、実行環境の違いによる差異までは検証していません。