Pattern（行・列の数字で塗るお絵かきロジック）の生成ロジックを読む — その2: 一意解判定・生成ループ・失敗時の扱い

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

solve(rowClues, colClues, n, nodeLimit = 20000)は、まずlinePlacementsで全行・全列の配置候補を求め、propagateで絞り込んだ上で、それでも未確定なマスが残る場合にバックトラック探索で解の数を数えます。

function solve(rowClues, colClues, n, nodeLimit = 20000) {
  const rowPlacements = rowClues.map((clue) => linePlacements(clue, n));
  const colPlacements = colClues.map((clue) => linePlacements(clue, 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, rowPlacements, colPlacements);
    if (!state.valid) return;
    let choice = -1;
    for (let i = 0; i < state.domains.length; i++) { if (state.domains[i].length > 1) { choice = i; break; } }
    if (choice < 0) {
      solutions.push(state.domains.map((d) => d[0]));
      return;
    }
    for (const v of state.domains[choice]) visit(state.domains.map((d, i) => (i === choice ? [v] : d)));
  }
  const initial = Array(n * n).fill(0).map(() => [0, 1]);
  visit(initial);
  return { solutions, nodes, truncated };
}

要点はLoop・Signalのsolveと同じ3つです。

• 候補選択。 未確定(length > 1)のマスのうち、最初に見つかったもの(配列を先頭から走査して最初にヒットしたマス)から分岐します。擬似コードと実装の差: LoopやSignalのsolveは「候補数が最小の未確定要素」を明示的に探す(MRV: 最小残余値ヒューリスティック)コードになっていますが、Patternの各マスの候補は常に0・1の2値([0,1])しかなく、候補数に差が出ないため、choiceの探索は単に「最初に見つかった未確定マス」を選ぶ実装になっています。結果として得られる分岐順序は「候補数最小」と同じ(全部が同点)ですが、コード上は最小値の比較を行っていません。
• 2解で打ち切り。 solutions.length >= 2になった時点で探索をやめます。一意解かどうかの判定に3つ目以降の解は不要だからです。
• ノード数上限で打ち切り。 探索ノード数がnodeLimit(既定20,000。generate内では明示的に20,000、tests.cjsの一部テストでは30,000を指定)を超えるとtruncated = trueにして探索を止めます。truncatedが立った場合、solutions.lengthが実際の解の総数を表す保証はありません。

葉ノード(choice < 0、つまり全マスが確定)に達したら、そのままその盤面を解として記録します。LoopのvalidateLoopのような追加の整合性チェックはありません。これは、domainsがpropagateによって常に行・列の数字と矛盾しない状態に保たれているため、全マス確定した時点でそのまま「数字条件を満たす1つの完成盤」になっているからです。

打ち切りの動作例(実行して確認)

nodeLimitに0を渡すと、最初のvisit呼び出しの冒頭で++nodesが1になった時点で1 > 0が成立し、1回もpropagateを実行せずにtruncated: true・solutions.length === 0を返します(tests.cjsのa search budget of zero cannot claim a unique solutionで確認済み)。

前編で見たn=2の曖昧なケース(行・列クルーすべて[1])をsolveに渡すと、伝播だけでは絞り込めないため分岐探索に入り、nodes: 3でsolutions.length === 2([1,0,0,1]と[0,1,1,0])を返します(実行して確認)。一方、前編で見たn=5の具体例は伝播だけで全マスが確定するため、solveはnodes: 1(最初のvisit呼び出しのみ)で一意解に到達します。

生成ループ(generate): 先にランダムな答えを作り、あとで一意解かを検査する

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

function generate(n, seed) {
  if (![5, 8, 10].includes(n) || typeof seed !== 'string' || seed.length > 80) {
    throw new Error('サイズは5・8・10、シードは80文字以内で指定してください。');
  }
  const random = rng(seed);
  for (let attempt = 1; attempt <= 500; attempt++) {
    const density = 0.4 + random() * 0.25;
    const answer = Array(n * n).fill(0).map(() => (random() < density ? 1 : 0));
    const filled = answer.reduce((a, b) => a + b, 0);
    if (filled < Math.max(3, Math.floor(n * n * 0.15)) || filled > n * n - Math.max(3, Math.floor(n * n * 0.15))) continue;
    const { rowClues, colClues } = cluesFor(answer, n);
    const check = solve(rowClues, colClues, n, 20000);
    if (check.truncated || check.solutions.length !== 1) continue;
    if (JSON.stringify(check.solutions[0]) !== JSON.stringify(answer)) continue;
    return { n, seed, version: 1, answer, rowClues, colClues, attempt, cells: n * n };
  }
  throw new Error('500試行で一意解の問題が見つかりませんでした。サイズやシードを変更してください。');
}

手順は次のとおりです。

