Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- プログラムで問題を解く
しらみ潰しでも解ける
しらみ潰しの方法
人間的な解き方を説明してきたし、それと同じ方法をコンピュータを用いてはるかに高速に行なうのが、通常のナンプレを解くプログラム(ソルバー)の作り方の基本である。
しかし、人間的な解き方をプログラムするのは、それなりに面倒である。少くとも、私にとっては面倒だ。
それで、人間的な解き方ではなく、まったく非人間的な解き方を紹介しようと思う。 高速なコンピュータがあって初めて可能な解き方である。
しらみ潰し
空きマスに、可能な数字を延々と入れて、あらゆる可能性を全部試してしまう、 というとんでもないことを考えてみよう。 要するに、「しらみ潰し」をやろうということである。
文章だけでは難しいので、図を使って、手順を説明していこう。
以前と同じ以下の問題で説明する。
この問題の空きマスを左上から、右下に向けて、 以下の図の A, B, C, D, .... の順番に可能な数字を入れて調べて尽くす。
Ａマスの可能な数字を1から順に試して、入れられる数字を見つける。 １は既に右側のマスに入っているので、最初に入れられる数字は２である。
Ａマスに２を入れた状態で、Ｂマスに入れられる一番小さい数を考える。 この場合は、４になる。
Ｂマスを４に決めた状態で、次にＣマスに入れられるもっとも小さい数字を 考えてみよう。この場合、５が入る。
。。。。。。
これを延々と続けていくとどうなるだろうか？
延々とやっていくと、次の状態に達する。
しかし、赤の×が入っているマスには、入れられる数がない。 １から９まで、いずれの数も、同じ横、同じ縦、同じブロックのどこかに 存在するので、どの数字も入れられない。
要するに、破綻してしまった。
不可能になったのだから、これより先のマスを調べても意味が無い。 ここで、１手戻ろう。緑枠のマスの７をあきらめて、次に入れられる 数を探す。この場合、８が入れられる。
そして、その後、次々と決めて行くと、以下の状態にたどり着く。
しかし、もうすぐ行き詰まるので、また手を戻さないといけない。
こんなことを延々とやると、解けるはずだ。
体力勝負でナンプレを解きたい人は、ぜひこの方法を試して欲しいが、 あまりお薦めはしない。
馬鹿独
さて、上記のように、延々と調べ尽くすのは大変なようだ。 実際、どのくらい大変なのか、デモできるページが用意されているので、 見てみよう。
「馬鹿独」?というページである。
とりあえず、３問について動作確認できるようになっているので、 ぜひ遊んでみて欲しい。
実際に動作させると分かるのだが、数千〜数万回、延々と数字を 入れたり消したりすれば調べ尽くせることが分かる。
コンピュータは延々とやってくれるから良いが、 とても人間がやれる作業ではないことが分かるだろう。
このプログラム、実は表示をしているからとても時間がかかる。 いちいち数字を入れ替えるごとに表示しなければ、 速度は一気に上昇し、１秒もかからなくなる。
ということは、こんな馬鹿な方法でも解けるということだ。
馬鹿独のページには、馬鹿なJavaソースコードがあるので、参考(参笑)されたい。
また、この方法によるCプログラムの詳しい作り方は、 Cパズルプログラミング-再帰編 のナンバープレイスの部分を参照(参笑)されたい。
しらみ潰しと正当性
しらみ潰しでも何とか解を見つけられることは分かったが、 正当な問題だけではなく、正当でない問題の場合を含めて考えてみよう。 正当でない問題については、誤った問題だけではなく、 作りかけの問題についても考慮することにしよう。 実は、そのところが非常に重要になるのだが、 それについては後で詳しく解説する。
まず「解」について考えよう。 右下隅のマスまで全部ルールを満たしながら 全部のマスを埋め尽くすことができたら解である。
さて、この解がいくつ存在するかで分類してみよう。 解が求まったからといって途中で止めるのではなく、 全ての可能性を調べ尽くすまで執念深くやる。
解が０個
しらみ潰しである以上、全ての可能性は調べ尽くしている。 しかし、それでも解が無かったのだから、この問題には「解がない」と言える。 要するに、問題が間違っている。
解が１個
これは、正当な問題である。 解が１個求まっても、もう他に解がないとは保証できないので、 解が求まった後も、延々と調べることを忘れてはならない。
解が２個以上
解が２個求まったら、問題としては成立しない。 少くとも、まっとうな問題ではない。
普通、２個目が見つかったら、問題が駄目と分かるので、 そこで中断するのが普通だ。 しかし、３個目、４個目どころか、 本当は何個解があるのか知りたくなることもある。
実は、問題を作っている途中では、今まで空色で示していた一部のマス にしか数字が入っていない。 そういう作りかけの問題を解かせると、ふつう解が複数個出てくる。 そういう情况を利用できないかと考えてみるてはどうだろう。