Signal（回転ネットワーク）の生成ロジックを読む — その2: 一意解判定・難易度・スコア

候補集合と制約伝播(propagate)

各タイルの「向きの候補」は前編で見たvariants(mask)です。propagate(input, n)は、この候補集合を隣接マス同士の整合性でくり返し絞り込みます。

function propagate(input, n) {
  const domains = input.map(a => a.slice());
  let changed = true, rounds = 0;
  while (changed) {
    changed = false; rounds++;
    for (let i = 0; i < domains.length; i++) {
      const next = domains[i].filter(mask => BITS.every((bit, d) => {
        const j = neighbor(i, d, n);
        return j < 0 ? !(mask & bit)
          : domains[j].some(other => !!(mask & bit) === !!(other & BITS[(d + 2) % 4]));
      }));
      if (!next.length) return { domains, valid: false, rounds };
      if (next.length !== domains[i].length) changed = true;
      domains[i] = next;
    }
  }
  return { domains, valid: true, rounds };
}

ルールは2つだけです。

1. 盤の外側に向かう辺(j < 0)を持つ候補は除外する(境界からはみ出す接続は不可)。
2. 隣接マスjの候補すべてが、こちら側の接続の有無と矛盾する場合、その候補を除外する。

どのマスの候補も変化しなくなるまで(changedが立たなくなるまで)くり返します。これは制約充足問題(CSP)における弧無矛盾(arc consistency)を求める処理の一種です。擬似コードと実装の差: 教科書的なAC-3はキューで変化のあった弧だけを再チェックしますが、この実装は毎ラウンド全マスを走査し直す素朴な実装です。結果(到達する不動点)は同じですが、計算量はAC-3より多くなりえます。マス数36程度の規模なので実用上の問題にはなっていません。

どこかのマスの候補が0件になった場合、valid: falseを返します。これは「この部分割り当てでは解が存在しない」ことを意味し、後述の探索での枝刈りに使われます。

一意解の判定(solve): 探索打ち切り付きバックトラック

solve(board, n, nodeLimit = 30000)は、boardの各マスの形状(variants(mask))を候補として、実際に何通りの完成形がありうるかを数えます。

function solve(board, n, nodeLimit = 30000) {
  const initial = propagate(board.map(variants), n), solutions = [];
  let nodes = 0, truncated = false;
  function visit(input) {
    if (solutions.length >= 2 || truncated) return;
    if (++nodes > nodeLimit) { truncated = true; return; }
    const state = propagate(input, n);
    if (!state.valid) return;
    let choice = -1;
    state.domains.forEach((a, i) => {
      if (a.length > 1 && (choice < 0 || a.length < state.domains[choice].length)) choice = i;
    });
    if (choice < 0) {
      const answer = state.domains.map(a => a[0]);
      if (isSolved(answer, n)) solutions.push(answer);
      return;
    }
    for (const value of state.domains[choice]) visit(state.domains.map((a, i) => i === choice ? [value] : a));
  }
  if (initial.valid) visit(initial.domains);
  return { solutions, nodes, truncated, deduction: initial.domains.filter(a => a.length === 1).length, rounds: initial.rounds };
}

要点は次の3つです。

• MRV(最小残余値)ヒューリスティック。 候補が複数残っているマスのうち、候補数が最も少ないマスから分岐します(state.domainsの先頭から走査するため、候補数が同じ場合はマス番号の若い方が優先されます。この優先順位は乱数ではなくマスの並び順に依存する決定的な挙動です)。
• 2解で打ち切り。 solutions.length >= 2になった時点で探索をやめます。一意解かどうかの判定に3つ目以降の解は不要だからです。
• ノード数上限で打ち切り。 探索ノード数がnodeLimit(既定30,000)を超えるとtruncated = trueにして探索を止めます。truncatedが立った場合、solutions.lengthが実際の解の総数を表す保証はありません。

生成側(後述のgenerate)は、verification.truncated || verification.solutions.length !== 1のときその問題を不採用にします。つまり「探索打ち切りで確認できなかった問題」は一意解問題として扱われません(AGENTS.mdにある「一意解の探索打ち切りを合格にしない」という方針が、ここでコードとして実装されています)。

