Number Place（9×9数字配置）の生成ロジックを読む — その2: 数字の除去・一意解判定・難易度

数字の除去(digging): ランダムな順で1マスずつ空け、空けるたびに一意解を確認

generate(seed, level, maxAttempts)は、前編のfillFullGridで完成盤answerを1つ作った後、そのanswerをコピーしたgivensから数字を間引いていきます。空けるマスの順序は、シードと同じ乱数列を使ってシャッフルした0〜80の通し番号です。

const givens = answer.slice();
const order = shuffle([...Array(N * N).keys()], random);
let blanks = 0;
for (const idx of order) {
  if (blanks >= target) break;
  const backup = givens[idx];
  givens[idx] = 0;
  const check = solve(givens, 30000);
  if (check.truncated || check.solutions.length !== 1) givens[idx] = backup;
  else blanks++;
}

手順は単純です。1マスを空けてみて、solve()(後述)でその時点の盤面がまだ一意解かどうかを確認します。一意解のままなら空けたままにしてblanksを1増やし、一意解でなくなる(複数解になる、または探索が打ち切られる)なら戻します。この処理を、目標空きマス数target(難易度ごとに定められた値、後述)に達するか、シャッフル済みの81マスすべてを試し終えるまで続けます。

擬似コードと実装の差: この削り方は「1マスを空けて即座に確認、ダメなら戻す」だけの貪欲法で、複数マスをまとめて空けて解の対称性を利用する、より高度な数独生成アルゴリズム(例: 対称パターンで一気に空ける手法)とは異なります。また、一度空けたマスへの再挑戦(戻したマスを別の空け方の後で改めて試す)は行われません。マスの試行順序自体が一発勝負で、orderを1周してtargetに届かなければ、そのblanksのまま次の処理に進みます。

一意解の判定(solve): 前編と同じsearchを昇順候補・2解打ち切りで使う

一意解の確認に使うsolve(givens, nodeLimit = 30000)は、前編で見たバックトラッキング関数search()を、fillFullGridとは異なるオプションで呼び出しているだけです。

function solve(givens, nodeLimit = 30000) {
  const init = initMasks(givens);
  if (!init) return { solutions: [], nodes: 0, truncated: false };
  const order = [...Array(N * N).keys()];
  const asc = (mask) => { const out = []; for (let v = 1; v <= 9; v++) if (mask & (1 << (v - 1))) out.push(v); return out; };
  return search(init.grid, init.rows, init.cols, init.boxes, { nodeLimit, maxSolutions: 2, order, pickCandidates: asc });
}

前編のfillFullGrid(maxSolutions: 1・候補はshuffleでランダム順)との違いは2点だけです。

• 候補の並び順が昇順(asc)。 乱数を使わず、常に数字の小さい順に試します。一意解の判定には「どの解が先に見つかるか」は関係なく、解の個数だけが問題になるため、乱数を消費する理由がありません。
• maxSolutions: 2で打ち切り。 一意解かどうかを判定するには、解が2個以上見つかった時点で「一意ではない」と確定できるため、3個目以降を探す必要がありません。

initMasks(givens)は、与えられたgivensにすでに矛盾(同じ行・列・ブロックに同じ数字が重複)があればnullを返し、その場合solveは探索すら行わず{ solutions: [], nodes: 0, truncated: false }(解0個・打ち切りなし)を返します。矛盾のない盤面だけが実際の探索に進みます。

ノード数上限による打ち切り。 探索ノード数がnodeLimit(数字除去中は3万、後述の最終確認も同じ3万)を超えるとtruncated: trueになります。truncatedが立った場合、solutions.lengthが実際の解の総数を表す保証はありません。 数字除去のループも、後述の最終確認も、check.truncated || check.solutions.length !== 1を「一意解ではない」として扱います。これはSignalの記事その2で述べた「一意解の探索打ち切りを合格にしない」という方針(AGENTS.mdにも明記)と同じ考え方です。

一意解の検証例

node --test numberplace/tests.cjsには、このsolveの性質を直接確認するテストがいくつかあります。

node --test numberplace/tests.cjs
✔ generated puzzles are uniquely solvable and match the planted full grid, across seeds
✔ a search budget of zero cannot claim a unique solution
✔ an empty grid has more than one solution (not claimed unique)
✔ a grid with a duplicate in a row is rejected as having zero solutions

この記事の執筆時点で実行し、全13件(UI回帰テストを含む)が成功することを確認しました。特にa search budget of zero cannot claim a unique solutionは、nodeLimitに0を渡すと(実際には解が1つしかない出題盤に対しても)必ずtruncated: trueになることを確認しており、「打ち切られた探索を一意解の根拠にしない」という設計を裏付けています。

