Loopの解き方上級編

Note

本文中の「初級・中級・上級」は、この3本の記事シリーズが読者に想定する読む順番であり、Loopアプリ自身が表示する難度(盤面サイズに基づくeasy/medium/hard)とは別の基準です。Loopの出題画面には「盤面サイズ（難易度の保証ではありません）」と明記されており、アプリ側の難度表示はサイズだけで決まる簡易な目安です。この記事でいう「上級」は、筆者が実際に解いて要した手順の複雑さ(仮置きの入れ子の深さ)を基準にしています。

結論。制約の伝播を繰り返しても未確定の辺が固まって残り、そこに1回仮置きしてさらに伝播させても、まだ未確定の辺が残ることがある。その場合は、1回目の仮置きを維持したまま、残った未確定の辺の中から2回目の仮置きを選んで重ねる。それでも決まらなければ3回目、4回目と重ねていく。この実例では、最大3段(15手順分の探索)重ねたところで、7通りの組み合わせすべてが矛盾し、残る1通りだけが正解でした。

出題と、伝播だけで確定する範囲

この盤面(6×6・36マス、辺は横辺(n+1)×n = 7×6 = 42本・縦辺n×(n+1) = 6×7 = 42本の合計84本)は次の数字で出題されます(.は空欄)。

0  2  .  .  .  0
.  .  .  0  .  .
.  .  .  .  0  .
2  .  .  .  0  .
2  .  .  .  0  .
0  .  2  2  1  .

初級編・中級編と同じ手順(セルの数字ルール→頂点の0/2ルールの繰り返し)を適用すると、84本中63本(75%)が確定し、21本が未確定のまま残ります(loop/engine.jsのpropagateをNode.jsで実行して確認)。未確定の21本は、盤の中央からやや右下寄りに、次のように固まっています(?が未確定)。

+   +   +---+---+   +   +
  0   2 | .   . | .   0
+   +---+   +   +---+   +
  . | .   .   0   . | .
+---+   + ? +   +   +---+
| .   . ? . ? .   0   . |
+   +   + ? +   +   +   +
| 2   . ? . ? .   0   . |
+---+   + ? +   +   +   +
  2 | . ? . ? .   0   . |
+   +---+ ? + ? +   + ? +
  0   . ? 2 ? 2 ? 1 ? . ?
+   +   + ? + ? + ? + ? +

未確定の21本は、盤の中ほど(行3〜行6・列3〜4の境目)を縦に貫く横辺4本(点(3,3)-点(3,4)・点(4,3)-点(4,4)・点(5,3)-点(5,4)・点(6,3)-点(6,4))と、盤の一番下の行(行6の下端、頂点の7行目)に集まる横辺・縦辺、それらをつなぐ縦辺で構成されています。これ以上、伝播だけを繰り返しても、この21本の候補はこれ以上絞れません。

1回の仮置きでは終わらない

中級編と同じように、未確定の辺の中から1本を選んで仮置きしてみます。伝播が次に絞り込む先(候補が2つしかない辺のうち、最初に処理される辺)は、縦に並んだ4本の横辺の一番上、点(3,3)-点(3,4)の横辺です。

ここで「点(3,3)-点(3,4)の横辺=輪でない」と仮置きして伝播させると、点(3,3)-点(4,3)の縦辺と点(3,4)-点(4,4)の縦辺の2本が新たに輪でないと確定しますが、それでもまだ大部分が未確定のまま残ります。 ここが中級編との違いです。中級編では1回の仮置きで残り全部が確定しましたが、この盤面では確定しません。

そこで、この仮置きを維持したまま、次に候補が絞られた辺(点(4,3)-点(4,4)の横辺)についてさらに仮置きを重ねます。それでもまだ決まらなければ、3本目(点(5,3)-点(5,4)の横辺)にも仮置きを重ねます。このように、1つの仮置きの中でさらに仮置きを重ねる操作を「入れ子の仮置き」と呼びます。

実際に検証した探索木(全8通り)

loop/engine.jsのsolve関数を実際にNode.js上で実行すると、この盤面は15回の探索ステップ(ノード)で唯一解に到達することを確認しました(nodes: 15, solutions: 1, truncated: false)。探索が実際にたどった、3段の仮置きの組み合わせ(縦に並んだ4本の横辺のうち上から3本を仮置きし、4本目は伝播で自動的に決まるか、そこで矛盾が確定します)は次の8通りで、そのうち7通りが矛盾、1通りだけが正解でした。

① 点(3,3)-点(3,4)=輪でない
  ├─② 点(4,3)-点(4,4)=輪でない
  │   ├─③ 点(5,3)-点(5,4)=輪でない → 矛盾(伝播で破綻)
  │   └─③ 点(5,3)-点(5,4)=輪　　　 → 矛盾(伝播で破綻・詳細は次節)
  └─② 点(4,3)-点(4,4)=輪
      ├─③ 点(5,3)-点(5,4)=輪でない → 矛盾(伝播で破綻)
      └─③ 点(5,3)-点(5,4)=輪　　　 → 矛盾(伝播で破綻)
① 点(3,3)-点(3,4)=輪
  ├─② 点(4,3)-点(4,4)=輪でない
  │   ├─③ 点(5,3)-点(5,4)=輪でない → 矛盾(伝播で破綻)
  │   └─③ 点(5,3)-点(5,4)=輪　　　 → 矛盾(伝播で破綻)
  └─② 点(4,3)-点(4,4)=輪 → 矛盾(この時点で伝播が破綻。③まで進まず確定)

正解にたどり着く組み合わせは、①輪でない・②輪でない・③輪でない、と3本連続で「輪でない」と置いたうえで、4本目(点(6,3)-点(6,4))だけが「輪」になる組み合わせです。この4本目は仮置きの対象ではなく、①②③を確定させたあとの伝播で自動的に決まります(候補が1つに絞られるため、探索は分岐しません)。