完成判定isSolvedは探索の終端でも使われる独立した検証です。

function isSolved(board, n) {
  if (board.length !== n * n) return false;
  let edges = 0;
  for (let i = 0; i < board.length; i++) for (let d = 0; d < 4; d++) {
    const j = neighbor(i, d, n), has = !!(board[i] & BITS[d]);
    if (has && (j < 0 || !(board[j] & BITS[(d + 2) % 4]))) return false;
    if (has) edges++;
  }
  return edges / 2 === board.length - 1 && connected(board, n).size === board.length;
}

「境界からはみ出す接続・相互不整合な接続が無い」「辺数がちょうどn²-1(木の辺数)」「始点から幅優先探索(connected)した到達マス数が全マス数と一致(単一の連結成分)」の3条件です。前編で見た通り、tree()が作る答えはこの条件を構築時点で満たしますが、isSolved自体は答えの作り方に依存しない独立した判定であり、探索が見つけた任意の割り当てにも同じ基準を適用します。

一意解の検証例

node --test tests.cjsには、このsolveを独立に検証するテストがあります。2×2盤(4マス)のすべての「端点・直線・エルボー・T字」の組み合わせ(各マス4通り×4マス=256通り)について、solveが返す解の数を、ビット演算だけで書いた別実装のブルートフォースと突き合わせています(exhaustive verifier agrees with independent brute force on all 2x2 tile degree combinations)。この記事の執筆時点で実行し、256通りすべてで一致することを確認しました。

node --test tests.cjs
✔ exhaustive verifier agrees with independent brute force on all 2x2 tile degree combinations

また、探索打ち切りが正しく機能することも専用のテストで確認できます。

// 16マス全部が「上下左右すべて接続」という候補固定の盤で、nodeLimitを0にすると即座に打ち切られる
assert.equal(E.solve(Array(16).fill(3), 4, 0).truncated, true);

難易度判定(analyzeDifficulty): 局所推論→大域推論→限定探索

難易度は、一意解の確認とは別の関数analyzeDifficulty(board, n)で判定されます。ここでのノード上限は5,000(一意解確認の30,000とは異なる値)です。手順は3段階です。

1. 境界だけの絞り込み(boundaryDomains)。 盤の端にあるマスは、外側への接続を持てないという制約だけで候補が絞れます。
2. 局所推論のくり返し(localStep)。 propagateと同じロジックの隣接マス同士の整合性チェックを、候補が変化しなくなるまでくり返します(localRoundsをカウント)。
3. 大域推論(graphConflict)。 局所推論が止まった後、各候補について「その値を選ぶと必須辺だけで閉路ができるか」「可能な辺のグラフが分断されるか」を確認し、矛盾する候補を除外します。これで新たに絞り込みが起きればまた2に戻り、止まればまた3を試す、を最大board.length * 4回くり返します(globalRoundsをカウント)。

function graphConflict(domains, n) {
  if (domains.some(a => !a.length)) return true;
  const parent = domains.map((_,i)=>i), possible = domains.map(()=>[]);
  const find = i => { while (parent[i] !== i) i=parent[i]; return i; };
  for (let i=0;i<domains.length;i++) for (const d of [1,2]) {
    const j=neighbor(i,d,n); if(j<0)continue;
    const bit=BITS[d], opposite=BITS[(d+2)%4];
    if(domains[i].some(v=>v&bit)&&domains[j].some(v=>v&opposite)){possible[i].push(j);possible[j].push(i);}
    if(domains[i].every(v=>v&bit)&&domains[j].every(v=>v&opposite)){
      const a=find(i),b=find(j);if(a===b)return true;parent[a]=b;
    }
  }
  const seen=new Set([0]),queue=[0];
  for(let k=0;k<queue.length;k++)for(const j of possible[queue[k]])if(!seen.has(j)){seen.add(j);queue.push(j);}
  return seen.size!==domains.length;
}

前半(Union-Find)は「両マスが確実につながる」辺だけを使って閉路を検出します。後半(BFS)は「つながる可能性がある」辺だけを使って、マス0から到達できない領域(=将来孤立しうる領域)があるかを検出します。この2つは別の判定基準であり、graphConflictは「閉路確定」と「到達不能の可能性」のどちらか一方でも真ならtrueを返す点に注意してください(1つの関数が2つの異なる矛盾を検出しています)。

