Pattern（行・列の数字で塗るお絵かきロジック）の生成ロジックを読む — その1: 盤面表現・乱数・配置列挙・伝播

盤面表現: マス目は1次元配列、行・列はそこから切り出す

Patternの盤面(答え・作業中の状態)は、n×nマスを行優先で並べた長さn²の1次元配列(各要素は0か1)として持たれます。行・列そのものを表す専用の構造体は無く、必要になった箇所でその都度切り出します。

function rowsOf(grid, n) {
  const rows = [];
  for (let r = 0; r < n; r++) rows.push(grid.slice(r * n, r * n + n));
  return rows;
}
function colsOf(grid, n) {
  const cols = [];
  for (let c = 0; c < n; c++) {
    const col = [];
    for (let r = 0; r < n; r++) col.push(grid[r * n + c]);
    cols.push(col);
  }
  return cols;
}

rowsOfはsliceで連続領域を取り出すだけですが、colsOfは列方向が配列上で飛び飛びの位置にあるため、1マスずつ拾い集めます。この非対称性(行はslice、列はループ)は、後述のpropagate・propagateColumnsが別関数として分かれている理由でもあります。

各行・各列の「数字」(クルー)は、computeClue(line)が塗りマス(1)の連続run(連の長さ)を数えて求めます。

function computeClue(line) {
  const runs = [];
  let run = 0;
  for (const v of line) {
    if (v === 1) run++;
    else { if (run) runs.push(run); run = 0; }
  }
  if (run) runs.push(run);
  return runs;
}

たとえば[0,1,1,0,1]は[2,1](2連続の塗り、1マス空けて1連続の塗り)、[0,0,0](塗りマスなし)は空配列[]になります(いずれもtests.cjsで確認済み)。全行・全列にこれを適用するのがcluesFor(grid, n)です。

function cluesFor(grid, n) {
  return { rowClues: rowsOf(grid, n).map(computeClue), colClues: colsOf(grid, n).map(computeClue) };
}

乱数: LoopやSignalと同一の実装

