【解法】Subset Counting

　Subset Counting は「特定の領域に各数字が最大何個入るか？」に着目した解法です。
　この「最大個数」がカギとなって、話が進んでいきます。
　ただ、数字ごとに最大個数を数えなければならず、非常に手間がかかってしまうのが玉にキズ。
　「こういう解き方もあるんだな〜」くらいに軽く流してください😓
　（難易度：★★★★★）

１．入れられる数字の最大個数がカギ

　まずは、この解法の核となる「最大個数」について話をしましょう。

図 1-1

　まずは、ごく普通の部分図を１つ。

　図1-1、青色７マスを見てみましょう。
　その７マスにある候補数字は全部で５種類ですね。
　２, ４, ５, ７, ９の５種類。
　この数字達で青色マスは埋め尽くされていくわけですが、もちろん、今のところどの数字が何個入るかはわかりません。

　そこで、ちょいと視点を変えてみる。
　こんなことを考えてみます。

それぞれの数字、青色７マスに最大何個まで入れられるんだろうか？

　各数字の個数の上限、それぞれ調べてみましょう。

図 1-2

　各数字の最大個数は次の通りです。

  • 数字２は最大１個まで入る。
  • 数字４は最大１個まで入る。
  • 数字５は最大２個まで入る。
  • 数字７は最大１個まで入る。
  • 数字９は最大３個まで入る。

　候補数字２は１ブロックにしかないから、最大１個。
　候補数字４はヨコ１列にしかないから、最大１個。
　候補数字５は１ブロックとタテ１列にあるから、最大２個。
　候補数字７は１ブロックにしかないから、最大１個。
　候補数字９は３つのブロックにあり、３個の数字９を配置する方法があるから、最大３個。
　というわけで、上記の通りです。

　これらの最大個数を合計してみましょう。
　1＋1＋2＋1＋3＝８個ですね。
　青色マスよりちょっぴり多かった。

　「青色７マスに対して最大個数の合計が８」という状況は何もおかしくありません。
　「その８個のうち７個が実際に青色マスに入ることになる」というだけですもんね。
　最大個数の合計が７以上なら不合理は起きません。

　では、もし最大個数の合計が７未満だったとしたらどうなるか？
　それを探っていきましょう。

図 1-3

　図1-1 から候補数字９をいくつか消して、図1-3 のようにしちゃいました。
　この青色７マスに対して、各数字が最大何個まで入るかをそれぞれ調べてみましょう。

  • 数字２は最大１個まで入る。
  • 数字４は最大１個まで入る。
  • 数字５は最大２個まで入る。
  • 数字７は最大１個まで入る。
  • 数字９は最大１個まで入る。

　最大個数を合計すると、1＋1＋2＋1＋1＝６個になりました。
　今度は合計値がマス数を下回りましたね。

　実は、この状況になると悲劇が起こるんです。

図 1-4

　どういう悲劇なのか？
　それは……、

数字６個では青色７マスを埋め尽くせない！

　これはもぅ明らかですね。
　７マス埋めたいのに数字が全然足りてないんだもの😵
　なんとか数字６個を入れたとしても 図1-4 のようになっちゃうし。

　当然ですが「最大個数の合計は６」なのだから、数字は６個より多くできません。
　破綻からはどうしても逃れられないんです。

　最大個数の合計が少なすぎてはダメなんですね。
　というわけで、結論が１つできました。

  • 空きマスからなる領域をＡとする。
    Ａに入り得る各数字の最大個数を求め、それらを合計する。その合計値はＡのマス数以上でなければならない。

　最大個数の合計は必ずマス数以上である。
　これ大事！

　解法 Subset Counting は、「最大個数の合計が減少する」ことがカギとなって機能します。
　その仕組みは次セクションで説明しましょう。

２．どういう解法？

図 2-1

　では、解法 Subset Counting を解説していきましょう。
　面倒なので前セクションの 図1-1 を流用します。
　手抜きとか言わないで😅

　図2-1 の青色７マスを見てみましょう。
　この７マスに入れられる各数字の最大個数は次の通りでした。

  • 数字２は最大１個入る。
  • 数字４は最大１個入る。
  • 数字５は最大２個入る。
  • 数字７は最大１個入る。
  • 数字９は最大３個入る。

　最大個数の合計は８ですね。
　７以上（マス数以上）であることも思い出しておきましょう。

　実は、この状況から結論が１つ生まれます。

図 2-2

　その結論とは……、

  • 最大個数の合計をマス数未満に減少させてしまうマスがある。そのマスに当該数字が入らなくなる。

　図2-2 では、赤色×印マスが該当します。
　実は、このマスに数字９が入らなくなるんです。

　なぜこういう結論になるんでしょう？
　それは、赤色マスに数字９が入ると最大個数の合計が大きく減少してしまい、破綻が起こるからです。
　それを解説しましょう。

図 2-3

　今、赤色マスに数字９が入ったと仮定しましょう。
　その上で、あらためて各数字が最大何個入るか調べてみます。

【数字２】
最大１個。
【数字４】
最大１個。
【数字５】
最大２個。
【数字７】
最大１個。
【数字９】
最大３個 → 最大１個。

　なんと、数字９は最大１個に減ってしまった！
　候補数字９がタテ１列にしか存在しなくなったからですね。

　数字９の最大個数が２減った。
　つまり、最大個数の合計は８から６に減少したわけです。

図 2-4

　マスは７個なのに、最大個数の合計はそれよりも少なくなった。
　破綻が起きてしまったんです😵
　無理やり数字を入れたとしても、図2-4 みたいになっちゃう。
　やっぱり、高々６個の数字で７マス埋めるのは叶わぬ夢である。