大域推論でも詰め切れずに候補が複数残ったマスがあれば、限定探索(solveと同様のMRV分岐、ただしgraphConflictも枝刈りに使う独自のsearch関数)に入り、maxDepth(探索の深さ)・decisionPoints(分岐した回数)・nodesを記録します。ここでもノード数が5,000を超えればtruncated: trueになります。

難易度のしきい値(コードそのまま)

const substantial = remaining >= Math.max(8, Math.ceil(board.length * .3)) && largestRegion >= 6;
const demanding = globalRounds >= 2 || (maxDepth >= 2 && decisionPoints >= 2);
const level = truncated || (needsSearch && !found) ? 'unrated'
  : substantial && demanding ? 'hard'
  : !needsSearch && !globalRounds && localRounds <= 8 && boundaryFixed / board.length >= .2 ? 'easy'
  : 'medium';

• 評価保留(unrated): 探索が打ち切られた、または探索しても解が見つからなかった(通常は起こらないはずですが、コード上は防御的にチェックされています)。
• 上級(hard): 局所推論後の未確定マスが「8マス以上」かつ「盤面の30%以上」残り、かつ隣接するマスの未確定領域(幾何学的なまとまり)が最大で6マス以上あり、さらに大域推論が2巡以上か、探索の深さ2以上・分岐2回以上のどちらかを満たす。
• 初級(easy): 探索不要(needsSearchが偽)・大域推論0回・局所推論8段以下・境界だけで確定するマスの割合が20%以上。
• それ以外はすべて中級(medium)。 「残りわずかなマスに浅い仮置きが1回だけ必要」なケースはここに含まれ、上級には分類されません(README記載の通り)。

擬似コードと実装の差: remaining・largestRegionはlocalDomains(局所推論が止まった直後のスナップショット)から計算されており、大域推論や探索でさらに絞り込まれた後の状態ではありません。README自身も「局所確定は境界と全部品の形状の双方から得られる結果で、端だけを原因とする厳密な因果指標ではない」「分岐判断は探索木内の回数(人間の判断箇所ではない)」と明記しており、この記事もその限定を踏襲します。

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

前編で生成したn=4・シード"notes-example"の問題に対するanalyzeDifficultyの出力です(実行して確認)。

{
  "level": "medium",
  "boundaryFixed": 3,
  "localFixed": 10,
  "localRounds": 3,
  "globalRounds": 0,
  "needsSearch": true,
  "maxDepth": 1,
  "decisionPoints": 1,
  "remaining": 6,
  "largestRegion": 6
}

局所推論だけで16マス中10マスが確定し(localFixed: 10)、残り6マスは大域推論(0巡)では絞り切れず、探索(深さ1・分岐1回)が必要でした。substantialの条件(remaining >= 8)を満たさない(remainingは6)ためhardにはならず、needsSearchが真のためeasyの条件も満たさず、結果としてmediumになっています。しきい値の式にこの数値を当てはめれば、誰でも同じ結論を再計算できます。

スコアリング(metrics): 完成度80点+多様性20点

metrics(answer, shuffled, n, verification)が計算する「完成度」スコアは、README(「完成度の定義」節)の通り2要素の合計です。

const correct = !verification.truncated && verification.solutions.length === 1 && isSolved(answer, n);
const turns = shuffled.reduce((sum, mask, i) => {
  let k = 0; while (mask !== answer[i] && k < 4) { mask = rotate(mask); k++; } return sum + k;
}, 0);
return {
  score: correct ? Math.round(80 + variety * .2) : 0,
  deduction, variety, turns, /* ... */
};

