Signal（回転ネットワーク）の生成ロジックを読む — その1: 盤面表現・乱数・全域木

盤面表現: 4ビットのタイルと循環シフトによる回転

各タイルは0〜15の整数1つで表されます。上下左右への接続を1ビットずつ持つビットマスクです。

const BITS = [1, 2, 4, 8]; // 上・右・下・左（bit0=1,bit1=2,bit2=4,bit3=8）

この対応はapp.js側の描画コードでも同じ並びで使われています(['上','右','下','左'][d])。たとえばmask = 6(2 | 4)は「右と下に接続」、つまりL字(エルボー)のタイルです。

タイルの90°回転は、この4ビットを1つ左に循環シフトする操作として実装されています。

function rotate(mask) { return ((mask << 1) & 15) | (mask >> 3); }

mask=1(上のみ)にrotateを適用すると2(右のみ)になります。「上」の接続が「右」の位置へ移る、つまり物理的には時計回りの90°回転です。UI側の各タイルのaria-labelにも「右回転」と明記されています。

回転を4回繰り返すと元に戻るため、1つのタイルが取りうる見た目は最大4通りです。ただし形状に対称性があると重複します。

function variants(mask) {
  const values = [];
  for (let i = 0; i < 4; i++, mask = rotate(mask)) if (!values.includes(mask)) values.push(mask);
  return values;
}

• 直線(例: mask=5 = 上+下)は回転2通りで元の形に戻るためvariantsは2要素
• 十字(mask=15)は回転しても不変なので1要素
• 端点・L字(エルボー)・T字は4通りすべてが異なるため4要素

このvariantsは後述の一意解探索・難易度判定・初期シャッフルのすべてで「そのタイルが取りうる向きの候補」として使われる、盤面表現の土台です。

乱数: シード文字列 → 32bit状態 → 疑似乱数列

rng(seed)は2段構えです。まずシード文字列をFNV-1a風のハッシュ関数で32bit整数の初期状態に畳み込みます。

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;
  };
}

返り値は呼び出すたびに[0, 1)の浮動小数点数を1つ返す関数です。同じシード文字列ならstateの初期値が一致するため、呼び出し順が同じであれば返す数列も完全に一致します(node --testのseed replay is deterministicで検証済み。後編で再掲)。

この実装に既存アルゴリズムの名称は付いていません(コード中にもコメントなし)。「FNV-1a風のハッシュで初期状態を作り、xorshift系の変換で1個ずつ出力する」という構造の独自実装として扱うのが正確で、特定の有名PRNG(例: mulberry32など)と同一と断定できる根拠はコード上にありません。暗号学的な乱数ではなく、公平性や予測不能性を保証する設計ではありません(後述の限界を参照)。

ランダム全域木: Kruskal風のシャッフル+Union-Find

答え(完成形)は、盤面をグラフと見たときのランダムな全域木として作られます。関数tree(n, random)の手順は次のとおりです。

1. 全マスについて、「右隣」「下隣」への辺だけを列挙する(左・上は隣接マスの辺として二重に数えないため)。n×n盤では辺の総数は2n(n-1)本。
2. この辺リストをFisher–Yates風のループでrandom()を使ってシャッフルする。
3. シャッフル後の順に辺を見て、Union-Find(find)で両端がまだ同じ連結成分でない辺だけを採用し、両端タイルの対応ビットを立てる。

function tree(n, random) {
  const board = Array(n * n).fill(0), parents = board.map((_, i) => i), edges = [];
  function find(i) { while (parents[i] !== i) i = parents[i]; return i; }
  board.forEach((_, i) => [1, 2].forEach(d => {
    const j = neighbor(i, d, n); if (j >= 0) edges.push([i, j, d]);
  }));
  for (let i = edges.length - 1; i > 0; i--) {
    const j = Math.floor(random() * (i + 1)); [edges[i], edges[j]] = [edges[j], edges[i]];
  }
  for (const [i, j, d] of edges) if (find(i) !== find(j)) {
    parents[find(i)] = find(j); board[i] |= BITS[d]; board[j] |= BITS[(d + 2) % 4];
  }
  return board;
}