const p = E.generate('budget');
const result = E.solve(p.givens, 0);
assert.equal(result.truncated, true);

最終盤面の再確認と完成盤の一致確認

target個の空きマスを確保できた(あるいは81マスを試し終えた)後、generateは出来上がったgivensに対してもう一度solveを呼び、一意解であることを再確認します。

const finalCheck = solve(givens, 30000);
if (finalCheck.truncated || finalCheck.solutions.length !== 1) continue;
if (JSON.stringify(finalCheck.solutions[0]) !== JSON.stringify(answer)) continue;

さらに、solveが見つけたその唯一の解が、fillFullGridが作ったanswerと一致するかも文字列比較で確認します。理論上は、正しく実装されていればこの一致は自明(数字除去は常に一意解を保つ操作の連続であり、その唯一解は最初からanswerのはずです)ですが、コードは念のためこれを明示的に検証しており、一致しなければその試行全体をcontinueで捨てます。

難易度分類(levelForBlanks): 探索の難しさではなく「空きマス数」だけで決まる

Number Placeの難易度は、SignalのanalyzeDifficulty(制約伝播・大域推論・限定探索を組み合わせた指標)とは根本的に異なり、空きマス数(givensの少なさ)だけを見る単純な閾値判定です。

const LEVEL_TARGET_BLANKS = { easy: 36, medium: 50, hard: Infinity };
const BLANK_THRESHOLDS = { easy: 45, medium: 54 };

function levelForBlanks(blanks) {
  if (!Number.isInteger(blanks) || blanks < 1 || blanks > 80) throw new Error('Unknown blanks');
  if (blanks <= BLANK_THRESHOLDS.easy) return 'easy';
  if (blanks <= BLANK_THRESHOLDS.medium) return 'medium';
  return 'hard';
}

LEVEL_TARGET_BLANKS(数字除去ループが目指す目標値)とBLANK_THRESHOLDS(実際の空きマス数から難易度ラベルを逆算する閾値)は別の定数です。easyは目標36マスに対し閾値45マス以下、mediumは目標50マスに対し閾値54マス以下、というように余裕を持たせてあります。これは、数字除去ループが目標targetに届く前に(それ以上空けると一意解でなくなるため)止まることがあるためで、目標値ちょうどに達しなくても、実際の空きマス数が閾値の範囲内に収まっていれば、その難易度として採用されます。

この関数は生成側(engine.js)だけでなく、採点側(rating.js)でも同じ関数levelForBlanksをインポートして使っています。 そのためコード上、表示・生成・採点の難易度判定が食い違うことはありません。ただしrating.js自身のコメントが明記する通り、「空きマスが少ないほど確定しやすく初級、多いほど上級」という前提は実プレイによる校正を経ていない暫定値であり、この記事もその限定を踏襲します。マス選択と数字入力の2操作が必要なことを踏まえた1マスあたりの目安秒数(SEC_PER_BLANK = { easy: 6, medium: 10, hard: 15 })も、同様に未検証の値としてコードにコメントされています。

擬似コードと実装の差: 「難易度」という言葉から、多くの読者はSignalのような論理的な解きやすさの指標を連想するかもしれませんが、Number Placeの難易度はそれとは独立した「ヒントの量」の指標です。空きマスが多い(ヒントが少ない)出題盤が、人間にとって必ず解きにくいとは限らない(空きマスの配置次第で難度が変わりうる)ことは、コード上の判定基準には反映されていません。

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

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

function generate(seed, level = 'hard', maxAttempts = 500) {
  if (typeof seed !== 'string' || seed.length > 80) throw new Error('シードは80文字以内の文字列で指定してください。');
  if (!Object.prototype.hasOwnProperty.call(LEVEL_TARGET_BLANKS, level)) throw new Error('未知の難易度です。');
  const target = LEVEL_TARGET_BLANKS[level];
  const random = rng(seed);
  for (let attempt = 1; attempt <= maxAttempts; attempt++) {
    const answer = fillFullGrid(random);
    if (!answer) continue;
    const givens = answer.slice();
    const order = shuffle([...Array(N * N).keys()], random);
    let blanks = 0;
    for (const idx of order) {
      if (blanks >= target) break;
      const backup = givens[idx];
      givens[idx] = 0;
      const check = solve(givens, 30000);
      if (check.truncated || check.solutions.length !== 1) givens[idx] = backup;
      else blanks++;
    }
    const finalCheck = solve(givens, 30000);
    if (finalCheck.truncated || finalCheck.solutions.length !== 1) continue;
    if (JSON.stringify(finalCheck.solutions[0]) !== JSON.stringify(answer)) continue;
    const finalBlanks = givens.filter((v) => v === 0).length;
    if (levelForBlanks(finalBlanks) !== level) continue;
    return { n: N, seed, level, version: 1, answer, givens, attempt, blanks: finalBlanks, cells: N * N };
  }
  throw new Error(`${maxAttempts}試行しても、この難易度（${level}）に一致する一意解の問題が見つかりませんでした。シードや難易度を変更してください。`);
}