• correctが偽ならスコアは0点。 一意解確認(前編で見たsolve、こちらはノード上限30,000)が打ち切られた・解が1つでない・isSolvedが偽、のいずれかで0点になります。
• variety(多様性、0〜100) は、完成形に使われているタイル形状(端点・直線・エルボー・T字・十字の5カテゴリ、回転違いは同一形状とみなす)のシャノンエントロピーをln(5)で正規化し100倍した値です。形状が5カテゴリすべて均等に出るほど高くなります。
• turns は、出題したshuffledからanswerまで、各マスを何回回転すれば到達するか(最大4回、届かない場合は無理に数えない仕組みではなくk<4で頭打ち)の合計です。スコアには使われず、参考値として返されます。

前編の例(n=4・シード"notes-example")ではscore: 95(variety: 75 → 80 + 75*0.2 = 95)、turns: 17でした。README自身が明記する通り、このスコアは論理的な成立度の参考値であり、「面白さ」「3分以内に解けるか」といった体験の実測値ではありません。

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

前編・この記事で見た各部品を組み合わせるのがgenerate(n, seed, target)です。

function generate(n, seed, target = 'any') {
  if (!['any','easy','medium','hard'].includes(target)) throw new Error('Unknown difficulty');
  if (![4, 5, 6].includes(n) || typeof seed !== 'string' || seed.length > 80)
    throw new Error('サイズは4〜6、シードは80文字以内で指定してください。');
  const random = rng(seed);
  for (let attempt = 1; attempt <= 500; attempt++) {
    const answer = tree(n, random), verification = solve(answer, n);
    if (verification.truncated || verification.solutions.length !== 1) continue;
    const difficulty = analyzeDifficulty(answer, n);
    if (target !== 'any' && difficulty.level !== target) continue;
    const shuffled = answer.map(mask => { const v = variants(mask); return v[Math.floor(random() * v.length)]; });
    if (isSolved(shuffled, n)) continue;
    return { n, seed, target, version: 3, answer, shuffled, attempt, difficulty, metrics: metrics(answer, shuffled, n, verification) };
  }
  throw new Error('500試行で指定条件の問題が見つかりませんでした。サイズや難易度を変更してください。');
}

重要な点は、random(乱数関数)が試行をまたいで使い回されることです。rng(seed)はgenerateの先頭で1回だけ呼ばれ、以後のtree()呼び出しやshuffledの生成は、この同じ乱数列を順番に消費していきます。そのため、

• 1回のtree()呼び出しは、n×n盤なら辺のシャッフルで2n(n-1) - 1回random()を消費します(前編でn=4なら23回と確認済み)。
• 一意解確認・難易度判定に失敗してcontinueした場合、その試行で消費した乱数は「捨てられて」次の試行に引き継がれません(次のtree()はその時点のrandomの続きから新しい木を作ります)。
• target条件に一致してshuffledを作る段階まで進んだ場合のみ、追加でn²回random()を消費します(マスごとにMath.floor(random() * v.length)を1回ずつ)。

つまり、同じシードでもtargetの指定によって消費される乱数の回数・順序が変わり、それ以降本来なら同じになるはずの部分の結果にも影響しうる、という点は、この関数を再実装する際に見落としやすい部分です。「何回目の試行で採用されたか」を示すattemptフィールドが結果に含まれているのも、この非自明な依存関係の存在を裏付けています。

500試行すべてで条件(サイズ・一意解・指定難易度)を満たす問題が見つからなければ、generateは明示的に例外を投げます。README・AGENTS.mdが明記する通り、この失敗時に「一意解が未確認の問題」や「指定と異なる難易度の問題」を代わりに返すことはありません。UI側(app.js)はこの例外を受け取ると、生成中の状態表示にエラーメッセージをそのまま出し、盤面を差し替えずに待機します。

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

• 難易度のしきい値(substantial・demandingの具体的な数値)が「人間が実際に感じる難しさ」と対応するかどうかは、README自身が「実プレイによる校正は未実施」と明記しており、この記事もそれを検証していません。コードに書かれた基準を正確に転記したにとどまります。
• スコアの多様性指標(シャノンエントロピー)が「見た目の面白さ」と相関するかどうかは検証していません。
• 500試行・ノード上限(一意解確認30,000/難易度判定5,000)という具体的な数値が、どの盤サイズ・難易度でも十分な余裕を持つかどうかの統計的な検証(たとえば6×6・上級指定で実際に何回目の試行で成功する分布か)は、この記事の範囲では行っていません。