rng(seed)はpattern/engine.js・loop/engine.js・signal/engine.jsの3ファイルで1文字も違わない同一のコードです(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整数の初期状態へ畳み込み、以後はxorshift系の変換で[0, 1)の浮動小数点数を1個ずつ返します。同じシード文字列なら同じ数列が同じ順番で得られるため、後編で見るgenerateの結果は同一のn・同一のシードで完全に再現します。3エンジンにまたがって同じコードが重複しているだけで、共有モジュールとしてまとめられているわけではない点も他2作と同様です(requireやimportによる共有は無く、pattern/engine.jsは他のどのファイルにも依存しない単一ファイルです)。

行・列の配置列挙: 数字が許すすべての塗り方を再帰で列挙する

Patternの核心部分は、「ある行(または列)の数字(クルー)が与えられたとき、その行が取りうるすべての塗り方」を列挙するlinePlacements(clue, length)です。これはrunStarts(clue, length)(各runの開始位置の組み合わせを再帰で列挙)の結果を、実際の0/1配列に変換したものです。

function runStarts(clue, length) {
  const k = clue.length;
  const results = [];
  function rec(idx, minStart, starts) {
    if (idx === k) { results.push(starts.slice()); return; }
    const run = clue[idx];
    let restMin = 0;
    for (let j = idx + 1; j < k; j++) restMin += clue[j] + 1;
    for (let start = minStart; start + run + restMin <= length; start++) {
      starts.push(start);
      rec(idx + 1, start + run + 1, starts);
      starts.pop();
    }
  }
  rec(0, 0, []);
  return results;
}

function linePlacements(clue, length) {
  return runStarts(clue, length).map((starts) => {
    const line = Array(length).fill(0);
    starts.forEach((s, i) => { for (let j = 0; j < clue[i]; j++) line[s + j] = 1; });
    return line;
  });
}

考え方は次のとおりです。

1. clueは[run1, run2, ...]という連の長さの並び(例: [1,3]は「長さ1の連」に続いて「長さ3の連」)。
2. rec(idx, minStart, starts)は、idx番目のrunをどこから始めるか(start)を、minStart以降のすべての位置で試す再帰関数。あるrunをstartから置いたら、次のrunは最低でもstart + run + 1(そのrunの直後に空白マス1つを挟んだ位置)以降からしか置けません。
3. restMinは「idx番目より後ろの全runが、最低限必要とする長さの合計(runの長さ + 区切りの空白1マスずつ)」です。start + run + restMinがlengthを超えてしまうstartは、後続のrunが入り切らないため試しません(枝刈り)。
4. すべてのrunの開始位置が決まったら(idx === k)、その組み合わせをresultsへ記録します。

擬似コードと実装の差: これは深さ優先探索によるバックトラックですが、実装上「候補を試して駄目なら戻る」という失敗パスは存在しません。forループの範囲(start + run + restMin <= length)自体が「入り切る候補だけ」に絞られているため、recが生成するすべての組み合わせはそのまま有効な配置であり、列挙した時点で全部が採用対象です(教科書的なバックトラック法によくある「無効な組み合わせを生成してから捨てる」処理はありません)。

具体例として、linePlacements([1,3], 5)は[[1,0,1,1,1]]という1通りだけを返します(実行して確認)。長さ1の連と長さ3の連を、間に空白1マス以上を挟んで長さ5に収める置き方は、この1通りしかありません。一方linePlacements([1,1], 5)は6通りを返します。

[1,0,1,0,0]  [1,0,0,1,0]  [1,0,0,0,1]
[0,1,0,1,0]  [0,1,0,0,1]  [0,0,1,0,1]

2つの長さ1の連を、間に空白を1マス以上空けて長さ5の行に収める置き方が、ちょうど6通り(2つの隙間を含めた「玉3個(連2つ+余白1)を4箇所に配る」組み合わせ数C(4,2)=6)あることに対応します。

制約伝播(propagate): 全配置候補が一致するマスだけ確定させる

propagate(domains, n, rowPlacements, colPlacements)は、各マスの候補(domains[i]。[0]・[1]・[0, 1]のいずれか)を、行・列それぞれの数字が許す配置と突き合わせてくり返し絞り込みます。

function propagateLines(domains, n, count, offsetFor, placementsFor) {
  let changed = false;
  for (let i = 0; i < count; i++) {
    const offset = offsetFor(i);
    const filtered = filterPlacements(placementsFor(i), domains, offset, n);
    if (!filtered.length) return { valid: false, changed: false };
    for (let pos = 0; pos < n; pos++) {
      let sawZero = false, sawOne = false;
      for (const p of filtered) { if (p[pos] === 0) sawZero = true; else sawOne = true; if (sawZero && sawOne) break; }
      const idx = offset + pos;
      if (domains[idx].length > 1) {
        if (sawZero && !sawOne) { domains[idx] = [0]; changed = true; }
        else if (sawOne && !sawZero) { domains[idx] = [1]; changed = true; }
      }
    }
  }
  return { valid: true, changed };
}

行(または列)ごとに、次の手順を行います。

1. filterPlacementsで、その行の全配置候補(linePlacementsが返した配列)のうち、現在のdomains(各マスの確定/未確定状態)と矛盾しないものだけを残す(filtered)。
2. filteredが1つも残らなければ(!filtered.length)、その時点でvalid: false。数字の並びが現在の盤面のどの塗り方とも両立しないという矛盾です。
3. 行内の各マス位置(pos)について、filteredに残った配置を1つずつ見て、そのマスが「常に0」(sawZero && !sawOne)か「常に1」(sawOne && !sawZero)かを判定する。全候補が同じ値で一致していれば、そのマスをその値に確定させる。1つでも食い違いがあれば(sawZero && sawOne)、そのマスはまだ未確定のまま残す。

これは行・列それぞれについて独立に行われ、行の結果が列の入力になり列の結果が行の入力になる、という相互作用を、変化が止まるまでくり返します。

function propagate(domains, n, rowPlacements, colPlacements) {
  domains = domains.map((d) => d.slice());
  let changed = true;
  while (changed) {
    changed = false;
    const rowResult = propagateLines(domains, n, n, (r) => r * n, (r) => rowPlacements[r]);
    if (!rowResult.valid) return { domains, valid: false };
    if (rowResult.changed) changed = true;
    const colResult = propagateColumns(domains, n, colPlacements);
    if (!colResult.valid) return { domains, valid: false };
    if (colResult.changed) changed = true;
  }
  return { domains, valid: true };
}

propagateColumnsはpropagateLinesと同じロジックを列方向(colsOfと同様、1マスずつ拾い集める形)で再実装したものです。行を1次元のsliceで、列を明示的なループで扱うという盤面表現の非対称性(前述)がそのまま、この2つの別関数として現れています。

擬似コードと実装の差: これもLoopやSignalのpropagateと同じく、変化のあった行・列だけを再チェックするAC-3的なキューではなく、毎ラウンド全行・全列を走査し直す素朴な実装です。到達する不動点(最終的な絞り込み結果)は同じですが、計算量はキュー方式より多くなりえます。盤面が最大10×10程度の規模なので、実用上の問題にはなっていません。

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

n=2・行クルー[[1],[1]]・列クルー[[1],[1]](「各行・各列にちょうど1マスだけ塗る」)という、Loopの一意解判定回でも触れたのと同型の曖昧なケースを試すと、propagateは一切絞り込めません。

const rowPlacements = [[[1,0],[0,1]], [[1,0],[0,1]]]; // 各行の配置候補は2通りずつ
const state = E.propagate(Array(4).fill(0).map(() => [0, 1]), 2, rowPlacements, colPlacements);
// state.domains は [[0,1],[0,1],[0,1],[0,1]] のまま(実行して確認)

実際、この数字条件には[1,0,0,1](左上と右下を塗る)・[0,1,1,0](右上と左下を塗る)という2つの解があり(solveで確認、後編で詳述)、どのマスも「全候補で値が一致」しないため、伝播だけでは1マスも確定しません。この場合、後編で見るバックトラック探索に頼ることになります。

一方、後編で使うn=5の具体例(rowClues = [[1,1],[2],[1,3],[2,1],[2]]・colClues = [[1,3],[2],[1,1],[2],[3]])では、propagateを1回実行するだけで25マス全部が確定し、分岐探索を一切行わずに答えが定まります(実行して確認)。数字の情報量によって、伝播だけで解けるか、探索が必要かが変わるという、典型的な制約充足問題(CSP)の性質がそのまま現れています。

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

• linePlacementsが返す配置候補の順序が、後続の探索(後編で見るsolveのMRVヒューリスティック)の効率にどう影響するかは検証していません。
• 一意解の判定(solve)・生成ループ全体・失敗時の扱いは扱っていません。これらはその2で扱います。
• PatternにはLoopにある数字の間引きや、Signalにある難易度判定関数がpattern/engine.jsのエクスポート一覧(rng, computeClue, linePlacements, propagate, solve, cluesFor, generate)に存在しないことを確認していますが、この点は後編で扱います。