Note
この実例のパラメータ(12色・容量5・空筒2)は、Color Sort本体の「超上級」設定(colorsort/app.jsのLEVEL_PRESETS.superhard)と同じ組み合わせです。この記事の見出しは「上級編」ですが、これはあくまでこの解説記事シリーズの3段階における3番目という意味で、アプリの4段階(初級・中級・上級・超上級)の「上級」とは対応していません(アプリの「上級」は同色を2本の筒に分けるduplicateColorsという別の要素を含みますが、この記事の実例には含まれません。duplicateColors自体については本文末尾の「この記事が確認していないこと」で触れます)。アプリの難度表示は色数・容量・空き筒数などパラメータの組み合わせにすぎず、個々の盤面が「どこで難しい判断を要求するか」までは判定していません。
結論。色数が増えても、詰みへ向かう分岐点の性質そのものは中級編と同じ(合法で、見た目には対称な2択のうち片方だけが唯一詰みへ向かう)。 ただし、色数が増えるぶん、分岐が現れるまでに必要な手数(この実例では12手)も、正しい側を証明するのに要る探索の深さ(566ノード)も大きくなることを、実際の生成盤面とsolve()の実行結果で確認しました。
出題と、序盤12手(どの順で進めても詰まない範囲)
numColors=12・容量5・空筒2で生成した盤面は、色つきの筒12本+空の筒2本、合計14本です。出題時点の内容です(下から積まれた順、括弧内は既定で隠れる下2層。色はA〜Lの12種)。
| 筒 | 内容(下→上) |
|---|---|
| 1 | (A, G), F, A, L |
| 2 | (B, D), E, B, C |
| 3 | (L, A), C, H, L |
| 4 | (D, H), I, I, C |
| 5 | (I, H), F, C, F |
| 6 | (K, J), B, L, K |
| 7 | (D, K), K, J, E |
| 8 | (G, C), H, B, A |
| 9 | (D, H), F, J, I |
| 10 | (L, D), E, J, G |
| 11 | (G, J), E, B, G |
| 12 | (F, K), I, E, A |
| 13 | 空 |
| 14 | 空 |
この盤面について、「注ぎ先の一番上の色が一致する、または空の筒へ」という合法な注ぎを1手ずつ選んでいくと、最初の12手のあいだは、どの合法な選択肢を選んでも最後まで解ける状態が保たれることを確認しました(各手の時点で存在するすべての合法手について、注いだ後の盤面にE.solveを実行し、詰みが確定するもの(探索打ち切りではなく)が1つも無いことを、12手目まで1手ずつ確認済みです)。つまり、この範囲では中級編のような「見分けが必要な分岐」はまだ現れません。実際にengineの解探索が選んだ順で12手進めると、次のようになります。
| 手 | 注ぎ | 移る色 |
|---|---|---|
| 1 | 筒1→筒13 | L |
| 2 | 筒1→筒14 | A |
| 3 | 筒3→筒13 | L |
| 4 | 筒5→筒1 | F |
| 5 | 筒2→筒5 | C |
| 6 | 筒8→筒14 | A |
| 7 | 筒2→筒8 | B |
| 8 | 筒7→筒2 | E |
| 9 | 筒12→筒14 | A |
| 10 | 筒2→筒12 | E |
| 11 | 筒12→筒2 | Eを2枚 |
| 12 | 筒9→筒12 | I |
12手を終えた時点の盤面です。
| 筒 | 内容(下→上) |
|---|---|
| 1 | A, G, F, F |
| 2 | B, D, E, E, E |
| 3 | L, A, C, H |
| 4 | D, H, I, I, C |
| 5 | I, H, F, C, C |
| 6 | K, J, B, L, K |
| 7 | D, K, K, J |
| 8 | G, C, H, B, B |
| 9 | D, H, F, J |
| 10 | L, D, E, J, G |
| 11 | G, J, E, B, G |
| 12 | F, K, I, I |
| 13 | L, L |
| 14 | A, A, A |
一見対称な2択: 筒7と筒9のどちらへJを寄せるか
この状態で、筒7(D,K,K,J)と筒9(D,H,F,J)は、どちらも一番上がJです。合流させる合法な注ぎは2通りあります。
- 候補X: 筒7→筒9 — 筒7のJ(1枚)を筒9へ。結果、筒7は
D,K,K(3枚、Kが露出)、筒9はD,H,F,J,J(5枚・満杯)。 - 候補Y: 筒9→筒7 — 筒9のJ(1枚)を筒7へ。結果、筒9は
D,H,F(3枚)、筒7はD,K,K,J,J(5枚・満杯)。
どちらも「Jが一番上同士で合流し、どちらか一方が満杯になる」という構造上は対称な操作です。しかし、候補Yだけが唯一詰みへ向かうことをE.solveで確認しました(nodes: 21の探索で、打ち切りではなく解なしと確定)。候補Xは引き続き解けますが、それを証明する探索には566ノードを要しており、中級編の実例(打ち切りでない判定に28ノード)より探索の負荷がはっきり大きくなっています。
| 候補 | 注ぎ | 結果 | 解けるか |
|---|---|---|---|
| X | 筒7→筒9 | 筒7=D,K,K・筒9=D,H,F,J,J(満杯) |
解ける(566ノードで確認) |
| Y | 筒9→筒7 | 筒9=D,H,F・筒7=D,K,K,J,J(満杯) |
解けない(21ノードで解なし確定) |
候補Yを選んでも、この時点ではまだ合法な注ぎが残っており(E.hasAnyMoveはtrue)、手詰まりの警告は出ません。この1手は筒を完成させていないためE.canUndoもtrueのままで、実際にアプリで「1手のヒント」を押せば、中級編と同じ現在の状態からは解けません。一手戻すか最初からをお試しください。という応答が返ることを確認済みです。
この記事での読み方: どちらを満杯にするかで、埋もれる色が変わる
E.solveは理由を説明しないため、以下は盤面を見た筆者の解釈です。候補X・候補Yのどちらでも、一方の筒が満杯(容量5・混色)になり、満杯になった筒は、自分の一番上から注ぎ出さない限り、以後何も受け取れません。違いは、満杯にする筒がどちらの色を下敷きにするかです。
- 候補Y(不可)は、K(色10)を2枚持つ筒7を満杯にします。筒7の中身は
D,K,K,J,Jとなり、Kの2枚はJの2枚の下に埋もれます。 - 候補X(可)は、Kを持たない筒9を満杯にします。筒9の中身は
D,H,F,J,Jとなり、埋もれるのはH・F(1枚ずつ)で、Kはどこにも埋もれません。
この盤面の他の場所にはKを含む筒がもう無く(筒6のK,J,B,L,Kが残る唯一のK供給源)、Kを2枚とも1本にまとめるには、筒7のKへいずれ手を付ける必要があります。候補Yでその筒7自体を満杯にしてしまうと、Kを掘り出す前に、まず自分で積み増したJを2枚とも別の場所へ逃がす必要が生じ、この盤面の残り13本の空き具合ではそれをやり切れなかった、というのがこの記事の読み方です。ここでも中級編と同様、「色の合流そのもの」が悪いのではなく、「どちらの筒を満杯にするか」という選択が結果を左右しています。
候補Xを選んで最後まで解く
候補X(筒7→筒9)を選んだ場合、E.solveはここからさらに61手の解を返し(このノードでの探索は566ノード)、序盤12手と合わせて全74手でこの盤面を解ききります。この記事では61手すべてを表に書き下すことはしませんが、E.pourGameで74手すべてを最初から適用し、次を確認しました。
- 途中、詰みが発生する箇所は無い(全74手が最後まで適用できる)。
- 最終盤面で
E.isSolved(色が筒ごとに分かれている)・E.isFullyRevealed(隠れていた24個の「？」がすべて露出済み)・E.isCleared(両方を満たす)のすべてがtrue。 - 最終盤面は次のとおりです(12色それぞれが1本の筒にまとまり、空筒2本が残ります)。
| 筒 | 内容 |
|---|---|
| 1 | A×5 |
| 2 | B×5 |
| 3 | J×5 |
| 4 | 空 |
| 5 | C×5 |
| 6 | K×5 |
| 7 | 空 |
| 8 | E×5 |
| 9 | D×5 |
| 10 | L×5 |
| 11 | G×5 |
| 12 | F×5 |
| 13 | I×5 |
| 14 | H×5 |
誤りやすい判断
- 「対称に見える2択」でも、対称なのは操作の形だけで、結果まで対称とは限らない。 候補X・候補Yはどちらも「Jが一番上同士で合流し、片方が満杯になる」という同じ形の操作でしたが、結果はまったく非対称でした。
- 色数が増えるほど、詰みを見分けるための確認コストも増える。 中級編の実例(5色)では28ノードで判定できましたが、この実例(12色)では正しい側の証明に566ノードを要しました。アプリの「1手のヒント」も内部で同じ探索を行っており(既定の探索上限は4万ノード)、色数の多い盤面ほど判定に時間がかかることがあります。
- 満杯(容量ぴったり)にした筒は、自分の一番上から注ぎ出すまで何も受け取れない。 この記事の実例では、どちらの候補を選んでも必ずどちらかの筒が満杯になりましたが、満杯にする筒に、まだ掘り出していない別の色(この実例ではK)を抱え込ませるかどうかが明暗を分けました。
読者の検証方法
- 同じ盤面は、色数12・容量5・空筒2・シード
notes-colorsort-superhard-3で再現できます。E.generate({ numColors: 12, capacity: 5, duplicateColors: 0, emptyTubes: 2, seed: 'notes-colorsort-superhard-3' })を実行すれば、この記事と同じtubes配列が得られます。 - 序盤12手を適用した状態(
state after 12 forced movesの表)から、候補Y(筒9→筒7、0始まり添字では[8, 6])をE.applyPourで適用し、その結果にE.solve(next, 5, 40000)を呼ぶと{ solved: false, truncated: false }が返ることを、誰でも手元で確認できます。 - 候補X(
[6, 8])を適用した結果に対して同じE.solveを呼ぶと{ solved: true, nodes: 566, ... }が返り、そこからさらに61手で完成に至ることも確認できます。
この記事が確認していないこと
- 序盤12手のあいだ「どの合法な選択肢を選んでも解ける」と確認したのは、この実例(このシード)固有の観察です。色数の多い盤面全般で、序盤にこのような分岐が現れないと主張するものではありません。
- 候補X・候補Yの結果を分けた理由(「なぜ候補Yだけが詰みへ向かうのか」)は、盤面を見た筆者の解釈であり、
colorsort/engine.jsが明示している理由ではありません。 - Color Sort本体の「上級」プリセット(
duplicateColorsで同色を2本の筒に分ける設定)は、この記事の実例には含まれていません。同色が2本の完成筒に分かれる盤面での判断は扱っておらず、別の記事の対象です(colorsort/app.jsのコード中コメントは、この設定が「行き詰まりにくさの目安となる、解を保つ手の割合」を超上級より一貫して高くすることを、6シードのサンプル比較で示していますが、これは全シードでの一般的な証明ではないと同コメント自身が述べています)。 - 全74手のうち、序盤12手と分岐直後の2択(候補X・Y)は本文で検証・提示しましたが、残り61手すべてを表として書き下すことはしていません(実行してisClearedに到達することは確認済みです)。
この結果が言っていないこと
- 検証は
colorsort/engine.js・colorsort/app.js(いずれも記事執筆時点、生成結果のversion: 2で確認)を対象にしています。将来の版で表示・判定基準が変わる可能性があります。 - 「候補X」「候補Y」という呼び方、および「なぜ詰みへ向かうか」の説明はこの記事独自の解釈用の表記です。アプリ本体の画面上にはこのような候補の一覧表示・理由の説明はありません。