Color Sort（筒を注いで色分け）の生成ロジックを読む — その2: 生成ループ・難易度プリセット・隠し色モード・失敗時の扱い

生成ループ(generate): 却下条件と再試行

前編で見たdealTubes・solveを組み合わせるのがgenerate(options)です。

function generate(options) {
  const {
    numColors, seed, capacity = CAPACITY, duplicateColors = 0, emptyTubes = 2, nodeLimit = 20000,
  } = options || {};
  if (!Number.isInteger(numColors) || numColors < 4 || numColors > 20 || typeof seed !== 'string' || seed.length > 80) {
    throw new Error('色数は4〜20、シードは80文字以内で指定してください。');
  }
  if (!Number.isInteger(capacity) || capacity < 4 || capacity > 8) {
    throw new Error('容量（層数）は4〜8で指定してください。');
  }
  if (!Number.isInteger(duplicateColors) || duplicateColors < 0 || duplicateColors > numColors) {
    throw new Error('同色を分ける数は0〜色数の範囲で指定してください。');
  }
  if (!Number.isInteger(emptyTubes) || emptyTubes < 1 || emptyTubes > 4) {
    throw new Error('空の筒の数は1〜4で指定してください。');
  }
  const random = rng(seed);
  let truncatedCount = 0, unsolvableCount = 0;
  for (let attempt = 1; attempt <= 500; attempt++) {
    const tubes = dealTubes(numColors, capacity, random, duplicateColors, emptyTubes);
    if (isSolved(tubes, capacity)) continue;
    if (tubes.some((t) => t.length >= 2 && t[0] === t[1])) continue;
    const check = solve(tubes, capacity, nodeLimit);
    if (check.truncated) { truncatedCount++; continue; }
    if (!check.solved) { unsolvableCount++; continue; }
    return {
      numColors, capacity, duplicateColors, emptyTubes, numTubes: tubes.length, seed, version: 2,
      tubes, attempt, solutionLength: check.moves.length, nodes: check.nodes,
    };
  }
  throw new Error(
    `500試行で解法が確認できる問題が見つかりませんでした（探索打ち切り ${truncatedCount} 回・解なし確認 ${unsolvableCount} 回）。色数やシードを変更してください。`
  );
}

入力検証(色数4〜20、容量4〜8、同色重複数0〜色数、空筒数1〜4、シード80文字以内)を通ったあと、rng(seed)はループの外で1回だけ呼ばれ、以後の全試行はこの同じ乱数列の続きをdealTubesで消費していきます(却下された試行で消費した乱数が巻き戻ることはありません)。各試行は次の条件で却下(continue)され、次の試行に進みます。

1. 配色した時点ですでに完成している(isSolved)。 各色が最初から1本の筒に丸ごと収まっている場合で、パズルとして成立しないため却下します。
2. いずれかの筒で、底から2枚目までが同色(t[0] === t[1])。 これは前編で見た「注ぎは常に同色のかたまり全体を動かす」という性質と関係します。もし底2枚が同色のまま埋もれた場合、その2枚を引き離す注ぎ手は存在せず、深い方の1枚を露出させる手段が永久に無いため却下します。この条件は次章の隠し色モードと直結しており、後で詳しく扱います。
3. solveが探索打ち切り(truncated: true)。 truncatedCountをインクリメントして却下。「解なしと確認できたわけではない」ケースです。
4. solveが解なしと確認(solved: falseかつtruncated: false)。 unsolvableCountをインクリメントして却下。

これら4条件のどれにも当てはまらなければ、その配色を採用して{ tubes, attempt, solutionLength, nodes, ... }を返します。500試行すべてで採用できる配色が見つからなければ、truncatedCount・unsolvableCountの内訳付きで例外を投げます(後述)。

再現可能な具体例(通常成功するケース)

numColors=5・既定パラメータ・シード"notes-example"でgenerateを呼んだ結果です。

const p = E.generate({ numColors: 5, seed: 'notes-example' });
// { numColors: 5, capacity: 4, duplicateColors: 0, emptyTubes: 2, numTubes: 7,
//   seed: 'notes-example', version: 2, attempt: 2, solutionLength: 20, nodes: 20,
//   tubes: [[2,1,0,3],[2,3,1,4],[1,4,4,0],[0,3,3,0],[1,2,4,2],[],[]] }

