Color Sort（筒を注いで色分け）の生成ロジックを読む — その1: 筒の表現・乱数・配色・少なくとも1つの解の探索

筒・色・容量の表現: 色番号の配列を積んだ配列

Color Sortの盤面(tubes)は、筒ごとの配列を集めた配列です。各筒の配列は、底から積まれた色の番号(0始まりの整数)を並べたもので、配列の末尾が筒の一番上を表します。

const CAPACITY = 4; // 既定の容量(層数)。generateのcapacityオプションで4〜8に変更可能

1本の筒は「空([])」か「容量以下の枚数の色番号が積まれた配列」のどちらかです。筒の集合全体(tubes)には決まった本数の制約はなく、後述のdealTubesが「色数(numColors)+同色重複数(duplicateColors)本の色つき筒」+「空筒(emptyTubes本)」を組み立てます。

「注ぐ」という操作はpourInfoが可否と量を判定し、applyPourが実際に適用します。

function pourInfo(tubes, capacity, i, j) {
  if (i === j) return null;
  const src = tubes[i], dst = tubes[j];
  if (!src.length) return null;
  if (dst.length >= capacity) return null;
  const color = src[src.length - 1];
  if (dst.length && dst[dst.length - 1] !== color) return null;
  let amount = 0;
  for (let k = src.length - 1; k >= 0 && src[k] === color; k--) amount++;
  amount = Math.min(amount, capacity - dst.length);
  return { amount, color };
}

function applyPour(tubes, capacity, i, j) {
  const info = pourInfo(tubes, capacity, i, j);
  if (!info) return null;
  const next = tubes.map((t) => t.slice());
  for (let k = 0; k < info.amount; k++) next[j].push(next[i].pop());
  return next;
}

合法な注ぎ手の条件は次のとおりです。

• 同じ筒への注ぎ(i === j)は不可。
• 注ぎ元が空、または注ぎ先が満杯なら不可。
• 注ぎ先が空でない場合、その一番上の色が注ぎ元の一番上の色と一致していなければ不可。
• 実際に移る量(amount)は、注ぎ元の一番上から続く同色のかたまりの枚数と、注ぎ先の残り容量の小さい方。

applyPourはtubesを直接書き換えず、slice()で複製した新しい配列を返します。これは後述のsolveが「同じ状態を作らない」ように多数の枝を試す際、元の状態を破壊せずに済むための実装です。

盤面が完成しているかどうかはisSolvedが判定します。

function isSolved(tubes, capacity) {
  return tubes.every((t) => t.length === 0 || (t.length === capacity && t.every((c) => c === t[0])));
}

すべての筒が「空」か「容量ぴったり・単一色」のどちらかであれば完成です。途中まで同色が積まれているだけの筒(例: 容量4で同色が2枚だけ)は未完成として扱われます。

canon(tubes)は、盤面を筒1の内容,筒2の内容,...のような文字列に変換し、筒の並び順を無視してソートしたものです。

function canon(tubes) {
  return tubes.map((t) => t.join(',')).sort().join('|');
}

同じ色の配置でも筒の並び順が違うだけの状態は、探索上は同一局面とみなすためのシグネチャで、次章のsolveが「訪問済み局面」を管理するのに使います。

乱数: 他のOrcantus Puzzlesエンジンと同一の実装

rng(seed)は、Loop・Signalの記事で確認したrngと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個ずつ返します。同じシード文字列なら同じ数列が同じ順番で得られるという性質は他エンジンと同じですが、colorsort/engine.js・loop/engine.js・signal/engine.jsはそれぞれ独立した単一ファイルで、requireやimportによる共有はありません(コードが重複しているだけです)。

shuffle(array, random)はFisher–Yates法のその場シャッフルで、配色の乱数消費はすべてこれ経由です。

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

配色と空筒の追加: dealTubes

dealTubes(numColors, capacity, random, duplicateColors, emptyTubes)が、色つきの単位を作ってシャッフルし、筒へ配ります。

