BreakdownCheck

パズル問題自動生成時代　-- ナンプレ -- -- プログラムで問題を自動生成

破綻の判定が欲しい

人間が調べ尽くすのは困難

偶然にも、次の状態にたどりついたとしよう。

問題は、残りの空色マスに適当に数字を配置することで、ユニークな解とすることができるかどうかだ。

もし、どうやっても無理なら、破棄するか、何手が戻って違うことを考えないといけない。

残りは４マスなので、全ての可能性を調べることも可能だろうか。それぞれのマスに実際に入れられるのは９種類ではなく、もっと制限がついている。

7 * 5 * 7 * 7 = 1715 通り

人間がこれだけの場合を調べるのは不可能であるが、コンピュータなら大丈夫だろうか。

もし、ユニーク解がなければ、このまま頑張るのは無駄になる。逆に、ユニーク解があるのに、ここで放棄してしまっても無駄になる。実際にどうなのかを知ることが非常に重要だ。

普通なら、可能な組み合わせが1715通りだったら、それだけの問題を実際に解いてみるのが普通だろう。

しかし、別のことを考えてみよう。つまり、組み合わせの数だけ試したら、ちゃんと分かるのは確かだが、組み合わせの数が増えると大変時間がかかるだろうし、そもそも普通のやり方なので面白味がない。

そういうことは普通の人間に任せて、別のことを考えてみた。

馬鹿独の活用

何度も解くのではなく、一度解くだけで、まだ問題として使える場合が存在するのかどうか判定できないだろうか。

と思ったときに、馬鹿独? を思い出した。

これを使えば、馬鹿独式に、つまり虱潰しだけでユニーク解になる問題をごっそり蒐集できないだろうか。

実は、できるのであるが、その方法は別に記す。ここでは、虱潰しで得られた２つのユニーク解を示す。違いがあるのは、２マスだけである。

どちらも、Hardの入口くらいのレベルであろうか。

虱つぶしは役に立たないだろうか

さて、秘技という程ではないのだが、馬鹿独を活用して、ユニーク解があるかないか、もしあるなら幾つ存在するかを調べる方法について検討しよう。

まず、未決定の空色マスを、ABCD で識別する。

これにより、各マスの値いを ( A B C D ) の順に並べることで、全ての可能性を識別することができる。

直前に示した２つのユニーク解は、それぞれ

( 6 1 7 3 ) ( 6 9 2 3 )

と示すことができる。

さて、実際にどうやって調べるかについて述べよう。

馬鹿独で全部調べ尽くすとき、途中で何度か全マスが埋まることがあり、これらは解である。この解が見つかったとき、解を記憶するのではなく、(A B C D)の部分のみ記憶することにしよう。

つまり、( A B C D ) の全てのパターンについて、それぞれ何回発生したかを記録できるようにする。

要するに、次の３種類の関数を用意する。

resetCount(A,B,C,D)	Count(A B C D) = 0
incCount(A,B,C,D)	Count(A B C D) を＋１する
getCount(A,B,C,D)	Count(A B C D) を取りだす

表現がいい加減だが、意味するところは分かるだろう。

今回の場合なら、 7 * 5 * 7 * 7 = 1715 のサイズの配列を用意してもよい。どんな方法でもよいのだが、Count(A B C D) の全てのパターンについて、発生回数を数えられる仕組を作ろう。

そうしておいて、馬鹿独式に虱潰しを始める。

虱つぶしも結構有効

馬鹿独方式で虱潰しを開始して、右下の最後のマスまで埋まったら、
Count(A B C D) をインクリメント(＋１)する。

まず、

が見つかったとしよう。

Count(2 1 5 1) であるが、初期値はもちろん 0 で、今回見つかったので、＋１されて１になった。

以上の処理をしてから、また延々と調べていたら、

にぶち当った。これも、 ( 2 1 5 1 ) なので、さらに＋１することで、 Count(2 1 5 1)は２になった。つまり、この時点で、( 2 1 5 1 ) というパターンは、２つの解が存在することが分かった。つまり、 ( 2 1 5 1 ) は多重解となる問題となり、使えない。

このように調べて行くと、 Count( A B C D ) の値を３種類に分類できる。

Count(...)	意味
0	解がない
1	ユニーク解
2以上	複数解(値は多重度を示す)

と分類でき、値が１になるパターンだけが有効な問題となる。そういうパターンが見つからない場合には、既に破綻している。

今回、全ての解を1715 通りのパターンに対応させたら、

( 6 1 7 3 ) ( 6 9 2 3 )

の２パターンだけが Countが１になったので、問題として有効なのは２パターンと分かった。

馬鹿独の有効性と限界

もう一度、

を見てみよう。４つの未決定空色マスの状態だが、馬鹿独にとっては、未決定空色マスは白マスと同様に扱い、可能な全ての数字を試す。

さて、この場合、馬鹿独で解かせると、解の総数は幾つになるであろうか。

実は、ちゃんと調べてみた。といっても、プログラムが勝手に調べたのだが、 447619通りの解が存在した。

コンピュータがいくら高速といっても、 447619通りを調べ尽くすとなると、まだ結構な時間がかかる。未決定が４つでこのくらいだから、未決定が５つだと、もっともっと場合の数が増え、時間も10倍くらいかかるであろう。

つまり、馬鹿独方式では、残りの空色マスの数が少ない場合しか適用できない気がする。

解の数もさることながら、パターンの数も、最初から全てに対して配列か何かで用意しようとすると、空色マスの増加とともにパターンが激増することは間違いない。空色マスが、まだ残り10個とかで試そうと思ったら、パターンの配列だけで大量になり、システムを困らせる。そもそも走らせられなくなる。

パターンは、最初から全てを用意するのではなく、実際にでてきたパターンだけを保持するように改良するとよい。出現カウントが０のパターンは、そもそも存在しなくなるので、出現するものに対してのみ気を使えばよくなる。

この実現方法は色々考案されていて、アルゴリズム関係の書籍を見れば解説されていることがあるし、その解説をすると長くなって、パズルの本題から外れてしまいそうなので、ここでは残念ながら省略する。 WEBで検索する場合には「スパースなベクトル」などで調べると良かろう。

ということで、馬鹿独の利用についてまとめておこう。

馬鹿独方式で、ユニーク解がまだ残っているかどうか調べられる。
馬鹿独方式は、問題作りの最終段階にしか適用できない。

自動生成プログラムをまだ作っていなかった頃、途中まで問題を手作りし、最後に馬鹿独にかけて、情况を把握することをやっていた。人間が必死で読み切らなくても、馬鹿独が教えてくれるので、問題作りはこれだけでも劇的に楽になった。

でも、もっと馬鹿独の利用方法はないものだろうか。そのあたりについては、おいおい述べていく。

Home

パズル問題自動生成時代

ナンプレ