数独を解く２

１０月２８日付けブログの数独を解くプログラムで、数独を解いてみた。連続的に解くために若干の修正をしたが、本質的には変わりない。

サンプルとして挙げた「超極・激」には、対角線指定や、変形３×４などが含まれており、それらを除いた通常のもの１３０題を解いたものである。

出力の冒頭を以下に示す。



問題と解答と所要時間を示した。

解答時間の平均は０．６９２秒　最大３．４４秒であった。使用マシンのCPUはi7である。解答時間の分布は



詳細を検討してみると、checkだけで解けているものも多数あり、solveを用いて試行錯誤的にアプローチしているものも多い。solveを用いた場合、再帰の深さは結構深いのが目につく。

前回の解法アルゴリズムで、１つのグループ内に例えば５の可能性のあるマスが１つだけならばそこが５である、というアルゴリズムを最後に付け加えた。

これを拡張して、１つのグループ内に可能性が５と８だけであるマスが２つあれば、そのグループのほかのマスからは５と８の可能性が削除できる。

また、１つのグループ内に　可能性５と８を含むますが２つだけならば、その２つのマスの５と８以外は削除できる。

さらに拡張すると、１つのグループ内に例えば可能性が５と８と９だけであるマスが３つあれば、そのグループのほかのマスからは５と８と９の可能性が削除できる。この場合、この３つのマスのうちの１つは「５と８」でもよい。など。

これらについてはまだ、実装してない。