Pattern（行・列の数字で塗るお絵かきロジック）の解き方 — 上級編: 仮定の上にさらに仮定を重ね、矛盾で1段ずつ引き返す

まず候補列挙で絞れるところまで絞る

初級編・中級編と同じ手順(行・列の候補列挙の繰り返し)を、この10×10盤面(100マス)に適用します。出題時点の数字配置は次のとおりです。

• 行の数字(行1〜行10): 「3 1」「1 2 2」「1 1 3」「2 3」「3 1」「1 4」「2 6」「2 3 1」「1 2 2」「2 1 3」
• 列の数字(列1〜列10): 「2 3」「1 1 2 1」「1 1 1」「3 2」「2 1 1」「3 2」「1 3」「2 5」「6 2」「3 3 1」

pattern/engine.jsのpropagate関数をこの数字配置に対して実行すると、100マス中63マスが確定し、37マスが未確定のまま残ります。これ以上、候補列挙だけを繰り返しても状態は変化しません(Node.js上で確認済み)。中級編の16マスより多く未確定が残っており、候補列挙だけでは全く歯が立たない局面です。

仮定その1: 行1列1=空白 → すぐには矛盾しない

未確定の37マスのうち、盤面の左上から順に見て最初に見つかる行1列1(行1の数字「3 1」の一部)を仮に決めてみます。

1. 行1列1=空白と仮定して波及させると、候補列挙は矛盾なく進み、未確定マスが37個から36個に1つ減っただけで止まります。この時点ではまだ正誤が決まりません。

中級編で扱った例と違い、1マスの仮定だけでは決着がつかない局面です。ここで諦めず、この仮定を維持したまま、さらにもう1マスを仮定します。

仮定その2: (行1列1=空白のまま)行1列2=空白 → まだ矛盾しない

2. 残った未確定マスのうち、やはり左上から順に最初に見つかる行1列2を、行1列1=空白の仮定を維持したまま、さらに空白と仮定します。波及させると、今度は未確定マスが36個から32個に減りますが、まだ矛盾は起きません。

仮定その3: (行1・2列=空白のまま)行1列3=空白/塗り → どちらも矛盾

3. さらに残った未確定マスの中から行1列3を選び、2通り(空白・塗り)をそれぞれ試します。
   • 行1列3=空白と仮定して波及させると、ある行または列の数字を満たせる候補が1つも残らなくなり、矛盾します。
   • 行1列3=塗りと仮定して波及させても、同様に候補が1つも残らなくなり、矛盾します。

行1列3は空白でも塗りでも矛盾するため、その1段上の仮定(行1列2=空白)自体が誤りだったことになります。

4. では行1列2=塗り(行1列1=空白は維持したまま)を試すとどうなるか。これも波及させると、ある行または列で候補が1つも残らなくなり、矛盾します。

行1列2は空白でも塗りでも(行1列1=空白を前提にする限り)矛盾するため、最も外側の仮定(行1列1=空白)自体が誤りだったことになります。

最初の仮定を逆にすると、追加の仮定なしで即座に全マスが確定する

5. 行1列1=塗り(仮定その1の逆)にやり直して候補列挙を波及させると、追加の仮定を一切必要とせず、残り99マスすべてが一気に確定します(pattern/engine.jsのpropagate関数に、このマスを「塗り」に固定した状態を渡して実行し、有効な状態のまま全100マスが確定することを確認済みです)。

この探索の流れをまとめると、次のような木になります(E.solveが実際にたどった分岐と一致します)。

行1列1=空白 と仮定
  行1列2=空白 と仮定
    行1列3=空白 と仮定 → 矛盾
    行1列3=塗り と仮定 → 矛盾
  行1列2=塗り と仮定 → 矛盾
  （したがって行1列1=空白 自体が誤り）
行1列1=塗り と仮定 → 追加の仮定なしで全マス確定

