Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- -- プログラムで問題を自動生成
乱数の乱用だけでは限界
数字をどんどん入れ替える
先に問題の形を決める
どんどん数字を抜いていったら、問題の数字の数を減らせなかった。そして、無理に減らそうとしたら、とても汚い問題になってしまった。
汚い形にしないために、最初に問題の形を決めてしまおう。
抜いているのでは、残り数字32個まで奇麗な対称形だったのだが、それ以上は減らせなかった。
ここでは、残り数字28個の次のパターンを実現することを考えよう。
最初の数字
適当に数字をばら撒いて始めても良いのだが、最初に作っておいた答えのパターン
と重なるように初期配置してみよう。
これを実際に解けるところまで解くと、
という感じになり、数字の決まらない白マスがかなり残ってしまう。
さて、どうしよう。
とりあえず数字の入れ替え
とりあえず、左上の方の空色のマスの数字を３から７に入れ替えてみた。
だいぶ未決定のマスが減ったので、このまま入れ替えを続けると解がユニークな問題がちゃんとできちゃうかもしれない。
今度は、右の方のマスを７から９に入れ替えてみた。
今まで決定済みの個所が未決定になってしまったり、決まっていなかったマスが決まったりする。たった１マスの数字の変更が、どうも全体に影響を及ぼしてしまい、その影響も予測しがたいようだ。
でも、未決定の白マスが減ったから、良い方向に向かっているのではないかと思う。
このやりかたで、どこかの数字を別の数字にして解いて行くと、次のように、どの数字も入れられない不可能マスが発生することがしばしばある。
しかし、こういう場合も無視して、更に別のマスの入れ替えを延々とくり返していくことにしよう。
人間が入れ替えるのなら大変な労力であるが、コンピュータなら延々と入れ替えても疲れることはないだろう。問題として成立するパターンを見つけるまでやり抜けばよいのだ。
何百、何千、何万回でも、コンピュータにとって、それほどの負担にはならないのではないか?
何とか完成
延々と入れ替えていたら、何とかユニーク解に辿りつくことができた。
これを、以下のような表示にすれば、いかにも問題のように見えるだろう。
形は最初に固定したから美しさは保てているが、２８個もの数字がある。これだけ数字が多いと、普通ならかなりやさしい問題になってしまう、というか易しくなければいけないだろう。
でも、できあがった問題は、じつはあまり易しくなかった。難易度に関しては、ユニーク解であることが分かった時点で、希望する難易度範囲に収まっていない問題が出来た場合には、問題を捨てて、つくり直せばよい。
コンピュータは高速なんだから、これで大丈夫ではないだろうか。乱暴な考え方だが、まあそういうもの有りということにしてしまおう。
でも、、、
ヒント数を減らしてみよう
数字が２８個の問題ができたくらいでは実用にならない。もっと少ない数字の問題が作れないといけない。
とりあえず、４隅をちょっとだけ変更した次の形を考える。
これを種パターン重ねると、初期の数字の配置は以下のようになる。
まるでちゃんとした問題のように見えるのだが、この状態で解けるところまで解くと、こうなる。
ほんの少ししか確定しなかった。
このやり方で大丈夫だろうか。
何とか問題を作ることができた
延々と走らせていると、とても多数のマスの数字を入れ替えたところで、ユニーク解にたどり着いた。
白マスの数字を消して、空色の背景も消すと、以下の問題となる。
偶然できたこの問題の難易度はどうだろう。あるいは、解き心地はどうだろう。 時にはまともな問題もできるのではないだろうか。
やや難しい問題だが、まあ遊べる問題ではないだろうか。
実は、偶然こんな良い問題が簡単にできる訳ではない。
この入れ替えでは、仮定しないととても解けないような問題になってしまった場合には、決まらないものとして、入れ替えを続けることにしている。
もし、仮定しても解けるものは解けるとして問題として採用してしまうと、仮定しなければ解けないような超難問がどんどんできてしまう。数字の個数が少くなってしまうと、解がユニークになったと思っても、そういう超難問になってしまう。
という訳で、入れ替えで、それなりの難易度の問題を見つけるには、延々と入れ替えを行なわないといけない。
数字が２４個の問題というのは標準的な個数の筈なのだが、すでに相当の時間がかかっているので、もうこれ以上数字を減らすのは厳しいようだ。
どうも、こんな方法では、２４個以下の問題をどんどん作るのは厳しいようだ。やはり、別の方法でないと駄目なようだ。