Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- -- プログラムで問題を自動生成
多重解にならないために
白マスを積極的に決める
方針変更
方針を決めるために、手作りを振り返ってみよう。
次の図は、「ナンプレを作ってみよう」の中級問題のまだ序盤である。
赤丸に何か適当な数字を置くと、赤い「Ｉ」のマスがその数字になる。 ここでは、「２」を使うことにしている。
さて、ここで考えてみよう。 赤丸を「２」にしたら、「Ｉ」のマスが２に決まると言うが、 今まで考えてきた方法で、上のようになるであろうか。
空色マスで既に決まっている部分だけ数字を入れてみた。 その場合、白色マスは、今までの考えに従うとどこまで決定するだろうか。
空色マスに注目数字を入れられないと仮定する
実は、白マスについては、これ以上何も決まらないのである。 仕方がないので、手作りのときに決まっていたマスに数字を入れて、 その後の１手についてだけ考えることにしよう。
右の赤の２を決めたとき、手作りの場合には、緑枠のマスも２に決めていた。 しかし、今まで考えた方法では、そこまでは決まらない。
どういう考えに基づけば、緑マスの数字が２になるのだろうか。
注目すべきは、緑枠のあるマスを含む３×３のブロックであろう。
で、その考えは？
注目すべき３×３のブロックだけを取り出してみた. 緑枠のマスを２に決定するためのロジックは何だろう?
２について調べると、小さい２が入っているマスは、 １白マスと３空色マスになっている。
手作りのときには、考えている数字(今の場合は２)は、 空色マスには入らないものと考えていた。 空色マスに２が入らないとすると、白マスで２を入れられるのは １マスしかないので、確かに緑枠のマスが２に決まる。
というのは、手作りのときの考えだが、これをプログラムで実現するのに 都合のよい手順にまとめ直してみよう。
ある数字が、あるグループ(縦、横、ブロックの９マス)の中で、 出現する白マスが１個所しかなければ、空色マスにいくら存在しても、 その白マスをその数字に決めることができる。
文章力がないので、こんなに長ったらしい文になってしまった。
上の実例で言うと、ある数字というのは２である。 あるグループというのは、切り出している３×３のブロックのことである。 小さい２が存在するマスを調べると、白マスで２が入っているのは、 緑枠のある白マスだけである。 だから、この白マスは２に決まる。
となるのだ。
各グループについて、まだ出現しない数字に関して、 白色マスに関する限り１個所にしか出現しない場合には、 そのマスをその数字に決定して良いというものだ。
ということで、この考え方をプログラムに組み込んでみよう。
プログラムに実装
上記の考え方をプログラムに組みこんで動かしたら、 次図のようになった。
白マスがどんどん決まるようにしているにもかかわらず、 全然決まっていない。
実際、この状態でなんとか白マスも決めようとしても、 決められる個所がない。
なぜ？
そもそもの方針が、影響空色マスは少なく、影響白マスを多くしていたのだが、 そうすると、どうしても異なる数字を使いたがるようになる。
この図では、２と５がそれぞれ２個あるが、その他の数字は１個である。
これは、人間が問題を作るときとは大きく異なる。 人間は、もっと片寄った数字の使いかたをする。 というか、特定の数字を早く片付けようとする。
さて、どうしよう？
考え直そうかと思ったが、面倒なので、 ここはもう少し様子を見ることにしよう。
ということで、そのまま続行したらどうなるかみてみよう。
１５個目の空色マスの決定で、やっと次の場面に到達した。
中央上のブロックの白マスの１が決まっているので、 プログラムは仕組まれたように動いているようだ。 めでたし、めでたし。
しかし、まだ、白が１マス決定しただけに過ぎないし、 空色マスも残りが９マスもある。 まだ、馬鹿独で虱潰しで問題にできるパターンを全部調べ尽くすのは 困難だろう。
ということで、さらに続けてみた。
すると、次の状態に到達し、白マスが２つ決まった。
決まった理由は分かるだろうから、説明は省略する。
まだ、決まるだろうか？
実は、次のように、(1,0)の５が決まる。
決まる理由は分かるだろうか？
左から２列目で、５が入れられるマスを調べてみよう。 空色マスには入れないことにすれば、 (1,0),(1,2),(1,6),(1,8)の４マスが入れられる可能性の あるマスである。
しかし、(1,2)と(1,6)は横に５が存在するので、５は入れられない。 したがって、白マスで５が入れられるのは (1,0)と(1,8)に絞られる。
しかし、下中央のブロックで５が入れられるのは、一番下の段の (3,8)と(5,8)しかないので、(1,8)には５は入らない。
ということで、空色マスに５を入れないという路線に従うと、 (1,0)に５を入れることになる。
同様の考えで、さらに３つのマスが決まる。 といっても、１つは空色マスなので、ちょっともったいないが。
早めに序盤を終らそう
さて、次の状態に到達した。
ここで、情况を分析してみよう。
空きの空色マスが６マスである。
白マスはまだ空きのままの状態がたくさん残っているが、 もしかすると馬鹿独で虱潰しが可能かもしれない。
ということで、とにかく虱潰しをやってみた。
虱潰しをした結果、解の総数は７８７９個であった。
そして、ユニーク解、つまり問題として採用できる場合はどうなるだろうか。
多重解
残念ながら、ユニーク解はなく、全て多重解になってしまった。
ということは、今まで考えた方針は良くなかったのかも知れない。
もっと人間的なアルゴリズムを考えるべきだろうか。 空色マスばかりがどんどん決まってしまうアルゴリズムを止め、 しっかり白色マスも決まるように空色マスの数字をコントロールするべきか。
しかし、考えると面倒である。 最初は適当にバラバラと置いてしまおう、 それで駄目なら少しくらいは努力しようという横着路線だった。
ここは横着路線を守ることにして、面倒なプログラムを書かないでも、 何とかならないかを考えることにする。
それで、途中まで戻して、次の状態で考えなおすことにしよう。 つまり、最後の３マスぶんの決定を取り止めた状態である。
さて、この状態で、ユニーク解は存在するのだろうか？
調べ尽くせば
頑張って調べ尽くしてみたら、解の総数が57258通りあり、 そして、ユニーク解が25個もあった。
つまり、白色マスの決まる場所を積極的に決めるのを やり過ぎたようだ。途中で止めておけば、 たくさんのユニーク解がみつかり、 その中から適当なのを選べばよいことになる。
たとえば、次を問題として使ってもよいだろう。
序盤の結論
白色マスをできるだけ決めてしまうのは重要ではあるが、やり過ぎると破綻する。
この序盤のやりかたから、直接力業の虱潰し(終盤)に繋げるのは無理があるようだ。
序盤を適当なところで放棄し、もう少しうまく決められる方策を組みこんだ中盤を準備するのが妥当ではないかと思う。
序盤：適当にばらまく
中盤：巧みに決めていく
終盤：力業の虱潰しで調べ尽くす
これで大丈夫だろう。
中盤が終ったときに、ユニーク解が存在しやすい状態になるように中盤のアルゴリズムを作らねばならない。
まあ、そういうアルゴリズムは中盤の解説で述べることにし、とりあえず、序盤の話はここで終ることにする。
序盤と中盤の切り替えのタイミングも重要なようだが、それも中盤のアルゴリズム次第だろう。
やれやれ、やっと序盤が終った。(終らせた！)