Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- -- プログラムで問題を自動生成
終盤へのつなぎ方
終盤に繋げられるか
中盤は、各空色マスに入る数字の回数を数えて、 それらの中から少ない方の３つくらいの中から 適当に選ぶことにした。
この方法で大丈夫かどうか、終盤に繋げられるか試してみよう。
その前に、終盤とは何だろうか。 馬鹿独で、唯一解(問題として成立)となる 問題パターンが存在するかどうか確かめられる状態に たどり着いた時点を終盤とする。
要するに、馬鹿独できちんと調べ尽くせるかどうかだ。
時間さえかければ、10,000,000個の解があっても調べられるが、 妥当なのは数万個以内だろう。 ここでは、短時間で調べられるように、 解の総数が10,000個以下になったら、 馬鹿独の虱潰しで処理できる終盤になったとみなそう。
調べている解の総数 ＜ 馬鹿独で虱潰しが可能な解の数(10,000個)
中盤も、結局馬鹿独で統計を取っていて、 現在10,000個まで調べて中断しているだけである。 解を調べ尽くせることが分かった時点で、 中盤を終えれば良い。
３手目 (7,5)=3 887 ３番目 ４手目 (5,1)=7 1231 １番目
(5,1)に７を入れたとき、やっと白マスが１個所決まった。 やれやれである。
さらに続けてみよう。
５手目 (8,2)=6 845 ３番目 ６手目 (2,4)=6 1159 １番目
６手目の(2,4)のマスに６を入れると、次々と６が決まったところである。 さらに、(2,7)の５も決まる。
決まる順番は
(7,8)=6 (0,7)=6 (1,1)=6 (2,7)=5
である。
統計情報を見てみよう
空色マスの空きは６マスに減ってきた。 そろそろ終盤になってくれなければ困る。
空色マスの統計情報を示す。
(2,0) 2-7072 3-1539 8-1389 (7,1) 1-4436 5-2550 8-354 9-2660 (1,5) 1-1729 2-3180 4-1280 5-1697 9-2114 (0,6) 2-4769 3-2606 8-2625 (3,7) 1-2547 8-4305 9-3148 (6,8) 2-628 3-7436 8-1936
まだ、10000個以上解があって、終盤には入れない。
しかし、以前とは違い、最初の方が１つの数字に固まっていて、 n-10000 という様な表示にはならなくなった。
今回は、もっとも少ない、つまり出来るだけ制約を強くかけられそうな
(7,1)=8 354
を選んでみよう。 354/10000 に絞り込むとも考えられる。
しかし、どんどん白マスが決められるということはないようだ。 さて、これで、終盤に持ちこめるだろうか。
さらに馬鹿独で統計を取ったら、次のようになった。
(2,0) 1-182 2-1238 3-358 8-6618 (1,5) 1-1635 2-1544 4-627 5-2532 9-2058 (0,6) 1-1318 2-2197 3-2254 8-2627 (3,7) 1-1753 8-3753 9-2890 (6,8) 2-1088 3-4007 8-3301
また、できるだけ絞りこむのが良いだろうから、ここでも一番回数の少ない
(2,0)=1 182
を選ぶべきだろう。
と思ったら、
Answer 8396
という表示も出ていた。今、解の総数が10000以下になったら、 中盤終え、終盤で完全虱潰しをやろうとしているのだが、 とうとう終盤に入れるようだ。
ここで、(2,0)と決めるのは止めて、終盤処理に入ろう。
ところで、終盤はどうすれば良いのだろうか。
終盤に入れそうだ
めでたく、まだ空色マスが５個残した状態で、 解の総数を10000未満にすることができたので、終盤処理に入れるようだ。
解の総数が10000未満になる前に空色マスの残りが無くなってしまったら、 それは失敗である。 まあ、そいういう時には、初めからやり直すことにしよう。 人間が問題を作っていると、簡単にやり直しはできないが、 コンピュータはやり直しを命じられても、ただもくもくと処理するだけだ。 コンピュータはどんどん高速になっているのだから、 失敗したら、気軽に最初から作り直すのがよいだろう。
さて、解の総数が10000未満で、空色マスが残っている場合には、 馬鹿独で、全解を調べ尽くして、問題として使えるパターンが存在するか 判定しよう。
そのやり方は、 破綻の判定が欲しい の中の「馬鹿独の活用」に書いたので、調べて欲しい。 以下に、簡単に書いておく。
残りの空色マスは、
A=(2,0) B=(1,5) C=(0,6) D=(3,7) E=(6,8)
であり、この５つのマスに入る全パターンの出現回数を数えるのであった。
その数が１の場合だけユニーク解であり、０は存在しないパターン、 ２以上になったら複数解となるパターンである。
では、実際に調べてみよう。
どういう (A B C D E) に対してユニーク解が存在するだろうか。 あるいはまったく存在しないのだろうか。
終盤処理
さて、虱潰しでユニーク解が存在するかどうか調べたら、 幸運なことに３個もユニーク解が存在することが分かった。
以下にユニーク解を列挙する。
(1 1 1 1 8)
(2 5 3 1 3)
(1 9 3 9 8)
これで、めでたし、めでたし。
かな?
問題の選択
３個も問題として可能なものが存在した。
これら３個をそれぞれ別々の問題として良いだろうか。 問題の数字は、高々５個所しか違わない。
これらの問題が、解いているときに似ている手筋で解けたり、 そうでなくても解き心地が似ていたりすると、 別の問題という感じがしないと思う。
それに、この３つの問題を連続して出題されたら、 あまりに似ていて、出題者は間違って同じ問題を出題してしまった、 と思わないだろうか。
いずれにしろ、似たような問題を出すのは良くないだろう。
今回は３個だったが、もっと沢山のユニーク解、問題候補ができる こともあるだろう。そういうときでも、それらの中から１つだけ これはと思うのを選択し、残りは潔く捨てないといけない。
問題なんて、コンピュータを使えば疲れることなく、 人間が解くより早く作れるのだから、
良いものを１つだけ選んで問題としよう。
さて、そのときの選択はどうすればよいだろうか。
難易度を考慮
まず難易度を考えないといけない。
虱潰しでユニーク解であることは保障されているが、 難易度に関しては何も分かっていない。
人間に解けないような難しい問題を作ってもムダである。 人間がちょっと、あるいは頑張って解ける程度のが良い。
という訳で、人間が解けるレベルかどうか、 仮定をしなくてもちゃんと解けるかなど調べないといけない。
これについては、実際に解いて調べないといけない。 人間が解いて調べても良いが、それは大変な作業になる。 「プログラムで問題を解く」の中の 難易度判定 で詳しく述べたので、実際のやり方はそちらを参照して欲しい。
今回の３個の問題候補の難易度は、当方のシステムでは以下のようになった。
(1 1 1 1 8) Level 4 (2 5 3 1 3) Level 7 (1 9 3 9 8) Level 6
このように、同時に生成される問題でも、難易度はまちまちである。 どれを選択するかは、どのくらいの難易度の問題を作ろうとしているかによる。