attempt: 2が示すとおり、1回目の配色は却下されています。rng('notes-example')から同じ手順でdealTubesを2回呼んで確認すると、1回目の配色[[4,1,1,3],[0,3,1,2],[2,3,0,0],[2,4,1,0],[4,4,2,3],[],[]]は5番目の筒[4,4,2,3]の底2枚が同色(4,4)であるため却下条件2に該当し、2回目の配色が採用されていることを実際に確認できました。同じnumColors・同じseedでgenerateを再度呼ぶと、attemptを含むすべてのフィールドが1回目と完全一致します(実行して確認済み。tests.cjsのseed replay is deterministicテストでも同様の性質が検証されています)。

難易度: エンジン内蔵の評価関数ではなく、UI側のパラメータの組み合わせ

colorsort/engine.jsのエクスポート一覧(CAPACITY, rng, shuffle, pourInfo, applyPour, isSolved, canon, solve, dealTubes, generate, createGame, pourGame, undoGame, canUndo, revealedIds, isHidden, isFullyRevealed, isCleared, findRevealMove, hasAnyMove, isDeadlocked)には、SignalにあるanalyzeDifficultyのような難易度判定関数がありません。Color Sortの「初級・中級・上級・超上級」は、colorsort/app.jsが定義するパラメータのプリセットです。

const LEVEL_PRESETS = {
  easy: { numColors: 5, capacity: 4, duplicateColors: 0, emptyTubes: 2 },
  medium: { numColors: 8, capacity: 5, duplicateColors: 0, emptyTubes: 2 },
  hard: { numColors: 8, capacity: 5, duplicateColors: 4, emptyTubes: 3 },
  superhard: { numColors: 12, capacity: 5, duplicateColors: 0, emptyTubes: 2 },
};

色数・容量・同色重複数・空筒数の組み合わせを変えているだけで、generate自身はこれらを「難易度」として特別扱いしません(単なるgenerateの引数です)。colorsort/rating.js側にも、この4段階を得点計算のベンチマーク(1手あたりの目安秒数)に対応づけるテーブルがあります。

const LEVEL_BY_KEY = {
  '4:0': 'easy', '5:0': 'easy',
  '6:0': 'medium', '8:0': 'medium',
  '7:0': 'hard', '10:5': 'hard', '8:4': 'hard',
  '12:0': 'superhard',
};
const SEC_PER_MOVE = { easy: 6, medium: 9, hard: 13, superhard: 16 };

rating.jsのコード中コメントは、この対応づけが「生成時に確認済みの最短手数(solutionLength)」を基準にした暫定値であり、「実プレイによる校正は未実施」であると明記しています。つまりこの秒数基準は理論値であって、実際のプレイヤーの所要時間データから調整された数値ではありません。

app.jsのコメントは、上級(hard)プリセットが超上級(superhard)より「行き詰まりにくい」ことの根拠として、colorsort/tests.cjsのsafeMoveStatsという検証を挙げています。これは、正解手順の最初の数手それぞれについて、その時点で打てる合法手のうち「打っても(限られた探索ノード数の範囲で)なお解けることが確認できる手」の割合を、6つのシードで平均して比較するテストです。実行して確認したところ、このテスト(the new hard preset keeps more solve-preserving moves available...)を含むcolorsort/tests.cjsは成功しました。ただし、これはあらかじめ選ばれた6シード・探索ノード上限8,000という条件下でのサンプル比較であり、「上級のほうが常に・どんなシードでも行き詰まりにくい」ことの一般的な証明ではありません(テスト自体のコメントも、ノード上限による過小評価が「差を過大評価する方向には働かない」とだけ述べています)。

隠し色モードの表示上の扱い

Color Sortでは、各筒の底から2枚までが最初は?として隠され、プレイヤーが注いでその位置を露出させるまで色が分かりません。この仕組みはgenerateが返すtubes(色の配列)そのものには触れず、その上に被せるゲーム状態としてcreateGame以降の関数群が管理します。

function createGame(puzzle, capacity) {
  const tubes = puzzle.tubes.map((t) => t.slice());
  let nextId = 0;
  const idTubes = tubes.map((t) => t.map(() => nextId++));
  const hiddenIds = new Set();
  idTubes.forEach((t) => { for (let k = 0; k < Math.min(2, t.length); k++) hiddenIds.add(t[k]); });
  return {
    tubes, idTubes, hiddenIds, everRevealed: new Set(), history: [], moves: 0, selected: -1, assisted: false, message: null,
  };
}

各単位に固有のid(idTubes)を振り、各筒の底からMath.min(2, 筒の長さ)枚分のidをhiddenIdsに登録します(容量4の筒なら底2枚、それより短い筒ではその筒の全枚数)。hiddenIdsは色の値ではなくidの集合であり、色そのものを隠しているわけではありません。isHiddenは、対象のidがhiddenIdsに含まれ、かつまだ一度も露出していない場合にのみtrueを返します。