　というわけで、「赤色マスに数字９が入る」という仮定は間違いだとわかった。
　そのマスに数字９を入れてはいけないんですね。
　図2-2 の結論通りになりましたね😊

　この解法の大事な点を１つ。

　マス数を境界線として、それを踏み越えることが必要です。
　合計がただ減少しただけでは解法 Subset Counting は使えない。
　この点、注意が必要です。

３．実際に使ってみよう！

　実は、既存の解法のうちいくつかは Subset Counting で解くことも可能です。
　そこで、WXYZ-Wing のページにある実例に使ってみます。

図 3-1

　図3-1、青色４マスを見てみましょう。
　候補数字は１, ３, ６, ７の全４種類。
　これらの数字が青色４マスに最大何個入るか数えてみましょう。

  • 数字１は最大２個入る。
  • 数字３は最大１個入る。
  • 数字６は最大１個入る。
  • 数字７は最大１個入る。

　４マスに対して、最大個数の合計は 2＋1＋1＋1＝5 です。
　マス数より１多い。
　ということは、数字１に着目して合計を一挙に２減少できるようなマスが見つかれば良さそうかな？
　では、Subset Counting を使ってみましょう！

図 3-2

　結論はこうなります。

  • 赤色２マスから候補数字１を除去できる。

　理由を簡単に説明しましょう。
　もし赤色マスのどちらかに数字１が入ると仮定すると、青色マスに入る数字１の最大個数が変化しますね。

【数字１】
最大２個 → 最大０個。
【数字３】
最大１個。
【数字６】
最大１個。
【数字７】
最大１個。

　合計は 0＋1＋1＋1＝3。
　マス数を下回って破綻が起きました。
　したがって、上記の結論に至るわけですね。

４．同数にこそ真価あり !?

　ここからは余談です。
　「Subset Counting って、案外パワフルな解法じゃね？」という話を１つ。

　今まで、最大個数の合計がマス数より１多いパターンを挙げてきました。
　でも、最大個数の合計がマス数に等しいパターンも当然あります。
　実は、既存の解法の中にそういうパターンがあるんです。

　例えば、皆さんご存じのｎ国同盟。これも Subset Counting の一種と言えます。
　Sue De Coq も同様です。
　ちょいとそのあたりの話をしてみましょうか。

図 4-1

　まずは３国同盟（Naked Triple）を１つ。
　図4-1 は３国同盟のページで実例として挙げた盤面です。
　青色３マスを見てみましょう。
　各数字の入り得る最大個数は簡単にわかりますね。

  • 数字２は最大１個入る。
  • 数字４は最大１個入る。
  • 数字９は最大１個入る。

　最大個数の合計は３で、マス数と同じです。
　ということは、数字２, ４, ９どれでもいいから最大個数を０にすれば破綻が起きる。Subset Counting で解決できる。
　そういうマスが左上ブロックにたくさん見つかりそうですね。

図 4-2

　というわけで、こういう結論になるんです。

  • 左上ブロックで候補数字２, ４, ９の大量除去が起こる。

　注目すべきところは、除去の多さです。
　なんと、５個もある！
　今までは１〜２個しか除去できなかったのに、格段に増えました。

　こういうふうに、合計とマス数が等しいパターンだと大きな除去力を発揮することがあるんです。
　「最大個数を１減らせばいい」というハードルはそこそこ低い。
　少なくとも、２以上減らすよりは明らかに低い。

　……とは言っても、ｎ国同盟をわざわざ Subset Counting で解釈するメリットは薄い。
　だけど、Sue De Coq のような高難度の解法だと Subset Counting の方が理解しやすいかもしれません。

図 4-3

　図4-3 は Sue De Coq のページで実例として挙げた盤面です。
　青色５マスに注目して、各数字の最大個数を調べると……、

  • 数字３は最大１個入る。
  • 数字４は最大１個入る。
  • 数字６は最大１個入る。
  • 数字７は最大１個入る。
  • 数字８は最大１個入る。

　候補数字４, ６はタテ１列にある。
　候補数字３, ８は１ブロックにある。
　候補数字７はタテ１列または１ブロックにある。
　だから、どれも最大１個です。

　合計は５で、マス数と同じ。
　ということは、最大個数を０に減らすような候補数字を除去できるわけですね。
　その結果、８個の候補数字に×がつきました。

　解法 Sue De Coq の解説ページを見ればわかりますが、場合分けを使っていて理屈が非常にまどろっこしいんです。
　でも、図4-3 の方法だと、各々の数字に対して「最大１個を０個にする」だけを考えればいい。
　理解の難易度はだいぶ軽くなるんですね。

　他には、XY-Wing, XYZ-Wing, ALS-XZ, Aligned Pair Exclusion なども同じ理屈で解釈可能です。
　実戦で Subset Counting を使う機会はほとんどありませんが、この『最大個数を１減らそう理論』は汎用性の高い概念ではないかなぁと個人的には思っています。

図 4-4

　最後は究極のパターンをご紹介。
　SK Loop です。
　青色16マスを調べると……、

  • 数字１は最大１個入る。
  • 数字２は最大２個入る。
  • 数字３は最大１個入る。
  • 数字４は最大２個入る。
  • 数字５は最大２個入る。
  • 数字６は最大２個入る。
  • 数字７は最大２個入る。
  • 数字８は最大２個入る。
  • 数字９は最大２個入る。

　合計は16で、マス数と同じ。
　『最大個数を１減らそう理論』が使えますね！
　というわけで、結果はもぅもぅ盤面バツだらけ😅（図4-4）

参考・参照

更新履歴