Loop（数字で描く一筆の輪）の解き方 — 中級編: 制約だけで止まったら、1辺だけ仮に決めて矛盾を探す

まず数字と格子点の制約で絞れるところまで絞る

初級編と同じ手順(マスの数字の制約→格子点の0本/2本ルールの繰り返し)を、この5×5盤面(25マス・60辺)に適用します。出題時点の数字配置は次のとおりです。

+   +   +   +   +   +
              2   0
+   +   +   +   +   +
  1   0
+   +   +   +   +   +
  2   0   1
+   +   +   +   +   +
                  0
+   +   +   +   +   +
          0
+   +   +   +   +   +

loop/engine.jsのpropagate関数をこの数字配置に対して実行すると、60辺中49辺が確定します。図にすると次のとおりです(?が未確定の辺)。

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

残る11辺は、盤の中央やや下(行3〜5列1〜4付近)にまとまっています。位置は次のとおりです(点(行,列)表記、1始まり。「位置」列はその辺がどのマス同士、またはマスと盤の外を隔てているかを示します)。

これ以上、数字の制約と格子点のルールだけを繰り返しても、この11辺の状態はこれ以上絞れません(実際にNode.js上でさらに数巡試しましたが、状態は変化しませんでした)。これが「数字+格子点の制約だけでは解けない」局面です。

1辺を仮に「輪」と決めて波及させる

11辺のうち、点(3,4)-点(3,5)の横辺を仮に「輪」と決めてみます(この辺を選ぶのに特別な意味はなく、未確定の辺の中から1つ選んだものです)。この仮定のもとで数字の制約と格子点のルールを波及させると、次の順で矛盾に突き当たります。

1. 点(3,4)-点(3,5)の横辺=輪 と仮定する。
2. 点(3,4)には4本の辺が接続します(「点(3,3)-点(3,4)の横辺」=輪でないと確定済み・仮定した「点(3,4)-点(3,5)の横辺」=輪・「点(2,4)-点(3,4)の縦辺」=輪でないと確定済み・「点(3,4)-点(4,4)の縦辺」=未確定)。すでに輪が1本(仮定分)あるので、0本/2本ルールを満たすには残る未確定の1本(点(3,4)-点(4,4)の縦辺)が輪でなければなりません。
3. 点(3,5)にも4本の辺が接続します(仮定した「点(3,4)-点(3,5)の横辺」=輪・「点(3,5)-点(3,6)の横辺」=輪でないと確定済み・「点(2,5)-点(3,5)の縦辺」=輪と確定済み(数字のない箇所で、この盤面ではpropagateの段階ですでに輪と決まっています)・「点(3,5)-点(4,5)の縦辺」=未確定)。すでに輪が2本(仮定分と、確定済みの縦辺)あるため、残る未確定の1本(点(3,5)-点(4,5)の縦辺)は輪でないでなければなりません。
4. 点(4,5)にも4本の辺が接続します(「点(4,4)-点(4,5)の横辺」=未確定・「点(4,5)-点(4,6)の横辺」=輪でないと確定済み・手順3で輪でないと決まった「点(3,5)-点(4,5)の縦辺」・「点(4,5)-点(5,5)の縦辺」=輪でないと確定済み)。すでに確定済みの3本がすべて「輪でない」なので、残る未確定の1本(点(4,4)-点(4,5)の横辺)も輪でないでなければなりません(輪でなければ0本、輪だと1本になって0本/2本ルールに反するため)。
5. 行3列3の数字(1)を見ると、そのマスの4辺のうち「点(3,3)-点(3,4)の横辺」(輪でないと確定済み)・「点(3,3)-点(4,3)の縦辺」(輪でないと確定済み)・手順2で輪と決まった「点(3,4)-点(4,4)の縦辺」の3辺がすでに分かっており、輪になっているのは1本(手順2の縦辺)です。数字1はこれで満たされたので、残る未確定の1本(点(4,3)-点(4,4)の横辺)は輪でないと決まります。
6. 点(4,3)にも4本の辺が接続します(「点(4,2)-点(4,3)の横辺」=輪でないと確定済み・手順5で輪でないと決まった「点(4,3)-点(4,4)の横辺」・「点(3,3)-点(4,3)の縦辺」=輪でないと確定済み・「点(4,3)-点(5,3)の縦辺」=未確定)。すでに確定済みの3本がすべて「輪でない」なので、残る未確定の1本(点(4,3)-点(5,3)の縦辺)も輪でないでなければなりません。
7. ここで点(4,4)を見ると、「点(4,3)-点(4,4)の横辺」(手順5で輪でない)・「点(4,4)-点(4,5)の横辺」(手順4で輪でない)・「点(3,4)-点(4,4)の縦辺」(手順2で輪)・「点(4,4)-点(5,4)の縦辺」(輪でないと確定済み)の4本すべてがすでに判明しており、輪になっているのは手順2の1本だけです。しかし、もう決められる未確定の辺は残っていません。輪の本数が1本で確定し、これ以上足す手段もないため、0本か2本という格子点のルールに反します。