1. サイズ(n)は5・8・10のいずれか、シードは80文字以内の文字列でなければ、即座に例外。
2. 試行ごとに毎回、塗りの密度(density)を0.4〜0.65の範囲でランダムに決め、各マスを独立に「random() < densityなら塗る」という判定で埋める。 これはLoopのgrowRegion(隣接マスへ広げていく)やSignalの全域木構築のような、マス同士の関係を考慮した構築的な手順ではなく、マス単位で完全に独立な確率的判定です。
3. 塗りマス数(filled)が全体の15%未満、または(全体 − 15%相当)を超える場合はその試行をcontinueで捨てる。n=5ならMath.max(3, Math.floor(25*0.15)) = 3なので、塗りマスが3未満または22超なら不採用です。
4. 残った下書きからcluesForで行・列の数字を作り、solveで一意解になるか確認する。探索が打ち切られた場合(truncated)も、解が0個・2個以上の場合も不採用で、次の試行へ進みます。
5. check.solutions[0](solveが見つけた唯一の解)と、もとのanswer(下書きそのもの)が完全に一致するかをJSON.stringifyで比較する。一致しなければ不採用。
6. 以上をすべて満たした時点で、その問題を返す。

JSON.stringify比較の意味。 propagateが数字条件と矛盾しない状態を保ったまま探索するため、理論上check.solutions[0]は必ずanswerと一致するはずですが、コードはこれを前提とせず明示的に再確認しています。LoopのfinalCheckと同様、実装が正しい限り失敗しないはずの不変条件を、生成の最終段階でもう一度検証する防御的な二重チェックです。これが実際に失敗するケース(solveが返す解が下書きと異なるケース)をこの記事では意図的に再現していません。

擬似コードと実装の差: Loopのgenerateは数字の間引き(一意解を保てる範囲で数字をnullにする)を行いますが、Patternのgenerateにはそのような間引き処理が一切ありません。cluesFor(answer, n)で得た全行・全列の数字が、そのままプレイヤーへ出題する数字になります。README(patternセクション)にも「Loopと異なり数字の間引きは行わず、全行・全列の数字を常に表示します」と明記されており、実装(pattern/engine.jsのエクスポート一覧rng, computeClue, linePlacements, propagate, solve, cluesFor, generate)にも間引き用の関数は存在しません。

再現可能な具体例: 1回目の下書きが2解で不採用になり、2回目で成立する

n=5・シード"notes-example"でgenerateをNode.jsから直接呼び出すと、attempt: 2(1回目は不採用、2回目で成立)という結果になります(実行して確認)。

const p = E.generate(5, 'notes-example');
// { n: 5, seed: 'notes-example', version: 1, attempt: 2, cells: 25,
//   answer: [1,0,1,0,0, 0,0,0,1,1, 1,0,1,1,1, 1,1,0,0,1, 1,1,0,0,0],
//   rowClues: [[1,1],[2],[1,3],[2,1],[2]],
//   colClues: [[1,3],[2],[1,1],[2],[3]] }

盤面(#が塗り、.が空白、行優先)は次のとおりです。

#.#..
...##
#.###
##..#
##...

generate内部の2回の試行を手順どおりに再現すると、それぞれ次のようになります(実行して確認)。

1回目: density=0.5589, filled=12 (下限3・上限22の範囲内) → solve → 解2個 → 不採用
2回目: density=0.4685, filled=13 (下限3・上限22の範囲内) → solve → 解1個 → 採用

1回目は塗りマス数自体は範囲内でしたが、できあがった行・列の数字集合が2通りの塗り方を許してしまい(solveがsolutions.length === 2を返す)、不採用になりました。2回目は同じrandom(1回目で消費した分の続き)から新しい下書きを作り、一意解になったため採用されています。random(乱数関数)は試行をまたいで使い回され、不採用になった試行で消費した乱数列が巻き戻されることはありません(次の試行はその時点の続きから乱数を消費します)。同じn・同じシードでgenerateを再度呼ぶと、密度・下書き・不採用/採用の経緯を含め、すべてのフィールドが1回目と完全一致します(実行して確認済み)。

性能の実測値

node --test pattern/tests.cjsにはn=5,8,10それぞれ8シードずつ、合計24回generateを呼ぶテスト(generated puzzles are uniquely solvable and match the planted grid...)が含まれます。手元の実行では、このテストを含む同ファイル内の全12件(UIテスト・Signalのテスト読み込みを含む)が約117ミリ秒で完了しました。generate単体を24回連続で呼ぶ簡易計測では約11ミリ秒でした(実測、特定の実行環境・シード集合での結果)。

試行回数(attempt)の分布も、n=5・8・10それぞれ20シードで計測したところ、ほとんどが1〜4回目までに成立し(実測)、上限の500試行には遠く及びませんでした。ただし、これは特定のシード集合での観測であり、あらゆるシードでの分布を保証するものではありません。

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

• 密度(0.4〜0.65)・塗りマス数の下限/上限(15%)という具体的な数値が、どのサイズ(5・8・10)でも十分な採用率を保つかどうかの統計的な検証(たとえば10×10で実際に何回目の試行で成立する分布か)は、上記の限定的な実測以上には行っていません。
• 塗りマス単位で完全に独立な確率的判定(random() < density)によって作られる盤面の集合が、可能なすべての一意解付き盤面のうちどれだけを網羅しているか(分布の一様性)は検証していません。
• Patternには難易度判定(easy/medium/hardのような分類)や数字の間引きを行う関数がpattern/engine.jsに存在しないことをエクスポート一覧の確認により把握していますが、「なぜ実装されていないか」という設計判断の理由までは、コード・README・AGENTS.mdのいずれにも記載がなく、この記事でも推測していません。
• pattern/rating.js(プレイ後のスコア・レーティング計算)は生成ロジックの範囲外として扱い、この連載では確認していません。