ChromaOracle は BFS（幅優先探索)というアルゴリズムを使用して、あらゆるカラーソートパズルの最短可能解を見つけます。求解器は推測やヒューリスティックに頼らず、最短のものから順にすべての可能な手のシーケンスを体系的に探索し、パズルを解くものを見つけるまで続けます。これにより、返される解が可能な限り少ない手数を使用することが保証されます。仕組みを、好奇心旺盛なプレイヤーと技術志向の読者の両方に向けて説明します。
パズルを探索問題として捉える
すべてのカラーソートパズル——ウォーターソート、ボールソート、その他のバリアントを問わず——は探索問題として記述できます。任意の瞬間のパズル盤面は「状態」です:すべての試験管にわたる特定の色配置です。すべての有効な注ぎや手は、ある状態を別の状態に変換します。パズルを解くとは、開始状態を目標状態——各試験管が一色だけか空である状態——に変換する手のシーケンスを見つけることを意味します。
地図のように想像してください。各交差点が状態です。交差点間の各道路が手です。開始状態は今いる場所です。目標状態が目的地です。求解器の仕事は最短ルートを見つけることです。
幅優先探索とは?
幅優先探索は、この状態の地図を非常に特定の順序で探索する方法です:開始から 1 手離れたすべての状態を最初に確認し、次に 2 手離れた状態を、次に 3 手、というように。あらゆる方向に均等に層ごとに広がります。
この層状のアプローチが最適性を保証します。BFS はどの 6 手解を探索する前にもすべての 5 手解を探索するため、目標状態に最初に到達したとき、必然的に最短パスを見つけたことになります。それ以上短いパスは見逃されているはずがありません——すべての短い可能性はすでに確認されているからです。
プロセスはこう動きます:
- 初期盤面状態から始める。
- その状態からすべての有効な手を生成する。各手が新しい盤面状態を生成する。
- これらの新しい状態のいずれかが解決済み状態かを確認する。そうなら、手のシーケンスを返す。
- そうでなければ、すべての新しい状態をキューに追加し、キューの次の状態でステップ 2 から繰り返す。
- 目標が見つかるか、すべての到達可能な状態が探索されるまで続ける。
キューが空になっても解が見つからない場合、パズルは解決不可能です——求解器はそれを即座に報告します。
状態空間の表現
BFS が効率的に動作するためには、求解器が各盤面状態をコンパクトに表現し、すでに訪問した状態を検出する方法が必要です。ChromaOracle は各試験管を色のスタックとして、盤面全体をこれらのスタックの集合として表現します。
同じ状態を 2 度探索しないように——時間とメモリを浪費する——求解器は各状態の正規キーを生成します。このキーは、試験管の順序に関係なく同一の配置を同じ状態として扱う、盤面の正規化された文字列表現です。2 つの盤面が同じ内容の試験管を持っているが順序が違うだけなら、それらは同じキーを生成し、重複として認識されます。
この重複排除は重要です。それなしでは、求解器は同じ位置を何百万回も再訪し、実用的でないほど遅くなります。それがあれば、求解器は各ユニーク状態を一度だけ処理します。
なぜ BFS は最短解を保証するのか
保証は探索の順序から来ます。BFS は厳密に開始からの距離(手数で測定)で状態を処理します。距離 N のすべての状態は、距離 N+1 のいずれの状態よりも前に処理されます。したがって、求解器が目標状態に最初に到達したとき、長さ N のパスを介して到達したことになり、長さ N 未満のパスは存在しません——すべての短いパスはすでに完全に探索されているからです。
これはアルゴリズムの数学的特性であり、ヒューリスティックや近似ではありません。BFS が返す解は証明可能に最適です。
BFS と DFS
ChromaOracle は代替アルゴリズムとして DFS（深さ優先探索)もサポートしています。DFS は異なる動作をします:層ごとに探索する代わりに、可能な限り深く一つのパスをたどってからバックトラックします。
トレードオフは:
- BFS は最短解を見つけますが、現在の深度レベルのすべての状態を同時に保存する必要があるため、より多くのメモリを使用します。
- DFS は多くの場合、解をより早く見つけ、より少ないメモリを使用しますが、解は最短ではない可能性があります。出会った最初の有効なパスを返し、必要よりもはるかに長い可能性があります。
ほとんどのプレイヤーにとって、BFS が正しい選択です——最少の手数が欲しいからです。DFS は、ただ何らかの解を素早く欲しい場合や、パズルが BFS でメモリ不足になるほど大きい場合に役立ちます。
ミステリーモードの仕組み
ChromaOracle の最も特徴的な機能の一つは、隠れた色や未知の色を含むパズル用に設計されたミステリーモードです。多くのパズルゲームでは、一部の試験管のスロットに色の代わりに疑問符が表示され、その層が試験管の最上部になったときにのみ実際の色が明らかになります。
ChromaOracle は順列分析を通じてこれを処理します:
- 求解器が未知としてマークされたすべての位置を識別します。
- パズルのルールと一致する——各色が正しい回数現れる必要がある——可能な色割り当てをすべて生成します。
- BFS を使用して結果として生じる各パズルを独立して解きます。
- すべての解集合を分析し、隠れた色が何であっても安全な手を見つけます。
これは「共通プレフィックス」を見つけることと呼ばれます——すべての可能な色割り当ての解の最初に現れる最長の手のシーケンスです。これらの手は未知が何を明らかにしても正しいことが保証されています。
このアプローチは、不確実性の問題を網羅的分析の問題に変えます。求解器は推測する代わりに、すべての可能性を考慮し、どの手にリスクがないかを伝えます。
パフォーマンスと実用的な制限
カラーソートパズルの状態空間は、試験管と色の数とともに指数関数的に増加します。5 色の単純なパズルには数千の到達可能な状態があるかもしれません。12 色の複雑なパズルには数百万あるかもしれません。
ChromaOracle はブラウザで TypeScript を使用して完全に実行されます。ほとんどのパズル——約 10 色まで——では、BFS は 1 秒以内に完了します。より大きなパズルは数秒かかることがあります。極めて大きい構成はブラウザのメモリ制限を超える可能性があり、その時点で DFS がより良い選択肢になります。
求解器は純粋な計算で、ネットワーク呼び出しはありません。パズルデータはデバイスから出ることはなく、解法速度はデバイスの処理能力にのみ依存します。
エンジンアーキテクチャ
技術的な実装に興味がある読者向けに、ChromaOracle の求解器エンジンは焦点を絞ったモジュールに整理されています:
- Container（コンテナ) —— 単一の試験管を色のスタックとして表現し、push、pop、トップ色クエリを処理します。
- Collection（コレクション) —— 完全な盤面を表現し、現在の状態からすべての有効な手を生成し、重複排除のための正規キーを生成します。
- Search（探索) —— BFS と DFS の両方を実装し、キューまたはスタックと訪問済み状態のセットを管理します。
- Strategy（戦略) —— マルチソリューション分析を調整し、すべての解を見つけてミステリーモードの共通プレフィックスを計算します。
- Validation（検証) —— 解法が始まる前にパズル構成が良くできているかを確認します。
エンジンはフレームワーク依存がありません。純粋な TypeScript で、独立してテスト可能で、任意の JavaScript ランタイムに移植可能です。
よくある質問
ChromaOracle が特定のパズルでより時間がかかるのはなぜ?
解法時間は状態空間のサイズに依存し、それは色、試験管、空きスロットの数で決まります。色が多く空の試験管が少ないほど、探索する可能な状態が増えます。空の試験管が 1 つの 12 色のパズルは、空の試験管が 3 つの 4 色のパズルよりもはるかに大きな状態空間を持ちます。
求解器は解を見つけられないことがありますか?
解が存在する場合、BFS は常にそれを見つけます。BFS が解を見つけずに完了する場合、パズルは数学的に解決不可能です——どの有効な手のシーケンスも目標状態に到達できません。ChromaOracle はこれを明確に報告するため、パズルが単に難しいのではなく、不可能であることを知ることができます。
BFS の解は常に最良ですか?
はい。BFS は手数の点で最短解を保証します。BFS が返す解よりも少ない手数の有効な解は存在しません。これはアルゴリズムの数学的特性です。
ミステリーモードはどの手が安全か知る方法は?
ミステリーモードは隠れた色のすべての可能な割り当てに対してパズルを解き、すべての解を比較します。手は、すべての可能性の最適解に現れる場合にのみ安全とマークされます。これは、隠れた色が何であっても、その手が正しいことを意味します。