これはKruskal法の考え方(辺をランダム順に見て、閉路を作らない辺だけ採用する)そのものです。全マスが連結なグラフの辺集合をランダム順で走査してUnion-Findで閉路を弾ぶと、必ず辺数n²-1本の全域木が1本残ります。これは数学的に保証された性質で、この盤面が「一意解」の必要条件である「閉路なし・全マス連結」を、後から検証するまでもなく構築の時点で満たしています(後編のisSolved判定と対応)。

擬似コードと実装の差: 上のKruskal法の説明は一般化した言い方で、実装は「右・下方向の辺だけを列挙する」ことで重複辺の追加を避けている点、Union-Findに経路圧縮(path compression)やランク付き結合(union by rank)を行っていない素朴なfindである点が、教科書的なKruskal実装との細かい違いです。マス数が最大36(6×6)程度の規模なので、性能上の問題にはなりません。

初期シャッフル: 完成形の各タイルを個別にランダム回転

tree()が返すboardは**完成形(答え)**です。プレイヤーに見せる初期盤面は、この答えの各タイルをvariantsの中からランダムに1つ選び直したものです(engine.jsのgenerate関数内)。

const shuffled = answer.map(mask => {
  const v = variants(mask);
  return v[Math.floor(random() * v.length)];
});
if (isSolved(shuffled, n)) continue; // 偶然すでに正解と同じ並びなら、この試行は捨てる

variantsには元の向き自身も含まれるため、タイルによっては「回転しても見た目が変わらない」「たまたま正解の向きが選ばれる」ことがありえます。全体としてshuffledがanswerと完全に一致してしまった場合(=最初から解けている)だけは、この生成試行全体をやり直します(isSolved(shuffled, n)が真ならcontinue)。個々のタイルが正解向きのまま残ること自体は許容されています。

再現可能な具体例

n=4・シード"notes-example"・難易度指定"any"で生成した結果です(Node.jsでsignal/engine.jsをrequireしてE.generate(4, 'notes-example', 'any')を実行。1回目の試行(attempt: 1)でそのまま条件を満たしました)。

{
  "n": 4,
  "seed": "notes-example",
  "attempt": 1,
  "answer":   [4,4,6,12, 3,11,13,1, 2,14,11,8, 2,11,10,8],
  "shuffled": [4,4,3,9,  3,13,13,4, 1,7,14,2,  4,11,10,4]
}

answerをビットから方向へ変換すると(↑上 →右 ↓下 ←左)、次の4×4の完成盤面になります。

この16マスの接続ビットを数えると合計30本(片方向カウント。両端で1辺=2カウント)で、30 / 2 = 15 = n² - 1 = 4×4 - 1と一致します。全域木として必要な辺数と一致することは、board.reduce((s,m)=>s+m.toString(2).replace(/0/g,'').length,0)で誰でも数え直せます。

同じ入力で再度E.generate(4, 'notes-example', 'any')を呼ぶと、answer・shuffledを含めすべてのフィールドが1回目と完全一致します(実行して確認済み)。これはrng(seed)が決定的であることの直接的な帰結です。

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

• 乱数生成器がFNV-1a・xorshift系のどの既存実装とも完全一致すると主張しているわけではありません。挙動(同じシードから同じ数列が出る)は確認していますが、既存アルゴリズムとの数学的な同値性までは検証していません。
• tree()が生成する全域木の分布の一様性(すべての可能な全域木が等確率で出るか)は検証していません。Kruskal風の手順が一様ランダム全域木を生成する保証は、辺の初期順序・シャッフルの品質に依存し、ここでは触れていません。
• 難易度判定・一意解の探索・スコアリングは扱っていません。これらはその2で扱います。