1.入れられる数字の最大個数がカギ
まずは、この解法の核となる「最大個数」について話をしましょう。
まずは、ごく普通の部分図を1つ。
図1-1、青色7マスを見てみましょう。
その7マスにある候補数字は全部で5種類ですね。
2, 4, 5, 7, 9の5種類。
この数字達で青色マスは埋め尽くされていくわけですが、もちろん、今のところどの数字が何個入るかはわかりません。
そこで、ちょいと視点を変えてみる。
こんなことを考えてみます。
それぞれの数字、青色7マスに最大何個まで入れられるんだろうか?
各数字の個数の上限、それぞれ調べてみましょう。
各数字の最大個数は次の通りです。
- 数字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-1 から候補数字9をいくつか消して、図1-3 のようにしちゃいました。
この青色7マスに対して、各数字が最大何個まで入るかをそれぞれ調べてみましょう。
- 数字2は最大1個まで入る。
- 数字4は最大1個まで入る。
- 数字5は最大2個まで入る。
- 数字7は最大1個まで入る。
- 数字9は最大1個まで入る。
最大個数を合計すると、1+1+2+1+1=6個になりました。
今度は合計値がマス数を下回りましたね。
実は、この状況になると悲劇が起こるんです。
どういう悲劇なのか?
それは……、
数字6個では青色7マスを埋め尽くせない!
これはもぅ明らかですね。
7マス埋めたいのに数字が全然足りてないんだもの😵
なんとか数字6個を入れたとしても 図1-4 のようになっちゃうし。
当然ですが「最大個数の合計は6」なのだから、数字は6個より多くできません。
破綻からはどうしても逃れられないんです。
最大個数の合計が少なすぎてはダメなんですね。
というわけで、結論が1つできました。
- 空きマスからなる領域をAとする。
Aに入り得る各数字の最大個数を求め、それらを合計する。その合計値はAのマス数以上でなければならない。
最大個数の合計は必ずマス数以上である。
これ大事!
解法 Subset Counting は、「最大個数の合計が減少する」ことがカギとなって機能します。
その仕組みは次セクションで説明しましょう。
2.どういう解法?
では、解法 Subset Counting を解説していきましょう。
面倒なので前セクションの 図1-1 を流用します。
手抜きとか言わないで😅
図2-1 の青色7マスを見てみましょう。
この7マスに入れられる各数字の最大個数は次の通りでした。
- 数字2は最大1個入る。
- 数字4は最大1個入る。
- 数字5は最大2個入る。
- 数字7は最大1個入る。
- 数字9は最大3個入る。
最大個数の合計は8ですね。
7以上(マス数以上)であることも思い出しておきましょう。
実は、この状況から結論が1つ生まれます。
その結論とは……、
- 最大個数の合計をマス数未満に減少させてしまうマスがある。そのマスに当該数字が入らなくなる。
図2-2 では、赤色×印マスが該当します。
実は、このマスに数字9が入らなくなるんです。
なぜこういう結論になるんでしょう?
それは、赤色マスに数字9が入ると最大個数の合計が大きく減少してしまい、破綻が起こるからです。
それを解説しましょう。
今、赤色マスに数字9が入ったと仮定しましょう。
その上で、あらためて各数字が最大何個入るか調べてみます。
- 【数字2】
- 最大1個。
- 【数字4】
- 最大1個。
- 【数字5】
- 最大2個。
- 【数字7】
- 最大1個。
- 【数字9】
- 最大3個 → 最大1個。
なんと、数字9は最大1個に減ってしまった!
候補数字9がタテ1列にしか存在しなくなったからですね。
数字9の最大個数が2減った。
つまり、最大個数の合計は8から6に減少したわけです。
マスは7個なのに、最大個数の合計はそれよりも少なくなった。
破綻が起きてしまったんです😵
無理やり数字を入れたとしても、図2-4 みたいになっちゃう。
やっぱり、高々6個の数字で7マス埋めるのは叶わぬ夢である。
というわけで、「赤色マスに数字9が入る」という仮定は間違いだとわかった。
そのマスに数字9を入れてはいけないんですね。
図2-2 の結論通りになりましたね😊
この解法の大事な点を1つ。
- 最大個数の合計がマス数以上だったのに、あるマスに数字を入れたら合計がマス数未満に減少し、破綻が起きた。
この事実が必要である。
マス数を境界線として、それを踏み越えることが必要です。
合計がただ減少しただけでは解法 Subset Counting は使えない。
この点、注意が必要です。
3.実際に使ってみよう!
実は、既存の解法のうちいくつかは Subset Counting で解くことも可能です。
そこで、WXYZ-Wing のページにある実例に使ってみます。
図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 を使ってみましょう!
結論はこうなります。
- 赤色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 も同様です。
ちょいとそのあたりの話をしてみましょうか。
まずは3国同盟(Naked Triple)を1つ。
図4-1 は3国同盟のページで実例として挙げた盤面です。
青色3マスを見てみましょう。
各数字の入り得る最大個数は簡単にわかりますね。
- 数字2は最大1個入る。
- 数字4は最大1個入る。
- 数字9は最大1個入る。
最大個数の合計は3で、マス数と同じです。
ということは、数字2, 4, 9どれでもいいから最大個数を0にすれば破綻が起きる。Subset Counting で解決できる。
そういうマスが左上ブロックにたくさん見つかりそうですね。
というわけで、こういう結論になるんです。
- 左上ブロックで候補数字2, 4, 9の大量除去が起こる。
注目すべきところは、除去の多さです。
なんと、5個もある!
今までは1〜2個しか除去できなかったのに、格段に増えました。
こういうふうに、合計とマス数が等しいパターンだと大きな除去力を発揮することがあるんです。
「最大個数を1減らせばいい」というハードルはそこそこ低い。
少なくとも、2以上減らすよりは明らかに低い。
……とは言っても、n国同盟をわざわざ Subset Counting で解釈するメリットは薄い。
だけど、Sue De Coq のような高難度の解法だと Subset Counting の方が理解しやすいかもしれません。
図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減らそう理論』は汎用性の高い概念ではないかなぁと個人的には思っています。
最後は究極のパターンをご紹介。
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)
参考・参照
- The New Sudoku Players' Forum, 『Subset Counting』,
http://forum.enjoysudoku.com/subset-counting-t3479.html - Sudopedia(ミラーサイト), 『Subset Counting』,
http://sudopedia.enjoysudoku.com/Subset_Counting.html
更新履歴
- 2023. 4.27.
- 新規公開。