function dealTubes(numColors, capacity, random, duplicateColors = 0, emptyTubes = 2) {
  const multiplicities = new Array(numColors).fill(1);
  for (let d = 0; d < duplicateColors; d++) multiplicities[d] += 1;
  const units = [];
  for (let c = 0; c < numColors; c++) {
    for (let m = 0; m < multiplicities[c]; m++) for (let k = 0; k < capacity; k++) units.push(c);
  }
  shuffle(units, random);
  const totalFilledTubes = multiplicities.reduce((a, b) => a + b, 0);
  const tubes = [];
  for (let t = 0; t < totalFilledTubes; t++) tubes.push(units.slice(t * capacity, t * capacity + capacity));
  for (let e = 0; e < emptyTubes; e++) tubes.push([]);
  return tubes;
}

手順は次のとおりです。

1. 色0〜numColors-1それぞれについて、容量(capacity)枚分の単位を用意する。ただしduplicateColorsで指定した本数だけ、**先頭側の色(0から順にduplicateColors個)**は多重度2になり、その色だけ容量の2倍の枚数(=満杯の筒2本分)の単位が用意される。
2. 全単位を1つの配列(units)にまとめ、shuffleでランダムに並べ替える。
3. 先頭からcapacity枚ずつ切り出し、色つきの筒を作る(筒の本数はtotalFilledTubes = numColors + duplicateColors)。
4. 末尾に空の筒(emptyTubes本)を追加する。

コード中のコメントが説明するとおり、duplicateColorsは「その色の完成先が2本の筒に分かれる」ことを意味します。たとえばduplicateColors = 1なら、色0だけは容量分×2=8枚の単位が用意され、シャッフル後に別々の筒へ分かれて配られる可能性が高く、最終的にその色を2本の満杯筒へ分けて完成させることになります(1本にまとめて完成させることはできません。1本の筒の容量はcapacity枚までしか入らないためです)。

再現可能な具体例

capacity=4・色数4・重複0・空筒2・シード"sample"でdealTubesを直接呼んだ結果です。

const random = E.rng('sample');
const tubes = E.dealTubes(4, 4, random, 0, 2);
// [[3,3,2,0],[2,1,1,3],[0,2,3,1],[2,0,1,0],[],[]]

色0〜3それぞれ4枚ずつ、合計16枚の単位が4本の筒に4枚ずつ配られ、末尾に空筒2本が付いています。同じ引数で再度呼ぶと、rngが決定的であることの直接的な帰結として、完全に同じ配色が得られます(実行して確認済み)。

少なくとも1つの解があることの探索: solve

dealTubesが返す配色は、色の単位をランダムに並べ替えて切り分けただけの結果であり、そもそも注ぎ手で解けるかどうかは保証されていません。これを確認するのがsolve(initialTubes, capacity, nodeLimit = 20000)です。

function solve(initialTubes, capacity, nodeLimit = 20000) {
  const start = initialTubes.map((t) => t.slice());
  if (isSolved(start, capacity)) return { solved: true, moves: [], nodes: 0, truncated: false };
  const visited = new Set([canon(start)]);
  let nodes = 0, truncated = false;
  function dfs(tubes, path) {
    if (truncated) return null;
    if (++nodes > nodeLimit) { truncated = true; return null; }
    const n = tubes.length;
    const moves = [];
    for (let i = 0; i < n; i++) {
      const src = tubes[i];
      if (!src.length) continue;
      const isSrcUniform = src.every((c) => c === src[0]);
      if (isSrcUniform && src.length === capacity) continue; // a full single-color tube is already settled
      for (let j = 0; j < n; j++) {
        if (i === j) continue;
        const dst = tubes[j];
        if (isSrcUniform && dst.length === 0) continue; // relocating a uniform pile to an empty tube never helps
        const info = pourInfo(tubes, capacity, i, j);
        if (info) moves.push([i, j, info.amount]);
      }
    }
    moves.sort((a, b) => b[2] - a[2]);
    for (const [i, j] of moves) {
      const next = applyPour(tubes, capacity, i, j);
      const sig = canon(next);
      if (visited.has(sig)) continue;
      visited.add(sig);
      if (isSolved(next, capacity)) return [...path, [i, j]];
      const result = dfs(next, [...path, [i, j]]);
      if (result) return result;
      if (truncated) return null;
    }
    return null;
  }
  const moves = dfs(start, []);
  if (moves) return { solved: true, moves, nodes, truncated: false };
  return { solved: false, moves: [], nodes, truncated };
}

