メニエスの名のもとに

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

ナンプレ(数独)問題作成プログラム ドキュメント

ドキュメントは重要、超重要

といいながら、プログラムが出来てからドキュメントを書いているようではいけないわけだが。doxygen ドキュメントを頑張っていれましたよ。まだまだ不足していますが、一気にやる気力はない。ボチボチやるが、ドキュメントなので、このブログでは修正報告はしません。
それ以前に、昨日のgit push 時には重大なミスがあってコンパイルできない状態でした。ダメじゃん。
MSaito/NumPl · GitHub

generate プログラムの解説

generate.c は主に5つのphaseに別れています。このうち、phase5だけが非対称にする操作なので、-S オプションで対称生成を指定した場合は、phase5をスキップしています。

phase1 数字を決め打ち

phase1とphase2はAとBという二種類あります。主にAで説明します。phase1Aが呼ばれる時点で、ナンプレの盤面にはすべてのマスにすべての数字が候補として入っています。この時、まだ固定された数字はありません。
9つのブロック三行三列でありますが、それを四隅の4ブロックと中央十字の5ブロックに分けます。この扱いがAとBの違いになります。Aでは中央十字ブロックのそれぞれのブロックに数字を置いてそこを固定マスとします。固定マスとは出題時に数字が入っているマスです。
十字の上のマス内のランダムな位置に数字の1を置きます。それと点対称な位置(十字の下のブロック)に数字の2を置きます。ブロック内の位置はランダムですが数字は決め打ちです。あとで convert コマンドによってランダム化する必要があります。
同じく十字の上のマス内のランダムな位置に数字の3を、点対称な位置に4を置きます。十字の右側のブロック内のランダムな位置に5,7を、点対称な位置に6,8を置きます。
8まで使ってしまったので、十字の中央のブロックにはランダムな位置とその点対称な位置にランダムな数字を置きます。ここではランダムな数字を置くので、解けない可能性があります。解いてみて解けなければ、やり直します。
それから、中央以外のブロックにランダムな数字を一個ずつ対称性を保ちながら入れます。ここも解いてみて解けなければやり直し。
というのがphase1Aです。phase1Bは中央の代わりに四隅に数字を入れる点が違います。

random_solve ユニークでない解を適当に選ぶ。

ここまででは、固定マスの数が14なので、矛盾して解けない場合を除けば高い確率で複数の解をもつナンプレ問題になっています。用意してある解法をつかうと、ほとんどのマスに複数の候補が入った状態になります。この複数の候補からランダムに一つ選んで解くということを再帰的に実行して解きます。選び方が悪いと矛盾して解けないこともありますので、その場合はやり直します。
結果的にはすべてのマスに一つの数が入った完成形のナンプレが得られます。

copy

完成形のナンプレから、phase1Aの盤面に四隅のブロックだけコピーします。コピーした部分は固定マスに設定します。phase1Bの後なら中央の十字ブロックをコピーします。
この後、phase2以降で固定マスを減らすということを繰り返していきます。

phase2A

全部固定マスになっている四隅のブロックからランダムなマスを選んで固定を解除しすべての数字を候補として入れます。各ブロックに4個ずつ固定を解除します。解いてみて解けなければあきらめる、つまり最初からやり直し。
十字の上のブロックに固定で入っている数字をその左右のブロックから取り除いてそこをすべての数字を候補とするマスに変えます。

phase3

ちょっと説明が面倒なので、明日にしよう。phase1, phase2が特に勘と経験と失敗に基づくヒューリスティックな部分。phase3以降は比較的工夫のないオーソドックスなアルゴリズム

グレンラガン

バンダイチャンネルで見放題に入ったのでグレンラガンを見た。これ、螺旋がテーマなのは話が宇宙までスケールアップするという設定が先にあって、そこから螺旋とドリルが出て来たのではないかと思う。こういうスケールアップはガイナックスならではですね。