sudoku.rbに対称性アプローチ
また少し数独ジェネレータで実験してみた。
ランダムに数字を抜き取るのではなく、対称性を考慮したほうがいいのではないか。なぜなら多くの人間が作る問題は左右、上下、あるいは反転、それらの組み合わせである回転対称などの対称性を持っていることが多いように見えるからだ。竹ひご細工のように数字列を編み込んだ形が理想的ではないかというのがぼくの直感。特に(5,5)のセルを中心とした180度の回転対象は効率が良さそうに思える。
セルから数字を抜き取る際、必ず4つセットで行う「reduce_by_quadruple」というメソッドを追加してみた。
回転対象の位置にあるセルって、どうやって座標を求めたらいいんだろうかと一瞬考えたけど、0から80までの一次元配列で表現した9×9のマトリックスであれば、単純にmatrix[i]と対照の位置にあるのはmatrix[80-i]だと気がついた。
最初にチェックするセルをfindを使って左上の象限に限定している。findって便利だ。
def reduce_by_quadruple srand candidate = (0..80).to_a candidate.find{|i| ((i % 9) <= 4) && ((i / 9) <= 4)} while(candidate.size > 0) c1 = candidate.pick_one c2 = 80 - c1 if(uniq_solution?(c1) && (uniq_solution?(c2))) @matrix[c1] = @matrix[c2] = 0 end candidate.delete(c1) candidate.delete(c2) end end
さて、これで対称性が保たれた数独の問題が作成できるようになった。しかしどうもヒントの個数が多いような感じだった。ヒント数を減らすために対称性を入れてみたのに本末転倒。
それで次に対称性を保ったまま数字を減らしていき、もうこれ以上4つまとめて取り除けなくなったら、再びランダムに1つずつチェックするという2段構成にしてみた。結果は以下のとおり。
47 --> 39 ------------------- | 2 |7 3 |4 8 | | 8 | |9 3| |1 |4 8 6|7 | ------------------- | 7| |8 9 5| | 5 | 1 | 2 | |9 4 6|2 |1 | ------------------- | 8|1 5| 9| |4 |3 2| 7 | |5 9 2| 4| 1 6| ------------------- 48 --> 44 ------------------- |8 5 1|6 4| 2 | |4 6 | 2 1|8 5| | 7 |9 8 | 6 | ------------------- |5 | 6 9|2 | |9 2 | |6 4 3| | 7|2 4 | 1| ------------------- |2 9 | 7 3| | |7 3| 5 | 1 2| | 4 |8 2|3 5 7| ------------------- 52 --> 46 ------------------- | 5| 6 7| 9 | |6 9| 5 8|7 2| |4 2 7| | 5 8| ------------------- | 9 1|5 7 | 8 | | 7 6|3 9|1 | |2 5 | 1 6|9 3 | ------------------- |9 6 | 5|8 4 1| |7 |9 8 |5 3| |5 4 |6 3 | | -------------------
「47 --> 39」とあるのは対称アプローチでたどり着けた最小のヒント数が47、その後さらに1つずつ取り除いた結果が39であることを示している。
対称性が高いものの、必ずしもそれが保たれていないという、ある意味ではやや人間臭いような問題が生成できるようになったし、どうもヒント数もぐっと減ったような気がする。そう思って平均値を調べてみた。
- 素朴な1つずつ除去：42.7個
- 対称に4つセットで除去：47.8個
- 4つセット除去 --> 1つずつ除去：42.5個
対称性を取り入れても、数字の上ではまったく意味がないらしい。
ただ、生成される問題を眺めていると、確かに対称性が高い問題が作れるようになった。と、いうことは、同じマトリックスの初期状態でも、抜き取る順序によって最終到達型は異なるということだ。当たり前ような、そうでもないような気もする。
もし抜き取る順序を工夫することで結果が変わるのなら、問題の難易度を上げるためにはブロックごとの残数が均等になるようなアプローチもあるかもしれない。