完成形は次のとおりです(#が塗り、.が空白)。

# # # . . # . . . .
# . . . . # # . # #
. # . . . # . # # #
. . . # # . . # # #
. . # # # . . . # .
. . . # . . # # # #
. # # . # # # # # #
# # . . . # # # . #
# . . # # . . # # .
# # . # . . . # # #

この塗り分けが全数字と一致することはcluesFor関数で、E.generateが実際に持っていた答えと1マスの違いもなく一致することも確認済みです。

なぜ2段・3段も仮定を重ねる必要があるのか

中級編の例では、1マスの仮定から数段の波及で矛盾(またはその不在)が判明しました。この上級編の例では、行1列1=空白という仮定だけでは、盤面のどの行・列の数字とも矛盾しないまま止まってしまいます。矛盾が存在すること自体は確かでも、それを見つけるにはもう1段、さらにもう1段と仮定を重ねて情報を積み増す必要がありました。これはLoopの上級編で見た「仮定の上にさらに仮定を重ねる」状況と同じ構造で、Patternでもバックトラック探索(pattern/engine.jsのsolve関数)が同じ理由で必要になることが分かります。

手順のまとめ

1. 行・列の候補列挙で絞れるところまで絞る(この実例では100マス中63マス)。
2. 残ったマスから1つを仮定し、波及させる。矛盾すれば逆側に決め直す。矛盾しないが全マスも確定しない場合は、その仮定を維持したまま、次の手順に進む。
3. さらに残ったマスから1つを選び、仮定を重ねて波及させる。矛盾しない限り、この手順を繰り返す(仮定を積み重ねる)。
4. ある段で、その時点のマスの両方の値(空白・塗り)がどちらも矛盾したら、その1段上の仮定自体が誤り。1段戻って逆側を試す。
5. 最終的にどの段でも両方の値が矛盾したら、最も外側の仮定自体が誤り。最初の仮定を逆にしてやり直す。

誤りやすい判断

• 内側の仮定が両方とも矛盾したからといって、盤面全体が解なしとは限らない。 この記事の実例では、行1列2の2択が(行1列1=空白を前提にする限り)両方矛盾しましたが、これは「行1列1=空白」という前提が誤っていただけで、盤面自体には唯一解があります(E.generateが一意解であることを保証済みの盤面のため)。矛盾が起きたら、常に「どの仮定まで巻き戻すべきか」を1段ずつ確認してください。
• 仮定を積み重ねる順番によって、必要な段数は変わります。 この記事は左上から順にマスを選びましたが(solve関数が実際にたどる順序と同じ)、別の順番でマスを選んでも最終的な答えは変わりません。ただし矛盾までの段数・手数は選び方次第で増減します。
• 手元で試すときは、UIの「一手戻す」を段数ぶん使う必要があります。 3段重ねた仮定を撤回するには3回の「一手戻す」が要ります。今どの段まで仮定を積んでいるか、自分で数を把握しておく必要があります(Pattern本体には仮定の階層を表示する機能はありません)。

読者の検証方法

• 同じ盤面はn=10・シードnotes-pattern-scan-10-137で再現できます。
• 「行1列1=空白」から「行1列2=空白」「行1列3=空白/塗り」の順に実際に試し、上の手順どおりにどちらも矛盾する状態まで進むことを、自分の手元で確認できます。
• 不安な場合は、仮定を1段試すたびに「1マスのヒント」で答え合わせしながら進めても、手順の妥当性は変わりません。ただし、ヒントを使うと「解答補助あり」の扱いになります。

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

• 「37マス未確定・3段の仮定で矛盾判明」という具体的な展開は、この記事の実例固有のものです。README・コードのいずれにも「上級相当の問題は仮定3段で解ける」という基準は明記されておらず、別の10×10盤面で同じ段数になることは保証されません(この記事を書く過程で調べた他の10×10盤面では、1段の仮定で済むものから、9段の仮定が必要なものまで幅がありました)。
• 仮定するマスの選び方(この記事は左上から順)を変えた場合に、矛盾までの段数がどう変わるかは体系的に検証していません。