Home
パズル問題自動生成時代
ナンプレ
はじめに
プログラムで問題を解く
プログラムで問題を自動生成
- 手作りの方法
- 破綻の判定が欲しい
- 序盤の数字のばらまき方
- 多重解にならないために
- 中盤は統計的にごまかそう
- 終盤へのつなぎ方
- 良い問題を目指して
- 終盤は問題の選択
- 見かけが大切
- 隠れた工夫
- 面白さの実現について
- 自動生成プログラムのススメ
乱数の乱用だけでは限界
将来展望
- もしミリ秒で問題生成できたら
- 誰でも簡単に問題が作れたら
- 自動生成も多種多様
- 解き方を見て問題を提供
- パズル作家風の問題生成
- 自動生成プログラムの自動生成
- 多種パズルに適用可能な汎用的アルゴリズム
- いつごろ実現できるか (1)
- オープンソースでの公開
- パズル作家は何をすべきか
パズル問題自動生成時代 -- ナンプレ -- プログラムで問題を解く
人間とコンピュータの難易度感覚の差
可能な数字が１つのマスを見つける
まずは、問題を見て欲しい。 自動生成プログラムによると、レベル9となっている。
この問題を解いて楽しんで(苦しんで)くれても良いのだが、 途中まで解き進んだ次図を見て欲しい。
コンピュータには非常に簡単に決められるマスがあるが分かるだろうか。
解けたであろうか。
次図として、もっと分かりやすいヒントを与えよう。
これなら気がつくだろう。
図の緑マスが5に決まる。
理由は、5 しか可能性がないからである。 でも、これはコンピュータが、各マスに入れられる数をきちんと 管理しているからできる。 コンピュータにとっては、マスに入れられる数が1つだけになった個所を 見つけるのは非常に簡単だ。
人間の場合は、どうだろうか。
人間は、普通なら、上図のように、各マスに小さく可能な数字を書き込む ことはあまりしないだろう。少くとも、上の図のように空きマス全部に 対して書きこむのはとても面倒だ。
もちろん、電車の中で、上図のように細かい数字を全部に書きこんで解いている のも見たことがあるので、一部の人間はコンピュータのように律儀なのかも知れない。
緑マスを含む、ヨコ9マス、タテ9マス、ブロック9マスに目を配り、 1から9までのうち、8つが既出であることを確認するのは大変だ。
今は、緑マスのマスが、そのような状態(残り数字が1つ) であることを調べるのは簡単だろうが、 どのマスかを指定されずに見つけるのは相当困難だ。 少くとも、一見しただけでは先ず分からないし、 全ての空マスに対して、残り数字が1つになっている個所を捜しだすのは 面倒な作業だ。
人間にとって面倒なだけの作業は、コンピュータにとっては逆に得意である。
英語(欧米)のナンプレの解法テクニックを見ると、 この「残り数字が1つ」というテクニックを、比較的やさしいテクニックと 紹介している場合が多い。
これは、実際にしっかり遊んだ経験がなく、 その前に解法プログラムを作ってしまい、 プログラムの作りやすさの方が優先してしまった結果だと思う。
仮定して解く
仮定して解く
人間が解くとき、難しくなってどうにもならなくなった場合を考えてみよう。 そのために、それなりに難しい問題をサンプルとしよう。
この問題を最初から解いてもらっても良いのだが、 とりあえず、次図の状態まで解けたとしよう。
ここで行き詰まってしまったら、どうしたら良いだろうか。 テクニックを駆使するのは無理になったのだから、 後は当てずっぽうにやるしかないだろうか？
どこも決められそうにないので、左上隅のマスに注目することにしよう。
ここに入れられるのは、2,6,7,9 のいずれかである。 一番小さい数字「２」を入れてみよう。
このとき、「仮定している」ということが分かるように、 仮定モードが存在し、そのモードに入ると入力された数字の色が 通常とは変わるプレイヤーが存在する。
この１手を仮定して、その後を、普通のテクニックで解き進むと どうなるだろうか。もう、仮定モードに入っているので、 仮定モードの色で数字が表示される。
ここまで解き進むと、矛盾が発生する。 空色のマスには、１〜９のいずれも入れることができない。
ということで、最初に左上のマスに「２を仮定」したのが駄目だった ことが判明する。 これで、左上に入れられる可能な数の候補は、 2,6,7,9 から２を除いたもので、 6,7,9 になる。
しかし、どうもこれでは効率が悪い。何とかならぬものか。
下の空色の２マスは、２か３しか入らないので、 とりあえず下図のように仮定してみた。
仮定モードに入って解き進むと、 以下の空色マスに入れられる数字がなくなった。
ということで、２と３ の入れ方が仮定した方は無理と分かったので、 次の図が正解に繋がるはずだ。
このように、候補の数が２つしか残っていないマスの一方を仮定して、 運よく矛盾にぶつかれば、仮定した数は駄目となり、 残り候補が１つになってしまうために確定する。
これにより、問題が一歩確実に解き進むのである。
しかし、このような解き方は、人間にとってとても面倒だ。 ブラウザ上のプレイヤーで、 仮定モードがあったり、バックできる場合に限り可能な方法ではないだろうか。
仮定して解く
プログラムで解く場合、細かいテクニックを考えるのは面倒で、 それよりも、延々と虱潰しをする方が簡単なことを説明した。
虱潰しは、何のテクニックも使わず、 仮定だけに頼ったやり方といって良い。 普通は、テクニックのうち、ルールチェックのみ、あるいは 非常に簡単に実現できるテクニックだけをプログラムし、 それらでは決定できるマスがなくなった場合には、 仮定して先に進むという方法がある。
この方法は、仮定法のプログラムを知ってしまえば、 もうそれ以上頭を使う必要もない。 ここではプログラムの詳細は述べないが、とても簡単に作れる。 プログラミングの勉強の基礎レベルに過ぎない。
一手仮定
適当に未確定のマスを選択し、そのマスで可能な数字が可能か どうか調べる。そのとき、そのマスの中の数字を１つ選んだら(仮定したら)、 後は普通のテクニックで解いてみて、 矛盾すること(何もいれられないマスができた)が分かったら、 最初に仮定したマスの選択した数字は駄目だということがわかり、 その数字を可能性から消すことができる。
こういうプログラムは、とにかく簡単だ。 プログラマは、ナンプレ独得の解法テクニックに精通している 必要はまったくない。知らないといけないのは、ルール程度ですむ。
ルールで直接数字が確定するマスを決定できる程度の とても馬鹿なプログラムと、１手仮定の仕組を結合するだけで、 ほとんどの問題は解けるようになる。 ものすごい回数のループのくり返しになるが、 くり返し処理はコンピュータが勝手にやってくれるので、 気にする必要もないし、今どきのコンピュータなら十分に高速だ。
人間は単調作業が嫌い
以上の仮定による解き方を、 人間が解くときにも使えるように、「仮定モード」が用意されている プレイヤーが存在する。
しかし、仮定しては試し解きして破綻を調べる処理は、 人間にとっては大変面倒な作業であり、私にはとても耐えられない。
コンピュータにとって易しいのは、簡単な短いプログラムで 実現できる場合であろう。単調なくり返し回数は、 疲れを知らないコンピュータには関係ない。
しかし、人間は単調なくり返し処理はとても苦手である。 やっているうちに、たいてい間違いを起こす。 それに、そもそも単調な作業など、遊びで行なう気にはなれない。
いずれにしても、コンピュータ(プログラム)と、 人間とでは、難易度感覚がとても違う。
プログラマの場合、問題の難易度を、 プログラムにとっての難易度と混同している場合が少くない。