【解法】Subset Counting

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

1.入れられる数字の最大個数がカギ

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

図 1-1

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

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

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

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

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

図 1-2

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

  • 数字2は最大1個まで入る。
  • 数字4は最大1個まで入る。
  • 数字5は最大2個まで入る。
  • 数字7は最大1個まで入る。
  • 数字9は最大3個まで入る。

 候補数字2は1ブロックにしかないから、最大1個。
 候補数字4はヨコ1列にしかないから、最大1個。
 候補数字5は1ブロックとタテ1列にあるから、最大2個。
 候補数字7は1ブロックにしかないから、最大1個。
 候補数字9は3つのブロックにあり、3個の数字9を配置する方法があるから、最大3個。
 というわけで、上記の通りです。

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

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

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

図 1-3

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

  • 数字2は最大1個まで入る。
  • 数字4は最大1個まで入る。
  • 数字5は最大2個まで入る。
  • 数字7は最大1個まで入る。
  • 数字9は最大1個まで入る。

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

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

図 1-4

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

数字6個では青色7マスを埋め尽くせない!

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

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

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

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

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

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

2.どういう解法?

図 2-1

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

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

  • 数字2は最大1個入る。
  • 数字4は最大1個入る。
  • 数字5は最大2個入る。
  • 数字7は最大1個入る。
  • 数字9は最大3個入る。

 最大個数の合計は8ですね。
 7以上(マス数以上)であることも思い出しておきましょう。

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

図 2-2

 その結論とは……、

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

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

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

図 2-3

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

【数字2】
最大1個。
【数字4】
最大1個。
【数字5】
最大2個。
【数字7】
最大1個。
【数字9】
最大3個 → 最大1個。

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

 数字9の最大個数が2減った。
 つまり、最大個数の合計は8から6に減少したわけです。

図 2-4

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

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

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

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

3.実際に使ってみよう!

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

図 3-1

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

  • 数字1は最大2個入る。
  • 数字3は最大1個入る。
  • 数字6は最大1個入る。
  • 数字7は最大1個入る。

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

図 3-2

 結論はこうなります。

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

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

【数字1】
最大2個 → 最大0個。
【数字3】
最大1個。
【数字6】
最大1個。
【数字7】
最大1個。

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

4.同数にこそ真価あり !?

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

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

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

図 4-1

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

  • 数字2は最大1個入る。
  • 数字4は最大1個入る。
  • 数字9は最大1個入る。

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

図 4-2

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

  • 左上ブロックで候補数字2, 4, 9の大量除去が起こる。

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

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

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

図 4-3

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

  • 数字3は最大1個入る。
  • 数字4は最大1個入る。
  • 数字6は最大1個入る。
  • 数字7は最大1個入る。
  • 数字8は最大1個入る。

 候補数字4, 6はタテ1列にある。
 候補数字3, 8は1ブロックにある。
 候補数字7はタテ1列または1ブロックにある。
 だから、どれも最大1個です。

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

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

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

図 4-4

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

  • 数字1は最大1個入る。
  • 数字2は最大2個入る。
  • 数字3は最大1個入る。
  • 数字4は最大2個入る。
  • 数字5は最大2個入る。
  • 数字6は最大2個入る。
  • 数字7は最大2個入る。
  • 数字8は最大2個入る。
  • 数字9は最大2個入る。

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

参考・参照

更新履歴