Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- プログラムで問題を自動生成
良い問題を目指して
一応問題を作れるようになったが、 よりよい問題、遊んでもらえる問題、 さらには驚きを与えるような問題を作るには さまざまな工夫が必要になる。
ここでは、まず、表出個数(空色マスの数)を減らすことを考えよう。
今までは、表出数字が２４個を例にとって説明してきた。
ナンプレの問題では、２４個というのは、中級レベルの問題では 最も普通の個数である。多過ぎず、少な過ぎず、である。
それに、２４は、４の倍数であり、対称性の良い形、美しいバランスの良い形を 作りやすいため、好まれる。
さて、ここでは、もっと少ない表出数字について考えよう。
表出数字を減らしていくと、人間が問題を作るときでも、 次第に問題作りが困難になっていく。 しかし、やはり表出数字が少ないすっきりした問題は気持が良い。
こんなに数字の数が少なくて、それでも難しくない問題ができると、 問題を作る方だって気持が良い。
ということで、もっと少ない表出数字にチャレンジしてみよう。
まず、２４個の場合であるが、問題は非常に作りやすく、とんでもない配置でなければ、 問題はほぼ一発の試行で作成可能だ。
では、２個減らした、表出２２の次の例を調べてみよう。
ヒントを１つ減らしてみよう
実際に試してみると、失敗もせずに簡単にできてしまった。
２２マスだから、ちょっと作り難いはずなのだが、 なぜかせいぜい数回のやり直しでできてしまう。 ５０％位の確率で一発でできてしまう。
なぜだろうか。このプログラムの性能が良過ぎるのだろうか。
どうも、空色マスの配置が良いようだ。 タテ、ヨコ、ブロックのどれをとっても、空色マスは２または３個であり、 なかなかバランスが良い。
こういう風にバランスが良いと、作るのも簡単なようだ。
バランスを保ちながら、２１マスに挑戦してみよう。
次の形ではどうだろう。
さらにヒントを１つ減らしてみよう
次の問題が、１分も掛からずにできてしまった。 まだ余裕があるようだ。
どうも、予想以上に性能が良いようだ。
対称性の良い、２０マスにチャレンジしてみよう。
当然、次の形である。
実行時間
表出２０個となると、なかなか難しくなるのだが、それでもできた。
比較的易しめの問題である。
この程度だと、だいたい３０分くらいかかってしまう。 表出マスが少くなるほど時間がかかってしまう。
２０個の問題を人間が作るのは相当困難であり、 それを、３０分という、パズル作家が普通の問題をホイホイ作る程度の時間で 完成させてしまうのだから、まあたいした自動生成システムなのかもしれない。
作るのにかかる時間は、表出マスが１つ減るたびに、５〜３０倍程度長くなっている。 ２４個の場合、形にもよるが、秒単位であったのだから、だいたい１００倍時間が かかるようになってしまった。
100倍の速度向上
２００７年現在、新アルゴリズムの考案により、速度は100倍以上向上している。 本原稿の執筆は、2006年の研究成果に基づいて書いたものである。 基本的な考え方は変更はないが、自動生成の高速化に関しては劇的に進歩した。
最少表出問題
表出２０個までは、それなりの時間でできた。
さて、まだ少ない問題でも作れるようなので、挑戦してみよう。
１９個の問題を試してみよう。 形には対称性を求めた方が格好が良いので、 次の形に挑んでみた。
さて、自動生成を走らせて、結果は待っていても時間がかかりそうだから、 明日確認しよう。
（※）2007年現在、数秒で自動生成可能になっている。
次の問題が、ちゃんと出来ていた。
難易度も、易しめの中級だ。問題としても悪くなさそうだ。
時間は、どうも何時間かかかったようだ。 ちゃんと計測すればよかった。
でも、表出１９マスの問題は、ナンプレの問題集を見ても 滅多に掲載されていない。 人間が作るにはあまりにも困難なのだろうか。
表出１８への挑戦
そろそろ、このシステムの限界に近づいてしまったかも知れないが、 さらに少ない表出１８に挑戦してみよう。
当然、次の形で試してみよう。
１８個でも、ちゃんと問題ができた。
難易度も、中級の標準的なレベルである。
しかし、このくらいになると、とても時間がかかるようになる。 空色マスの配置によっては、いくら時間をかけても出来ないことが多くなってしまう。
でも、どういうパターンなら可能らしいかは、やっていると次第に分かってくる。 どのタテも、どのヨコも、どのブロックも同じ程度の空色マスがばら撒かれている のが出来やすいことは確かだ。
表出１７への挑戦
さて、もっと表出数を少なくできるのだろうか。
17=4*4+1 ということで、左図のようなパターンを考えたが、 あまりにもまとまっていて問題ができそうにないので、 もう１つ考えてみた、というかちょっとだけ変化してみた。
さて、１７個で問題は作れるだろうか。
ネット上の研究情報
実は、１７個で、点対称に拘ると、どうも不可能らしい。
証明した訳ではないのだが、いくら試してもできないのだ。
というので、ここまで作ったプログラムでの説明ではなく、 インターネットに転がっているデータで、点対称の１７個のパターンについての 記事をいくつか紹介しよう。
日本語のサイトを紹介しようと思ったのだが、 最小数の追究については、どうも日本より海外の方が熱心な気がする。 実際、英語で、まるで数学論文のようなものが簡単に見つかる。
"The Mathematics of Sudoku" は、Tom Davis氏が Sudoku について詳しく、数学的に分析したものと言える。 英語であるが、多数の図が入っているので、英文をちゃんと読まなくても かなり参考になるのではないかと思う。
その中に、16 Minimal Sudoku Puzzles という項目があり、 １７個の１つの対角線に対して線対称な問題と、 １８個の点対称な問題を示している。
パズル界全体でも、まだ、点対称な問題はヒントが１８が最小と考えられていると思う。
もう１つ、有用と思われるものを挙げておこう。
The University of Western Australia の Gordon Royle 教授の "Minimum Sudoku" が参考になると思う。
17-hint の問題をネットで集めて載せているので、参考にして欲しい。
問題が成立する最小の数を求めることは、それはそれで多いに意義がある ことかも知れないが、これを延々とやっていては問題を作る話ができなくなるので、 最小表出問題については、これで打ち切ることとする。
本サイトで公開している ナンプレ自動生成エンジンV2 を用いれば、17ヒントの問題も十分作成可能である。 もちろん、可能なヒント配置でなければならないが、プログラムの工夫で、 どんどん作り出すことも可能ではないかと思う。