Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- -- プログラムで問題を自動生成
序盤の数字のばらまき方
序盤の考え方
さて、終盤で馬鹿独で虱潰しを実行することで、 破綻しているかどうかの判定はできそうなことが分かった。 終盤まで持ちこんで、虱潰しをして、ユニーク解が存在すれば、 その中から１つを問題として選べば良い。 沢山のユニーク解が存在するのなら、その中からもっとも良さそうなのを 問題とすればよい。
ということで、終盤に持ちこんでユニーク解が存在すれば、 問題作りは成功と考えられる。
問題を作る場合、先ず数字を置く位置(空色マスの配置)を決めて、 徐々に数字を置いていって、 最後に馬鹿独で虱潰しをすれば良いようだ。
でも、終盤にどうやってたどり着けば良いのだうか。
普通の問題だったら、表出数字は２４個位が妥当なところだろう。 さらに、数字が少なめの問題も作ることができれば、 非常に嬉しいではないか。
できることなら、２０個とか、さらにそれ以下の個数の 数字しかない問題だと、とてもすっきり感がするかもしれない。
そのためには、
必要以上に空色マスを使わない
ことが重要になる。
さて、どういう考えをすれば、空色マスを浪費せず終盤まで持ちこめるのだろうか。
効果的なヒントの場所
空色マスを浪費しないのも重要なのだが、もう１つ考えておくべきことがある。
「手作りの方法」で説明した方法にしたがって動くようなプログラムを 作ろうとすると、かなり面倒な気がする。
盤面を全部見渡して、空色マス１つを選ぶのならともかく、 ２つの組み合わせを選んで、なおかつ効率的に空色マスを使っている ことまで考えるのは面倒である。
実際に空色マスに数字を置き、 その先を可能なところまで延々と先読みすることが必要だ。 面白い手筋を問題に埋め込もうとすると、そういう面倒なことが必要だ。
そういう先読みを、全ての空色マスに対して、 可能な数字に関して全て調べるのはとても面倒だ。 それに、そういう手筋を考えながら動くプログラムを作るのは面倒だ。
何か、上手い方法で、結果としてまるで手筋を考えながら問題を作っている ようになる方法はないだろうか。 単純な調べ方しかしていないのに、 あたかもプログラムが熟考しているような動きは実現できないだろうか。
ということで、まず、空色マスに最初の数字を１つ置いた場合の 状態について考えてみよう。
どういうことが考えられるだろうか。
置いた数字のマスにことは考えないことにしよう。 その他のマスの状態がどのように変化したであろうか。
空色マス：５個のマスで、１を入れられなくなった。 白色マス：１５個のマスで、１を入れられなくなった。
では、次の図ではどうなるだろうか。
空色マス：８個のマスで、１を入れられなくなった。 白色マス：１２個のマスで、１を入れられなくなった。
さて、この２つでは、どちらが空色マスの使いかたとして効率的と言えるだろうか。
空色マスと白マスに対する考え方をまとめておこう。
空色マスは、できるだけ多くの可能性を残しておきたい。 作る側は、空色マスを制御して問題を作るので、 空色マスの減少、さらに、空色マスの中の可能性の減少もできるだけ避けたい。
白色マスは、できるだけ可能性を減らして、早く確定したい。 作る側は、白色マスを勝手にいじることはできない。 あくまでも空色マスに入れる数字の影響により白色マスをどんどん確定 させるしかない。 つまり、白色マスの確定、さらに、白色マスの中の可能性の減少は望ましい。
こういう考え方に立って評価してみよう。
すると、
| 配置場所 | 影響空色マス | 影響白マス |
| (0,2) | 5 | 15 |
| (1,1) | 8 | 12 |
の場合、(0,2) に置いた場合の方が効果的と考えられる。
この考え方で、いくつか置いてみよう。
何マスか決めてみよう
２つ目のヒント
２つ目を考えてみよう。 今の自動生成システムでは、次のようになった。
１の次の数字が４になった。いつも１から順番にしていては、 問題に余分な傾向がついてしまうので、
使う数字の順番は乱数で決めている。
２番目の数字は、もちろん１番目と違う数字を使う。 できるだけ異なる数字を使う方が、制約が強くなるから、 できるだけそうなるようにしている。
さて、どのマスに２番目の数字を置くかを決める事が重要だ。 この場合も、できるだけ空色マスへの影響を少くし、 白色マスへの影響を大きくする。
さらに、２つ目からは、既に置かれている数字との影響を考えないといけない。
次の図と比較しよう。２つ目のマスの場所が違う。
今回は、１番目のマス(0,2)の真下の(0,6)である。 これにより、左端の縦の列の空色マスは使い尽くしてしまった。
これは、左端の白マスの値は、左端の青マスではなく、その他の青マスの 影響で決めるしかないことを意味する。
縦、横、ブロックが全部で２７グループ存在するのだが、 できるだけ平均して使用していく、 偏りの少ない空色マスの使い方が望ましい。
したがって、同じ縦の(0,6)ではなく、縦と横が共に異なる(1,4)の方が 評価が高くなる。
３つ目、４つ目のヒント
３つ目を決めてみた。
既存の空色マスへの影響が少なく、白色マスにはできるだけ影響を及ぼす 空色マスの１つである場所に決まったようだ。
４つ目も決めてみた。
今回も、今までと同じ方針で決まっていると思われるのが分かるだろう。
自動生成システムの序盤
自動生成システムは、次々と適当な空色マスに数字を置き、 次の状態に到達した。
既に、中央を除く３×３ブロックの全てに数字が入ってしまっている。
次の数字を置くときには、必ず空色マスが既に使われているブロックの 空色マスを使うしかない。 手数が進んで来たのだから、そういう情况が発生するのはやむをえない。
自動生成システムでは、次の図のように(4,6)の空色マスを選んで、 まだ使われていない「２」を入れた。
同じブロックと、右横方向に既に数字の入った空色マスが存在するが、 そういうぶつかりが２個所しか発生しないマスを自動生成システムは選んだ。 空色マスによっては、３個所とぶつかるマスがあることを確認されたい。
いい加減な考えで動いているが、それでもちゃんと考えてマスを選び、 数字も選んで入れているかのように見える。 まあ、人工知能の内側が実はこんなことだったというのは良くある。
とりあえず、このまま進めることにしよう。
哀しい結末
どんどん決めてしまうと...
どんどん進めていったら次の図の状態に到達した。
左上(1,1)を３に決めたのだが、その影響で、右上の白マスの赤の「３」が 決定してしまった。
このくらい埋まってくると、白マスの中に決定してくるマスが出てくるので、 ちゃんとプログラムで調べて、決められる白マスは決めてしまうように しておかなければならない。
さらに進めると、次のようになった。
右上の(7,1)の８を決めたことにより、右上の３×３のブロックについて、 まず８が他に入らないことが分かる。 それにより、(6,1),(6,2),(7,2)の３マスに入るのは、６、７、９ しかないことが分かる。 これにより、(8,0),(8,1)が１、４しかありえないのも分かる。
ちょっと難しいかも知れないが、そういう必然で決まることは、 ちゃんとプログラムにしておこう。 要するに、決まるところまでできるだけ 調べ尽くすように作っておく必要がある。
もう残りの空色マスは４マスしか残っていない。 このくらいになったら、馬鹿でも調べられるだろうから、 馬鹿独の出番だろう。
さて、どうなるだろうか?
多重解の発生
ということで、馬鹿独に掛けてみたら、 結果は、解は2031個しかなかった。
しかし、全て多重解になり、問題として可能なものは存在しないのだった。
破綻してしまった!
ということで、このやり方では次のようなことが発生しやすそうだ。
このやり方では、全て多重解にて破綻しやすい。
空色マスの数が少くなれば、さらに破綻しやすい。
つまり、もう少し、白マスも早く詰まるようにしないといけないようだ。
次なる戦略は、もう少し早い段階、つまり空色マスが６個くらい残っている 段階で、もっと白マスを決めておくのが良いのではないだろうか。
そもそも、人間が問題を作るときには、最初から白マスの数字が 決まるようにして作っているではないか。
もう少し白マスを早期に決めてしまうことを考えなけれなならないようだ。 どうしよう。