重要な点は、前編でも触れたrandom(乱数関数)が試行をまたいで使い回されることです。rng(seed)はgenerateの先頭で1回だけ呼ばれ、以後のfillFullGrid呼び出しや空けるマスの順序シャッフルは、この同じ乱数列を順番に消費していきます。1回の試行が消費するrandom()の回数は、完成盤の作り方(バックトラッキングの分岐回数に依存し、一定ではない)と、81マスのシャッフル(shuffleはN*N - 1 = 80回)の合計で決まりますが、完成盤作りの消費回数は盤面ごとに変わるため、Signalのtree()(1回あたり固定2n(n-1)-1回)のように「何回消費するか」を事前に数式で示すことはできません。試行がcontinueで捨てられた場合、その試行で消費した乱数は次の試行に引き継がれ、無駄になった分だけ以後の結果も変わります。「何回目の試行で採用されたか」を示すattemptフィールドが結果に含まれているのは、この非自明な依存関係を裏付けています。

最大maxAttempts回(既定500)すべてで条件(一意解・指定難易度)を満たす問題が見つからなければ、generateは明示的に例外を投げます。README・AGENTS.mdが明記する通り、この失敗時に「一意解が未確認の問題」や「指定と異なる難易度の問題」を代わりに返すことはありません。

失敗する具体例

maxAttemptsに小さい値(1)を渡すと、シードと難易度の組み合わせによっては実際に1試行で失敗し、例外が投げられることを確認しました。

E.generate('force-fail-seed', 'hard', 1);
// → Error: 1試行しても、この難易度（hard）に一致する一意解の問題が見つかりませんでした。シードや難易度を変更してください。

一方、node --testのgenerate never returns a puzzle whose measured difficulty disagrees with the requested one, even under a tight attempt budgetは、maxAttempts: 1という厳しい制約のもとで多数のシード・難易度の組み合わせを試し、成功する場合は必ずlevelForBlanks(p.blanks) === levelが成り立ち、失敗する場合は必ずエラーメッセージに指定した難易度の文字列が含まれることを確認しています。つまり、試行回数を絞っても「指定と異なる難易度の問題」がこっそり返ることはない、という保証をテストで裏付けています。

再現可能な例(前編と同じ問題)

前編で生成したlevel: "medium"・シード"notes-example"の問題の出題盤(givens)です(実行して確認)。.は空きマスを表します。

5 . . 3 . . . . .
. 7 2 6 . . . 1 9
. . . 9 2 . 4 . 8
. . . . . . 9 . 7
2 . 6 7 9 8 . . 1
. . . 1 4 . 6 . .
. . . . 1 . . 6 .
9 . 8 . . . . . .
. 5 . 2 6 . . 9 4

空きマス数は50(blanks: 50)で、BLANK_THRESHOLDS.medium(54)以下・BLANK_THRESHOLDS.easy(45)を超えているため、levelForBlanks(50) === 'medium'となり、指定したlevel: 'medium'と一致しています(1回目の試行、attempt: 1でそのまま条件を満たしました)。この出題盤に対してsolve(givens, 50000)を実行すると、解は1個だけ見つかり、その解は前編で示した完成盤answerと一致します(実行して確認済み)。同じ入力で再度E.generate('notes-example', 'medium')を呼ぶと、givens・blanks・attemptを含めすべてのフィールドが1回目と完全一致します。

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

• 難易度の閾値(BLANK_THRESHOLDS・LEVEL_TARGET_BLANKSの具体的な数値)が「人間が実際に感じる難しさ」と対応するかどうかは、rating.jsのコメント自身が「実プレイによる校正は未実施」と明記しており、この記事もそれを検証していません。コードに書かれた基準を正確に転記したにとどまります。
• 1マスずつランダムに空けて確認する貪欲な削り方が、より高度な生成アルゴリズム(対称パターンでの一括除去など)と比べて、出題盤の質や空きマス配置の偏りにどう影響するかは検証していません。
• 500試行・ノード上限(数字除去中3万・最終確認3万・完成盤生成20万)という具体的な数値が、どの難易度でも十分な余裕を持つかどうかの統計的な検証(例えばhard指定で実際に何回目の試行で成功する分布か)は、この記事の範囲では行っていません。