数独というパズルがあって、どんなものか説明するのは大変めんどくさいのでググってほしいのだが、そのパズルを解くツールをRubyで作ってみた。たぶんどこかに転がっているとおもうのだが、探すのが面倒なのと頭の体操代わりに自分で作ってみたくなったのだ。
ボードスイープ
ロジックとしては、
- 同じ行と列にある数字
- 同じ3×3のエリアにある数字
- を集めてきて、それ以外の数字が1つしかなければそのマスにその（ひとつしかない）数字を入れる
というのを9×9の全部のマスについて実行して、それを何度か繰り返すと答えが得られる。これをボードスイープと呼ぶ。
エリアスイープ
ボードスイープだけ実装して巷の問題をいくつか拾ってきて入力してみるが、解ける問題と解けない問題がある。なんで？
途中まで解けた問題は、そこからワタシが（つまり人間なら）解くことができる。自分がどうやって解いたかを考えると、もうひとつスイープの方法があることに気づいた。つまり、
- あるマスに「入れられる数字」を求める。これは上記のボードスイープの過程で得られる。
- 同じ3×3のエリアの他のマスに「入れられる数字」の和集合を求める
- 前者に含まれ、かつ後者に含まれない数字を求める
ということをすれば、さらにいくつかのマスを埋めることができる。これをエリアスイープと呼ぶ。
複合技
ボードスイープとエリアスイープを繰り返すと答えが出ることが分かった。さっき解けなかった問題もこれでばっちり。
調子に乗って「超難問」とかいう問題に手を出したら…ばっちり解けなかった。なんでだ。なんか他に理屈があるのか。分からん。
というところで本日はお開き、続きは明日のお楽しみ。