この時点で矛盾が確定します。したがって、手順1の仮定(点(3,4)-点(3,5)の横辺=輪)は誤りで、正しくは「輪でない」です。

仮定をひっくり返すと、残り全部が制約だけで決まる

「点(3,4)-点(3,5)の横辺=輪でない」で確定し直したうえで、数字と格子点の制約を再び波及させると、今度は矛盾なく残り10辺すべてが確定します(loop/engine.jsのpropagate関数に、この1辺を「輪でない」に固定した状態を渡して実行し、有効な状態のまま全60辺が確定することを確認済みです)。完成形は次のとおりです。

+---+---+---+   +   +
|           | 2   0
+   +   +   +---+   +
| 1   0         |
+   +   +   +   +   +
| 2   0   1     |
+---+   +---+---+   +
    |   |         0
+   +---+   +   +   +
          0
+   +   +   +   +   +

この輪が全数字と一致し、かつひとつながりの単純な輪であることはvalidateLoopで、E.generateが実際に持っていた答えの輪と1辺の違いもなく一致することも確認済みです。

なぜ制約の繰り返しだけでは見抜けないのか

数字の制約と格子点のルールは、どちらも「そのマス(またはその格子点)だけ」を見て判定します。点(3,4)-点(3,5)の横辺を仮に輪と決めても、決めた瞬間にはどのマス・どの格子点とも矛盾しません(だからこそ、この2つのルールだけでは60辺中49辺までしか進めませんでした)。矛盾が表面化するのは、その仮定から数手先まで波及させて、複数のマス・格子点の情報が積み重なったときです。この記事の実例では、点(3,4)から始まった連鎖が、点(3,5)・点(4,5)・行3列3の数字・点(4,3)を経て点(4,4)に戻ってくるまでの6段階を経て初めて、格子点の0本/2本ルールとの食い違いが判明しました。

手順のまとめ

1. 数字の制約と格子点のルールで絞れるところまで絞る(この実例では60辺中49辺)。
2. 残った辺の中から1本を選び、仮に「輪」(または「輪でない」)と決める。
3. 同じ制約(数字・格子点)を波及させる。
4. 波及の途中で、あるマスの数字と輪の本数が食い違う、またはある格子点で輪の本数が1本や3本以上になってしまう場合、その仮定は誤り。逆側に決め直して手順3をやり直す。
5. 矛盾が起きなければ、そのまま制約を波及させて残りを埋める。

誤りやすい判断

• 仮定した直後に矛盾が出ないからといって、その仮定が正しいとは限らない。 この記事の実例では、矛盾が判明するまでに6段階の波及が必要でした。1〜2手先で矛盾が出ないからと安心せず、波及が止まるところまで進めてください。
• どの辺を仮定に選ぶかは、この記事の手順の正しさに影響しません。 未確定の11辺のうちどれを最初に仮定しても、正しい方の状態を選べば最終的には同じ完成形にたどり着きます(この記事が点(3,4)-点(3,5)の横辺を選んだのは、単に未確定の辺の一つだったからです)。ただし、選ぶ辺によって矛盾までの手数(波及の長さ)は変わります。
• 仮定は「賭け」ではなく、UIの「一手戻す」で安全に試せる操作です。 仮に輪にしてみて矛盾が見えたら、「一手戻す」でその辺を含む変更を取り消し、逆側を試せます。

読者の検証方法

• 同じ盤面はn=5・シードnotes-loop-medium-scan-90で再現できます。
• 「点(3,4)-点(3,5)の横辺=輪」を実際に試し、上の手順どおりに行3列3の数字1が2本の輪と食い違う状態まで進むことを、自分の手元で確認できます。
• 不安な場合は、仮定を1つ試すたびに「1辺のヒント」で答え合わせしながら進めても、手順の妥当性は変わりません。

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

• 「未確定の辺が11本残ったら、1回の仮定と6段階の波及で解ける」という具体的な展開は、この記事の実例固有のものです。README・コードのいずれにも「中級相当の問題は仮定1回で解ける」という基準は明記されておらず、別の5×5盤面で同じ手数になることは保証されません。
• 上級編(その3)で扱う、1回の仮定では終わらず、仮定の上にさらに仮定を重ねる必要があるケースは扱っていません。