function isHidden(state, showAll, tubeIndex, slotIndex) {
  if (showAll) return false;
  const id = state.idTubes[tubeIndex][slotIndex];
  if (!state.hiddenIds.has(id)) return false;
  return !revealedIds(state).has(id);
}

一度でも一番上に来て露出したidはeverRevealedに記録され、この集合は取り消し(undo)しても縮みません。つまり「一度見た色はプレイヤーの記憶から消えない」という扱いです。

function pourGame(state, capacity, i, j) {
  const info = pourInfo(state.tubes, capacity, i, j);
  if (!info) return { ok: false };
  const nextTubes = applyPour(state.tubes, capacity, i, j);
  const nextIds = state.idTubes.map((t) => t.slice());
  for (let k = 0; k < info.amount; k++) nextIds[j].push(nextIds[i].pop());
  const exposedNow = topExposedHidden(nextIds, state.hiddenIds);
  const everRevealed = new Set(state.everRevealed);
  for (const id of exposedNow) everRevealed.add(id);
  const completedNew = isFullMono(nextTubes[j], capacity);
  const history = [...state.history, {
    tubes: state.tubes.map((t) => t.slice()), idTubes: state.idTubes.map((t) => t.slice()), locked: completedNew,
  }];
  return {
    ok: true,
    state: { ...state, tubes: nextTubes, idTubes: nextIds, everRevealed, history, moves: state.moves + 1, selected: -1, message: null },
  };
}

注ぎの結果、隠れたidが新たに筒の一番上へ来ていればeverRevealedに加えます。また、この注ぎで筒が完成した(isFullMono)場合、その履歴エントリにlocked: trueを付けます。canUndoは直前の履歴がlockedならfalseを返すため、筒を完成させた手は取り消せません。コード中のコメントによれば、これは「完成筒の中身を覗いてから元に戻す」抜け道(取り消せば完成前の状態に戻りつつ、色を見たという情報だけ持ち帰れてしまう)を防ぐためで、単に色を露出させただけの手(完成を伴わない)には取り消し禁止を課していません。

完成条件(isCleared)は、色が揃っている(isSolved)だけでなく、隠れていた色がすべて一度は露出している(isFullyRevealed)ことも要求します。

function isFullyRevealed(state) {
  const revealed = revealedIds(state);
  for (const id of state.hiddenIds) if (!revealed.has(id)) return false;
  return true;
}
function isCleared(state, capacity) {
  return isSolved(state.tubes, capacity) && isFullyRevealed(state);
}

色を揃えるだけの操作では、隠れた?の位置(たとえば注がれずに残った筒の底)が最後まで露出しないまま終わる場合があります。そのためfindRevealMoveという補助関数が用意されており、色が揃った後でも未露出のidが残っていれば、それを露出させる合法手を探します。

function findRevealMove(state, capacity) {
  const revealed = revealedIds(state);
  const pending = new Set([...state.hiddenIds].filter((id) => !revealed.has(id)));
  if (!pending.size) return null;
  for (let i = 0; i < state.idTubes.length; i++) {
    if (!state.idTubes[i].some((id) => pending.has(id))) continue;
    for (let j = 0; j < state.tubes.length; j++) {
      if (j === i) continue;
      if (pourInfo(state.tubes, capacity, i, j)) return [i, j];
    }
  }
  return null;
}

このコード中のコメントは「パズルは解けた状態でも必ず少なくとも1本の完全に空の筒を保つため、このような手は常に見つかる」と説明しています。この前提はgenerateの入力検証(emptyTubesは1〜4の範囲で必須)から導かれます。色が揃った状態では、numColors + duplicateColors本の筒がそれぞれ単色で満杯になり、残りのemptyTubes本(1本以上)が空のままになるため、未露出の色が残っている筒からその空筒へ注ぐ手が必ず存在します。この記事では、この前提が実際にすべてのケースで成り立つことを網羅的には検証していませんが、tests.cjsのisDeadlocked flags an unclearable, unfinished board distinctly from a merely-unfinished oneというテストが、generateで作った問題を解いたあとfindRevealMoveをくり返し呼んで実際に完全露出まで到達できることを1シード分確認しており、実行して成功を確認しました。

