ナンプレ（数独）問題作成プログラム　その20 analyze

酔っ払ってプログラムを書いた。

一度作った問題を convert によって変換して何度も使うようにするという考えであった。ところが、convert すると solve で求める解法が違ってしまうので、convertで変わらないような解法の情報を求めようとしていたのであった。つまり、どの解法を何回使って解けるかということについて、できるだけ難しい方法を使わない最低の解法を求めようとしていたのである。
だいたい思いついたのだが、解法プログラム全部について同じような変更を入れなければならず、そいつは面倒だったので手をつけないでいた。しかし、年末年始に酒を飲んでから、突然やる気を出してプログラムを書いたのであった。

酔っ払って書いたプログラムはバグだらけだった。

コンパイルを通すところまでは酔っ払っていても行けたのだが、実行すると終了しない。こりゃあかんわい、ということで醒めてから書き直し。再帰すりゃなんとかなるだろうと思っていたが、再帰しない方がよいとわかった。

局所最適解を求めていた。

動くようにはなったが、convert を掛けるとやはり解情報が変わってしまう。少し考えてみると、今回書いたプログラムではまだ局所最適解を求めているだけであり、このアルゴリズムでは大域最適解は求まらないようだ。この問題に限らず、大域最適解を求めることは、一般には難しい。局所最適解を求めるプログラムを多少修正しても大域最適解を求めるプログラムにはならないのだ。全件検索すればよいのだが、その場合計算時間の予測がつかない。なので、一度あきらめる。analyze という実行ファイルができるまでのところは、GitHubに挙げておく。名前をanalysis ではなく analyze にしたのは、動詞の方がよいと思ったから。

convert のもう一つの懸案事項

convert によって問題数を増やせるのはよいのだが、一つ気になることがある。それは、自動生成した問題の中に convert によって変形できる問題があるのではないかということである。問題を10問作ってそれをconvertによって100問に増やしたつもりが、その100問の中に最初の10問と同じ問題があるかも知れない。これは嫌である。それを避けるには、何か正規の形というものを定めて、正規形になるようにconvertして、そこで同一性をチェックすればよい。解情報がconvertによって変わらないのであれば、それを使って少なくとも同一でないことが示せたのだが、それがダメになったので、正規形を考える必要性が高くなったということでもある。