メニエスの名のもとに

プログラミング関係を中心としたぐだぐだブログ

ナンプレ(数独)問題作成プログラム 生成法解説2

phase3 再帰しながら指定された解法を含むまで全部調べる。

phase3 は再帰アルゴリズム。入力は盤面配列(実は入出力)と検索開始位置と解法指定、出力はあまり言いたくないけど難易度、ただし、マイナスは矛盾があって解けない。ゼロは知っている解法では解けない。
最初に解いてみて、指定された解法で解ければ適当に計算した難易度を返す。解けなければ0またはマイナスを返す。指定された解法では解けない場合、関数本体の処理を行う。
開始位置から配列の半分までのすべての固定マスについて、そこを固定でなくしてみて再帰する。その中で再帰の返却値が最も大きい時の盤面を返す。
なんだ簡単だった。

phase4 もう一度固定を外す。

phase3では指定の解法を含んだ時点で固定マスを外すのを止めていたので、まだ固定マスを減らせる可能性がある。そこで対称性を保ちながら、固定マスを外しても解けるか調べる。

phase5 対称性を考えずに固定を外す。

最後に対称性を考えずに固定を外して解けるかを調べる。

単純ですね。

プログラムを日本語でそのまま説明して、ドキュメントにするなんていうのは、職業プログラマならいくらでも経験しているはず。図を描けばいいんだけど、それは面倒だからね。まあ、本当に関心のあるひとはプログラムを読むでしょう。明らかにphase3が遅い。その結果、難しい解法だけを指定するとプログラムの実行がすごく遅くなる。まあ、1問につき1行の出力なのでTuple以上あたりの指定(-tfy)で大量に出力させ、その中から良いものを選ぶのがいいんじゃないかな。

mosaic.wav の新作が出ている

だが、ナンプレアプリが売れていないのでがまん、我慢。