Loop（数字で描く一筆の輪）の生成ロジックを読む — その1: 盤面表現・乱数・領域成長

盤面表現: セルではなく「辺」を通し番号で持つ

Loopの盤面はn×nのマス目ですが、プレイヤーが実際に描くのはマスではなく辺(マスとマスの境界線)です。n×nマスの周りには(n+1)×(n+1)個の格子点(ドット)があり、辺はそのドットとドットを結ぶ線分です。makeGeo(n)が、この辺全体に通し番号を振ります。

function makeGeo(n) {
  const numH = (n + 1) * n, numV = n * (n + 1), total = numH + numV;
  const H = (r, c) => r * n + c;
  const V = (r, c) => numH + r * (n + 1) + c;
  const cellEdges = (r, c) => [H(r, c), H(r + 1, c), V(r, c), V(r, c + 1)];
  const vertexEdges = (r, c) => {
    const list = [];
    if (c > 0) list.push(H(r, c - 1));
    if (c < n) list.push(H(r, c));
    if (r > 0) list.push(V(r - 1, c));
    if (r < n) list.push(V(r, c));
    return list;
  };
  const endpoints = (e) => { /* 辺番号 → 両端の格子点2つ */ };
  return { n, numH, numV, total, H, V, cellEdges, vertexEdges, endpoints };
}

• 水平な辺は(n+1)行×n列でnumH = (n+1)*n本。H(r, c)はマス(r,c)の上にある横線です(rは0〜n)。
• 垂直な辺はn行×(n+1)列でnumV = n*(n+1)本。番号は水平な辺の続き(numHからのオフセット)で振られます。
• n=4ならnumH = 5*4 = 20本、numV = 4*5 = 20本、合計total = 40本です(実行して確認)。

各辺は0(選ばれていない)か1(輪の一部として選ばれている)かの2値で表され、盤面全体は長さtotalの配列(on)として持たれます。これは前編のSignal記事でのタイル単位のビットマスク表現とは根本的に異なる表現です。Loopには「タイルの向き」という概念がなく、代わりに「どの辺が輪に含まれるか」という辺集合そのものが状態です。

cellEdges(r, c)はマス(r,c)を囲む4辺(上・下・左・右)を返し、後述のクルー(数字)計算に使います。vertexEdges(r, c)は格子点(r,c)に接続しうる辺(最大4本、盤の端では少ない)を返し、後編で見る「輪は各格子点で0本か2本しか通らない」という制約に使われます。

乱数: Signalと完全に同じ実装

rng(seed)はloop/engine.jsとsignal/engine.jsで1文字も違わない同一のコードです(diffコマンドで比較し、差分ゼロを確認済み)。

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個ずつ返す、という構造はSignal前編で説明した内容がそのまま当てはまります。同じシード文字列なら同じ数列が同じ順番で得られるという性質も同じです。ただし、これは2ファイルに同じコードが重複して存在しているだけで、共有モジュールとして1箇所にまとめられているわけではありません(loop/engine.js・signal/engine.jsはそれぞれ独立した単一ファイルで、requireやimportによる共有は一切ありません)。

ランダム領域成長: 境界から広がる「穴のない」連結領域

答え(完成形)の元になるのは、n×nマスのうち一部を選んだ領域です。growRegion(n, random)が、1マスから隣接マスへとランダムに広げていく形でこれを作ります。

function growRegion(n, random) {
  const cells = n * n, cellIndex = (r, c) => r * n + c;
  for (let attempt = 0; attempt < 300; attempt++) {
    const start = Math.floor(random() * cells);
    const region = new Set([start]);
    const frontier = new Set();
    /* addFrontier(i): regionに隣接する未選択マスをfrontierへ追加 */
    addFrontier(start);
    const targetMin = Math.max(3, Math.floor(cells * 0.35));
    const targetMax = Math.max(targetMin + 1, Math.ceil(cells * 0.75));
    const target = targetMin + Math.floor(random() * (targetMax - targetMin + 1));
    while (region.size < target && frontier.size) {
      const arr = [...frontier];
      const pick = arr[Math.floor(random() * arr.length)];
      frontier.delete(pick); region.add(pick); addFrontier(pick);
    }
    if (region.size < 3 || region.size > cells - 1) continue;
    if (isSimplyConnected(region, n)) return region;
  }
  return null;
}