矛盾の詳細(1本を実際にたどる)

7通りの矛盾のうち、**①輪でない・②輪でない・③輪(点(5,3)-点(5,4)=輪)**の組み合わせを例に、実際にどこで矛盾が起きるかを最後までたどります。

仮定: 点(3,3)-点(3,4)の横辺=輪でない
点(3,3)の0/2ルール(他の2辺は確定済みでともに輪でない) → 点(3,3)-点(4,3)の縦辺=輪でない
点(3,4)の0/2ルール(他の2辺は確定済みでともに輪でない) → 点(3,4)-点(4,4)の縦辺=輪でない
仮定: 点(4,3)-点(4,4)の横辺=輪でない
点(4,3)の0/2ルール(他の2辺は確定済みでともに輪でない、手順2の1本も輪でない) → 点(4,3)-点(5,3)の縦辺=輪でない
点(4,4)の0/2ルール(他の2辺は確定済みでともに輪でない、手順3の1本も輪でない) → 点(4,4)-点(5,4)の縦辺=輪でない
仮定: 点(5,3)-点(5,4)の横辺=輪
点(5,3)の0/2ルール(他の1辺は確定済みで輪でない、手順5の1本も輪でない、手順7の1本が輪) → 点(5,3)-点(6,3)の縦辺=輪
点(5,4)の0/2ルール(他の1辺は確定済みで輪でない、手順6の1本も輪でない、手順7の1本が輪) → 点(5,4)-点(6,4)の縦辺=輪
点(6,3)の0/2ルール(既に確定済みの1辺が輪、手順8の1本も輪で計2本) → 残る2本(点(6,3)-点(6,4)の横辺・点(6,3)-点(7,3)の縦辺)はどちらも輪でない
行6列3の数字(2)を見ると、4辺のうち2本(手順10の2本)がすでに輪でないと決まっており、残る未確定の2本(点(7,3)-点(7,4)の横辺・点(6,4)-点(7,4)の縦辺)で数字2を満たす必要があるため、両方とも輪と決まります
点(7,3)は盤の下端の頂点で、接続する辺は3本だけです。そのうち2本(手順の途中で確定済みの1本・手順11で輪と決まった1本)を合わせると、すでに3本すべてが判明しており、輪になっているのは1本だけです。頂点は「0本」か「2本」しか許されず、未確定の辺も残っていないため、ここで矛盾が確定します。

この12手順は、loop/engine.jsのvertexEdges・cellEdgesが返す実際の隣接関係と、伝播後に確定していた基礎値をNode.js上で突き合わせて検証した内容です。残る6通りの矛盾についても、同じsolve関数を実際に実行して「伝播の途中で候補が0件になる辺が生じる」ことは確認していますが、この記事で手順を最後まで書き下したのはこの1通りのみです(他の6通りは検証済みだが、本文での逐次narrationは省略)。

誤りやすい判断

1回仮置きして矛盾が出ないからといって、それだけで確定とは限らない。 中級編までの感覚のまま「1回仮置きして伝播が止まらなければ正解」と判断すると、この実例のように未確定の辺がまだ残っている状態を見落とします。伝播後に未確定の辺が0本になっているかを必ず確認してください。
仮置きを重ねる順番に決まりはありませんが、候補が最も少ない辺から選ぶと探索が短くなります。 この実例でsolveが実際にたどった順番も、常にその時点で候補が最も少ない辺を選ぶ方式(MRV)でした。
入れ子の仮置きは、内側の仮置きが矛盾しても、外側の仮置きが自動的に正しいとは限りません。 上の探索木のとおり、外側(①輪でない)の下でも、内側(②③)の組み合わせ4通りのうち3通りが矛盾しました。外側の仮置きが正しいと分かるのは、内側の組み合わせを1つずつ確認し尽くして初めて言えることです。

読者の検証方法

同じ盤面はn=6・シードnotes-loop-hard-scan-71で再現できます。
手元でloop/engine.jsのsolve(clues, 6, 20000)を実行すると、nodes: 15・solutions.length: 1が得られることを確認できます。
アプリ上でも、伝播で決まる63本を先に埋めたあと、点(3,3)-点(3,4)の横辺を「輪でない」に固定して1手ずつ進めると、本文の手順2・3と同じ2本が確定することを確認できます。

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

探索木の8通りのうち、詳細な矛盾の手順を最後まで書き下したのは1通りだけです。残り6通りはsolve関数の実行結果(伝播が候補0件で破綻すること)として確認していますが、本文と同じ形式の手動derivationは行っていません。
「仮置きを3段重ねる必要がある」という深さは、この実例(6×6・このシード)で実際に観測された値です。Loopのn=6盤面すべてがこの深さを要するとは限りません(README・loop/rating.jsのとおり、Loopの難度表示自体が盤面サイズのみに基づく簡易な目安であり、実際に必要な仮置きの深さを保証するものではありません)。
上級編はこの記事で完結します。より深い入れ子(4段以上)を要する盤面については、今回検証した範囲では確認していません。

この結果が言っていないこと

検証はloop/engine.js・loop/app.js(エンジンv1、2026-09-29時点)を対象にしています。将来の版で表示・判定基準が変わる可能性があります。
本文の手順の「順番」は、筆者がvertexEdges・cellEdgesの関係を手作業で追った順序であり、propagate関数内部の実際のループ順序と一致するとは限りません(得られる結論・最終的な確定値は一致することをpropagateの実行結果と突き合わせて確認しています)。
「入れ子の仮置き」という用語はこの記事独自の説明用語であり、Loopアプリ内やREADMEに登場する用語ではありません。