要点は次のとおりです。

• 深さ優先探索(DFS)で、最初に見つかった解をそのまま返す。 LoopやNumber Placeの一意解判定のように「2つ目の解が見つかったら打ち切る」処理は無く、そもそも複数解を探すコードがありません。これはsolveが「少なくとも1つの解があるか」だけを確認する関数であり、一意解判定の機能を持たないことを意味します。
• visited(canonのSet)による同一局面の再訪問防止。 筒の並び順を無視した局面シグネチャがすでに訪問済みなら、その手は探索しません。
• 2つの枝刈りヒューリスティック。 ①すでに完成している単色満杯筒からは注がない(isSrcUniform && src.length === capacityのときcontinue)。②単色のかたまりを空筒へ移すだけの手は無視する(移し替えても盤面の「解けやすさ」は変わらず、探索を無駄に広げるだけのため)。どちらも探索の枝を減らすための最適化であり、解の存在・不在の判定結果そのものには影響しません(除外される手はどれも、実行しても状況を改善しない手であることがコード中のコメントで説明されています)。
• 手の順序を移動量の降順にソート。 同色のかたまりを大きく動かす手を先に試すヒューリスティックです。解が見つかる速さには影響しますが、解の有無の判定結果は変えません。
• nodeLimit(既定20,000)を超えたらtruncated = trueにして打ち切る。 この場合、solved: falseが返っても「解が存在しない」ことの証明にはなりません。探索打ち切りと「解なし確認」はコード上明確に区別されており(truncatedフィールドが別に立つ)、次章(その2)で見るgenerateはこの2つを別々のカウンタで数えています。

擬似コードと実装の差: 上の説明は一般化した言い方ですが、実装ではvisitedへの追加は「新しい局面を作った直後」に行われ、生成した子局面がすでに訪問済みならその時点でdfsを呼ばずに次の手へ進みます(教科書的なDFSでは子ノードに入ってから訪問済みチェックをすることが多いですが、ここでは子ノードに入る前にシグネチャで弾いています)。結果として、visitedに登録される局面の集合と実際にdfsが再帰的に呼ばれる局面の集合は必ずしも一致しません(前者の方が広い)が、探索結果(解が見つかるかどうか)には影響しません。

再現可能な具体例

前章のdealTubes(4, 4, 'sample', 0, 2)の結果に対してsolveを実行した結果です。

const check = E.solve(tubes, 4, 20000);
// { solved: true, nodes: 16, truncated: false, moves: [...16手...] }

16ノードの探索で16手の解が見つかりました(この局面ではたまたま見つかった最初の解の手数と探索ノード数が一致していますが、これは偶然であり、一般に成り立つ関係ではありません)。先頭5手は[[0,4],[0,5],[1,0],[2,1],[0,2]]([注ぎ元, 注ぎ先])で、同じtubes・同じnodeLimitで再度呼べば完全に同じ結果が再現します(実行して確認済み)。

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

• dealTubesがシャッフルする単位の配置の分布の一様性(可能なすべての配色が等確率で出るか)は検証していません。Fisher–Yates自体は理論上一様分布のシャッフルですが、その後段のsolveによる採否フィルタ(後編で扱うgenerateのループ)を経た後の採用された配色の分布までは調べていません。
• solveが返す解が、最短手数の解であるという保証はありません(移動量降順のソートは発見を速める・特定の手を優先するヒューリスティックであり、最短性を証明するものではありません)。
• 生成ループ全体・却下条件・難易度プリセット・隠し色モードの表示上の扱い・失敗時の扱いは扱っていません。これらはその2で扱います。