Number Place（9×9数字配置）の生成ロジックを読む — その1: 盤面表現・乱数・完成盤の生成

盤面表現: 行・列・3×3ブロックそれぞれをビットマスクで管理

盤面は9×9=81マスの1次元配列grid(0=空、1〜9=確定した数字)で表されます。マス番号iから行・列・ブロック番号への変換は次の通りです。

const N = 9;
const boxOf = (r, c) => Math.floor(r / 3) * 3 + Math.floor(c / 3);
// r = Math.floor(i / N), c = i % N

盤面が今どの数字を含んでいるかは、gridとは別に、行ごと・列ごと・3×3ブロックごとの3本の配列rows・cols・boxes(各9要素)で管理されます。それぞれの要素は9ビットの整数で、bit (v-1)が立っていれば「その行(列/ブロック)に数字vがすでに存在する」ことを表します。

function place(i, v) {
  const r = Math.floor(i / N), c = i % N, b = boxOf(r, c), bit = 1 << (v - 1);
  grid[i] = v; rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
}
function unplace(i, v) {
  const r = Math.floor(i / N), c = i % N, b = boxOf(r, c), bit = 1 << (v - 1);
  grid[i] = 0; rows[r] &= ~bit; cols[c] &= ~bit; boxes[b] &= ~bit;
}

あるマスiに置ける数字の候補は、511(2進数で9個の1、2^9 - 1)からその行・列・ブロックですでに使われているビットを引いた残りです。

const mask = 511 & ~(rows[r] | cols[c] | boxes[b]);

maskの立っているビット数(popcount)が、そのマスにまだ置ける数字の個数です。0なら矛盾(どの数字も置けない)、1ならその数字で確定、というように、place/unplaceのたびに更新される3本のビットマスクだけで、行・列・ブロックの制約チェックがビット演算1回で済むようになっています。

乱数: Signal・Loopと共通のシード付き疑似乱数

rng(seed)は、他のOrcantus Puzzles作品(Signal・Loop)とまったく同じコードです。

function rng(seed) {
  let state = 2166136261;
  for (const c of String(seed)) state = Math.imul(state ^ c.charCodeAt(0), 16777619);
  return () => {
    state += 0x6D2B79F5;
    let t = Math.imul(state ^ state >>> 15, 1 | state);
    t ^= t + Math.imul(t ^ t >>> 7, 61 | t);
    return ((t ^ t >>> 14) >>> 0) / 4294967296;
  };
}

シード文字列をFNV-1a風のハッシュで32bit整数の初期状態へ畳み込み、以後は呼び出すたびに[0, 1)の浮動小数点数を1つ返します。同じシード文字列なら同じ数列が再現します(node --testのseed replay is deterministicで検証済み。後編で再掲)。この乱数生成器自体の性質(既存アルゴリズムとの同一性が未確認であること、暗号学的な乱数ではないこと)は、Signalの記事その1で述べた限界がそのまま当てはまります。ここでの用途も、Fisher–Yates風のシャッフルにrandom()を渡すshuffle(array, random)という共通ヘルパー1つだけです。

function shuffle(array, random) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

完成盤の生成: MRVバックトラッキングで候補をランダムな順に試す

完成盤(答え)を作るfillFullGrid(random, nodeLimit = 200000)は、空の81マスに対してsearch()という共通のバックトラッキング関数を呼び出します。このsearch()は、後編で扱う「一意解の判定(solve)」とも共有される同じ実装です。

function search(grid, rows, cols, boxes, options) {
  const { nodeLimit, maxSolutions, order, pickCandidates } = options;
  let nodes = 0, truncated = false;
  const solutions = [];
  function visit() {
    if (solutions.length >= maxSolutions || truncated) return true;
    if (++nodes > nodeLimit) { truncated = true; return true; }
    let best = -1, bestMask = 0, bestCount = N + 1;
    for (const i of order) {
      if (grid[i]) continue;
      const r = Math.floor(i / N), c = i % N, b = boxOf(r, c);
      const mask = 511 & ~(rows[r] | cols[c] | boxes[b]);
      const count = popcount(mask);
      if (count === 0) return false;
      if (count < bestCount) { bestCount = count; best = i; bestMask = mask; if (count === 1) break; }
    }
    if (best < 0) { solutions.push(grid.slice()); return solutions.length >= maxSolutions; }
    const candidates = pickCandidates(bestMask);
    for (const v of candidates) {
      place(best, v);
      const stop = visit();
      unplace(best, v);
      if (stop) return solutions.length >= maxSolutions || truncated;
    }
    return false;
  }
  visit();
  return { solutions, nodes, truncated };
}