手順は次のとおりです。

1. ランダムな1マス(start)から領域を始める。
2. 領域に隣接する未選択マスの集合(frontier)から、ランダムに1マスずつ選んで領域に加える(「フロンティア拡張」によるランダム成長)。これを目標サイズ(target)に達するか、もう広げられなくなるまで繰り返す。
3. targetは全体マス数の35%(下限3マス)〜75%の範囲でランダムに決める。n=4(16マス)ならtargetMin = max(3, floor(16*0.35)) = 5、targetMax = max(6, ceil(16*0.75)) = 12で、5〜12マスの範囲になります(実行して確認)。
4. 出来上がった領域が小さすぎる(3マス未満)・大きすぎる(全マスから1マス引いた数を超える、つまり領域外が0マス)場合はやり直す。
5. isSimplyConnected(region, n)で「穴が無いか」を確認する。穴があれば(=領域に囲まれて盤の外周へ到達できないマスが領域外にあれば)やり直す。
6. 以上を最大300回試行し、条件を満たす領域が得られなければnullを返す(呼び出し元のgenerateはこの場合その試行全体をcontinueで捨てる。後編で扱う)。

isSimplyConnectedは、盤の外周マスから幅優先探索で「領域の外側」を塗りつぶし、その到達マス数が「本来の領域外マス数」と一致するかを見ます。一致しなければ、外周から到達できない領域外マス(=穴)が存在するということです。

function isSimplyConnected(region, n) {
  const cells = n * n, cellIndex = (r, c) => r * n + c;
  const outside = new Set(), queue = [];
  const mark = (i) => { if (!region.has(i) && !outside.has(i)) { outside.add(i); queue.push(i); } };
  for (let c = 0; c < n; c++) { mark(cellIndex(0, c)); mark(cellIndex(n - 1, c)); }
  for (let r = 0; r < n; r++) { mark(cellIndex(r, 0)); mark(cellIndex(r, n - 1)); }
  /* queueをBFSで広げ、regionに属さない隣接マスをoutsideへ追加していく */
  let nonRegion = 0;
  for (let i = 0; i < cells; i++) if (!region.has(i)) nonRegion++;
  return outside.size === nonRegion;
}

輪パズルとして意味を持つためには、領域(と、その裏返しである領域外)がそれぞれ「1つのつながった塊」である必要があります。穴のある領域(例: ドーナツ状)の境界線は2本の輪になってしまい、「ひとつながりの単純な輪」というルールに反するため、isSimplyConnectedはこれを事前に排除しています。

擬似コードと実装の差: 上の手順説明は一般化した言い方ですが、実装では「フロンティア拡張」はSetのfor...of展開([...frontier])による配列化とランダムインデックス選択で行われており、優先度付きキューのような構造は使っていません。マス数が最大36(6×6)程度の規模なので、性能上の問題にはなりません。

答えの輪の構築: 領域の境界がそのまま輪になる

growRegionが返すのは「マスの集合」であって、輪(辺の集合)そのものではありません。輪への変換はloopEdges(region, n, geo)が機械的に行います。

function loopEdges(region, n, geo) {
  const on = new Array(geo.total).fill(0);
  const inside = (r, c) => r >= 0 && r < n && c >= 0 && c < n && region.has(r * n + c);
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) {
    const here = inside(r, c);
    const [top, bottom, left, right] = geo.cellEdges(r, c);
    if (here !== inside(r - 1, c)) on[top] = 1;
    if (here !== inside(r + 1, c)) on[bottom] = 1;
    if (here !== inside(r, c - 1)) on[left] = 1;
    if (here !== inside(r, c + 1)) on[right] = 1;
  }
  return on;
}