そして、この隠し色モードが成立する前提こそが、前章で見たgenerateの却下条件2(底から2枚目までが同色の筒を却下)の理由です。もし底2枚が同色のまま配色されていたら、hiddenIdsはその2枚とも隠しますが、同色の2枚は注ぎでは決して分離できないため(注ぎは常に同色のかたまり全体を動かす)、深い方の1枚は永久に一番上に来ず、isFullyRevealedがtrueにならない=isClearedに到達できない問題になってしまいます。generateはこれを生成の時点で機械的に排除しています。

最後に、hasAnyMove・isDeadlockedは、「完成していないのに、どの筒からどの筒へも合法な注ぎ手が無い」手詰まり状態を検出します。

function isDeadlocked(state, capacity) {
  return !isCleared(state, capacity) && !hasAnyMove(state.tubes, capacity);
}

この判定は現在の盤面だけを見ており、「その手詰まりが本当に取り消し不能かどうか」(取り消せば脱出できる可能性)までは考慮しません。 実際、app.jsの画面表示は手詰まり時に「一手戻すか、最初からやり直してください」と案内しており、取り消しで解消できる可能性を前提にした文言になっています。

失敗時の扱い

前章で見たとおり、500試行すべてで採用できる配色が見つからなければgenerateは例外を投げます。実際に発生させて確認するため、既定パラメータの範囲を超えた極端な設定(色数20・容量8・空筒1本。UIの難易度プリセットには存在しない組み合わせ)で試したところ、次のとおり500試行すべてが却下されました。

E.generate({ numColors: 20, seed: 'unsolvable-probe-2', capacity: 8, emptyTubes: 1 });
// Error: 500試行で解法が確認できる問題が見つかりませんでした
//        （探索打ち切り 1 回・解なし確認 189 回）。色数やシードを変更してください。

（残る310回は却下条件1・2で早期に却下されており、truncatedCount・unsolvableCountには計上されません。）これはgenerate単体をNode.jsから直接呼び出した結果で、UIの難易度プリセット(LEVEL_PRESETS)が使うパラメータの組み合わせでは発生を確認していません。

この例外はcolorsort/worker.jsがtry/catchで受け止め、{ id, error: error.message }としてメインスレッドへpostMessageするだけです。

importScripts('engine.js');
self.onmessage = ({ data }) => {
  try { self.postMessage({ id: data.id, puzzle: ColorSortEngine.generate(data.options) }); }
  catch (error) { self.postMessage({ id: data.id, error: error.message }); }
};

app.js側のreceiveはこのerrorフィールドを見て、画面に準備できませんでした：${data.error}とそのまま表示します。Web Workerが使えない環境(location.protocol === 'file:'など)では、workerが生成されずgenerateをメインスレッドで直接呼び出す経路(app.js内のelse setTimeout(...))を通りますが、try/catchで同じerror.messageを拾って同じreceiveに渡す構造は変わりません。いずれの経路でも、探索打ち切りや解なし確認を「合格」扱いにして代わりのパズルを返すことはなく、生成できなかった事実をそのままプレイヤーへ伝えます。

再現条件と限界

この連載で示した再現例はすべて、記事執筆時点のcolorsort/engine.js(version: 2)を、Node.jsからrequireして直接呼び出した結果です。同じバージョン・同じ入力(色数・容量・同色重複数・空筒数・シード)であれば、generate・dealTubes・solveのいずれも決定的に同じ結果を返すことを、tests.cjsのseed replay is deterministic・difficulty preset seed replay is deterministic for every levelの各テストと、この記事中の個別の再現実行の両方で確認しています。

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

• generateが全パラメータ範囲(色数4〜20・容量4〜8・同色重複数0〜色数・空筒数1〜4)のどの組み合わせで、何回目の試行までに成功する確率が高いか・失敗しうるかという分布は調べていません。この記事で示した失敗例(色数20・容量8・空筒1)は、UIの難易度プリセットが使わない極端な組み合わせを意図的に選んだものです。
• 難易度プリセットのSEC_PER_MOVE(1手あたりの目安秒数)が実際のプレイ体験にどれだけ近いかは検証していません。rating.jsのコード中コメント自身が「実プレイによる校正は未実施の暫定値」と明記しています。
• safeMoveStatsによるhard/superhardの「行き詰まりにくさ」比較は、6シード・探索ノード上限8,000というサンプルでの比較であり、全シード・無制限の探索での一般的な証明ではありません。
• findRevealMoveが常に手を見つけられるという前提(解けた状態で必ず空筒が残る)は、コードの構造と1シードでのテスト実行から妥当と判断していますが、全パラメータ範囲での網羅的な検証は行っていません。