メニエスの名のもとに

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

ナンプレ(数独)問題作成プログラム その23 generate

generate の実行形式がmake できるソースをGitHubに上げました。

まあ、例によってバグがあるという可能性は否定できない。というかむしろ高い。
ドキュメントが出来ていない。doxygen を想定してコメントは入れていたけど、実際にはdoxygenをかけていないのでdoxygenのエラーが出ると思われる。これから直さないと。
MSaito/NumPl · GitHub

使用法

9x9のナンプレの問題を作成する

./generate
generate start seed = 4226 number = 1
"90,4,7,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,28,1":"  1 2    32 4 1      563     4  51  61  4  75  83  9     954      1 8 64      7  "

何も引数を指定しないと、一個だけ問題を作成する。出力の最初の行は疑似乱数のseed を表示している。number = 1 は出力を1個だけ出すということを表している。
次の行のコロンの前は、使用する解法の情報を示しているが、最後の二つは固定数字の数と解けるかどうかを示している。上の例では固定数字が28個、そして解ける。これはユニークな解があるという意味である(バグがなければ)。
後半は最初の9個が1行目、次の9個が2行目というように問題を表している。

 ./generate -v
generate start seed = 3593 number = 1
number = 0
kill_single:86
kill_hidden:10
kill_locked:3
kill_tuple :2
swordfish  :0
naked_tuple[2] = 0
naked_tuple[3] = 0
naked_tuple[4] = 0
naked_tuple[5] = 0
naked_tuple[6] = 0
hidden_tuple[2] = 2
hidden_tuple[3] = 0
hidden_tuple[4] = 0
hidden_tuple[5] = 0
hidden_tuple[6] = 0
fish[2] = 0
fish[3] = 0
fish[4] = 0
fish[5] = 0
fish[6] = 0
fish[7] = 0
fish[8] = 0
xywing     :0
fx_count   :29
solved     :1

            [1][2][3][4][5]


         [3]      [1]


               [5]   [6]


      [7][5]   [4][8]   [2]


   [9]               [3]


[5]   [8][2]   [3][4]


   [5]   [6]


      [6]      [7]


[7][8][2]   [5]
  • v オプションを指定すると、もう少し見やすい形式で作成した問題の情報を表示する。-v オプションを指定しないときの出力は、この出力と対応している。最初がkill_singleの数、次がhidden_single の数というように。naked_tuple[2]はnaked pair の数を表している。hidden_tuple[6]とか絶対に出現しないが気にしてはいけない。fish[2]はx-wing, fish[3]はswordfishの数である。
  • h を指定すると hidden_singl を解法として含むような問題だけを出力する。-l はlocked_candidate, -t はnaked tuple, hidden tuple, -f はx-wing, swordfish,...,
  • y はxywing を解法として含むような問題を出力する。この指定を複数すると or で結合される。つまり、どれかを含めば出力される。この部分に何も指定しないと、-tfy が指定されたものと解釈する。
  • S オプションを指定すると、点対称な問題だけを出力する(はずである)

出力された問題は正規化(いいかげんな正規化)されているので、sort -u なりなんなりして、同一の問題を取り除くとよい。その後、convert を使ってランダム化するとよい。

./convert "1        2 3 4      5167    89    41 3 281 6 51    83    4157      3 9 6        4"
84,11,3,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,29,1"  5      6 2 4    8  395   14    39  2 917 4  59    16   829  3    5 7 4      9  "

ああ、convertの出力がおかしい。あとで直さなければ。(今直せって)(いやでももう今日は達成感があるのでやりたくない。)
おっと、重要なオプションを書くのを忘れていた。-c 数値で出力する問題数を指定する。-c 1000 とか指定するとそこそこ時間がかかるので、-c 10 で時間を計って見当を付けてから大きな数字を指定するとよい。数万から数十万問題を作成してその中からよいものを選ぶ必要があると思う。

アルゴリズムなど

これぞ、ヒューリスティックというようないい加減なアルゴリズムなので、うまく説明できないが、まあうまく動いているみたいだからいいじゃないか。あとで説明するかも。で、既に問題生成プログラムがあったのに時間がかかったのは、潜在バグがあったからです。あと高速化しようとして逆に低速化したりしていたので。

あさひなぐ小学館漫画賞受賞おめでとうございます

1巻から買ってるよ。大工原さんもいいキャラです。

あさひなぐ 14 (ビッグコミックス)

あさひなぐ 14 (ビッグコミックス)