考え方はシンプルです。マス(r,c)とその上下左右の隣接マスで「領域に属するかどうか」が食い違っていれば、その間の辺は領域の境界線なのでonにする。一致していれば境界ではないので触りません(盤の外は常に「領域外」として扱われるので、inside(-1, c)は必ずfalseになり、盤の一番上の行が領域内なら最上段の横辺は自動的に境界線になります)。

この手順により、領域が「穴のない連結な塊」でありさえすれば、その境界線は必ず1本のつながった閉じた輪になります。isSimplyConnectedで穴を排除しているのはこのためで、前編のSignalにおける「全域木の構築がそのまま木の完成条件を満たす」のと同じ構図です。答えが持つべき性質(単純な閉じた輪であること)を、後から検証するのではなく構築の手順そのもので保証しています。

各マスのクルー(数字)は、そのマスを囲む4辺のうちonになっている本数を数えるだけです。

function clueFor(on, geo, r, c) {
  const [top, bottom, left, right] = geo.cellEdges(r, c);
  return on[top] + on[bottom] + on[left] + on[right];
}
function fullClues(on, geo, n) {
  const clues = [];
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) clues.push(clueFor(on, geo, r, c));
  return clues;
}

このfullCluesが返す配列が、まだ何も間引かれていない「全マスに数字が入った」状態です。後編で見る一意解判定・ヒントの間引きは、すべてこの配列を出発点にします。

再現可能な具体例

n=4・シード"notes-example"で、Node.jsからloop/engine.jsをrequireしてgrowRegionとloopEdgesを直接呼び出した結果です(内部のrng('notes-example')を1つの乱数関数として使い回しています)。

const random = E.rng('notes-example');
const region = E.growRegion(4, random);   // Set { 1, 2, 6, 7, 10, 11, 14, 15 }

growRegionは1回目の試行(内部の300回ループのうち1周目)でこの領域を返しました(乱数呼び出し回数は9回)。4×4マスを行優先(r*4+c)で並べたとき、選ばれたマスは次のとおりです(#が領域内、.が領域外)。

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

これは偶然、中央2列がそのまま選ばれた縦長の長方形になっています(growRegionのランダム性による結果の一例であり、常にこの形になるわけではありません)。loopEdgesでこの領域の境界を求めると、期待どおり中央2列を囲む1本の長方形の輪になります。fullCluesでまだ何も間引かれていない全16マスに数字を振ると次のようになります(|・-が輪、数字がそのマスのクルー)。

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

clues配列としては[1,3,2,2, 0,2,1,2, 0,1,1,1, 0,1,2,2](行優先)です。この時点ではまだ1マスも間引かれておらず、後編で見る「一意解を保てる範囲でランダムに数字を消していく」処理を経る前の状態です。

同じn・同じシードで再度growRegion・loopEdgesを呼ぶと、領域・輪・クルーのすべてが1回目と完全一致します(実行して確認済み)。これはrng(seed)が決定的であることの直接的な帰結です。

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

• growRegionが生成する領域の分布の一様性(可能なすべての「穴のない連結領域」が等確率で出るか)は検証していません。フロンティア拡張によるランダム成長は、開始マスや成長順序に依存した偏りを持ちうる典型的な手法であり、この記事では触れていません。
• 制約伝播・一意解の探索・ヒントの間引き・生成ループ全体は扱っていません。これらはその2で扱います。
• LoopにはSignalにあるanalyzeDifficultyのような難易度判定関数が実装に存在しないことを、loop/engine.jsのエクスポート一覧(rng, makeGeo, growRegion, isSimplyConnected, loopEdges, clueFor, fullClues, propagate, closedComponent, isClosedLoop, clueViolations, validateLoop, solve, generate)を確認して把握しています。難易度に関する記述は後編でも扱いません。