要点は次の3つです。

• MRV(最小残余値)ヒューリスティック。 まだ埋まっていないマスのうち、候補数字が最も少ないマス(bestCountが最小)を次の分岐対象に選びます。order配列(fillFullGridでは[0, 1, ..., 80]、単純な行優先の走査順)の先頭から見ていくため、候補数が同数の場合はマス番号の若い方が優先されます。候補数が1のマスを見つけた時点でその場でループをbreakし、それ以上の走査を打ち切る早期終了もあります。
• 候補が0個のマスがあれば即座にfalseを返す。 これはそのマスだけでなくvisit()全体の枝刈りで、行き止まりを検出したら残りのマスの走査すら行わずバックトラックします。
• pickCandidatesは呼び出し側が渡す関数。 fillFullGridはこれをshuffle(out, random)(候補数字をランダムな順に並べ替えたもの)として渡します。

function fillFullGrid(random, nodeLimit = 200000) {
  const grid = Array(N * N).fill(0);
  const rows = Array(N).fill(0), cols = Array(N).fill(0), boxes = Array(N).fill(0);
  const order = [...Array(N * N).keys()];
  const randomized = (mask) => {
    const out = [];
    for (let v = 1; v <= 9; v++) if (mask & (1 << (v - 1))) out.push(v);
    return shuffle(out, random);
  };
  const result = search(grid, rows, cols, boxes, { nodeLimit, maxSolutions: 1, order, pickCandidates: randomized });
  if (result.truncated || result.solutions.length !== 1) return null;
  return result.solutions[0];
}

maxSolutions: 1なので、最初に見つかった完成形1つで探索を止めます。候補の試行順がランダムであるため、どの数字がどのマスに入るかはrandom()の消費順に依存しますが、「MRVでどのマスを埋めるか」自体はマスの候補数という決定的な基準で選ばれており、乱数は使われません。 ノード数がnodeLimit(既定20万)を超えた場合、または(理論上起こり得ないはずですが)解が見つからなかった場合はnullを返し、呼び出し元(後編で扱うgenerate)はその試行を諦めて次の試行に進みます。

擬似コードと実装の差: 教科書的な数独ソルバーの説明では「候補を試す」「行き詰まったら戻る」という記述にとどまることが多いですが、この実装は次の点で具体的です。(1) 候補が0個になった時点でforループ自体をreturn falseで打ち切る(全マスを走査し尽くさない)。(2) 候補が1個のマスを見つけた時点でそれ以上マスを探さずbreakする。(3) place/unplaceはgridだけでなくrows/cols/boxesの3本のビットマスクを同時に更新・復元する。いずれも計算量を減らすための具体的な最適化であり、コードを読まなければ分からない詳細です。

再現可能な具体例

シード"notes-example"・難易度"medium"でE.generate('notes-example', 'medium')を実行した結果です(Node.jsでnumberplace/engine.jsをrequireして実行。1回目の試行(attempt: 1)でそのまま条件を満たしました。この関数自体は後編で扱いますが、内部で最初に呼ぶのが本記事のfillFullGridです)。

{"n": 9, "seed": "notes-example", "level": "medium", "version": 1, "attempt": 1, "blanks": 50, "cells": 81}

完成盤(answer)は次の9×9盤です。

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

各行・各列・各3×3ブロックに1〜9が過不足なく1回ずつ現れることは、node --testのthe planted answer is itself a valid completed gridで機械的に検証されています。同じ入力(E.generate('notes-example', 'medium'))を再度呼ぶと、この完成盤を含め結果のすべてのフィールドが1回目と完全一致します(実行して確認済み)。これはrng(seed)が決定的であることの直接的な帰結です。

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

• fillFullGridが生成する完成盤の分布の一様性(すべての可能な数独完成盤が等確率で出るか)は検証していません。MRVヒューリスティックは「候補が少ないマスから確定させる」ことで探索を高速化しますが、これは解の存在確率を均すための工夫ではなく、生成される完成盤の分布に偏りがないことをコードは主張していません。
• 数字の除去による出題盤の作成、一意解の判定、難易度分類、生成ループ全体は扱っていません。これらはその2で扱います。