Statistically

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

中盤の考え方

序盤の考え方のまま終盤まで引っ張るのは無理らしいことが分かった。

ということで、序盤のやり方とは違う方法を考え出さないといけない。

さて、序盤のやり方にはどんな問題があっただろか。序盤は、数字を置いたときに、どのくらい影響が出るか、効果的に決まっているかどうかを、白マスと空色マスの決まり方で判断した。この判断方法は甘かったようだ。

最大の問題は、影響を調べるものの、解の存在をまったく調べていないことである。あるいは、まったく解こうともしていないことだろう。

中盤の中途半端な状態で解く

ということを考え、中途半端に解けた(？)状態から、適当に有用な情報を抽出し利用することができないだろうか。

利用できる技術：馬鹿独(虱潰し)

さて、これらを組み合わせると、何かできないだろうか？

虱潰しは可能か

この状態で馬鹿独で虱潰しをしようとすると何が起きるだろうか？

言うまでもないことと思うが、延々と時間がかかる。

ただし、解(最後まで詰められること)はいっぱいある。 10,000,000個で止めちゃったが、まだまだ解はあるようだ。

厖大な解が存在することは確認できるようだ。しかし、

全部を調べることは解が多過ぎて困難

ならば、

最初の幾つかの解から、有益な情報を得ることはできないか。

10,000,000個も求めたら大変だろうが、 10,000個の解なら今どきのコンピュータなら簡単に求まるだろう。

さて、いったいどうすれば良いだろうか？

考えただけでは何もアイデアはでて来ないので、とりあえず馬鹿独に序盤を終えた段階の作りかけ問題データを与えてどんな解が出てくるか見てみよう。

出てくる解を調べてみよう

上図は、最初の方の解を２つ示す。

空色マス上の黒い数字が、馬鹿独開始時に与えられた数字である。

馬鹿独を実行すると、こういう盤面が延々と得られる。

良く見ると、上の方はずっと完全一致であるが、途中から違う。

さて、全部の解を単にため込んでも、データ量がいっぱいになるだけだ。この中から、重要なデータだけを抜き出したいのだが、どうすればよいだろうか。

白色マスの数字は、問題を作る側は制御できないので、情報を蒐集しても役立てることはできないと思われる。

ということは、

空色マスに関する情報だけを蒐集する

で良いと思うのだが、どうすれば良いのだろうか。

最初の10000個

最初の10000個の解について、各空色マスに入った数字の回数をカウントしてみた。

(2,0)   3-10000
(1,1)   6-10000
(5,1)   9-10000
(7,1)   4-10000
(8,2)   6-10000
(2,4)   2-2175  4-1484  5-3690  6-2651
(1,5)   1-3403  3-1735  4-2156  5-986   7-1720
(7,5)   6-3251  8-3834  9-2915
(0,6)   2-3072  3-2474  7-2088  8-2366
(1,7)   1-2129  4-1910  5-4922  7-1039
(3,7)   1-2166  5-1486  7-1778  8-1876  9-2694
(7,7)   6-1824  7-4618  8-1349  9-2209
(6,8)   4-2305  6-4503  8-3192

左端が、どの空色マスかを示し、-の前の数字がそのマスに入った数字を、-の後ろがその数字が入った回数を示している。

最初の空色５マスは10000個の解全部に対して同じ数字になった。だから、

と決めて良い訳ではない。これでも万一問題を作れるかも知れないが、間違った考えである。

(2,4)以降については、入る数字が適当にバラバラだ。

(2,4)以下について、入る数字はここに示されているものに限られると考えるのは早急過ぎる。

最初の空色５マスが、3-6-9-4-6 という入れ方をした場合の解の統計なので、最初の５マスがそれら以外の場合には、 (2,4)以下についても、ここに示されていな数字が入ることも考えられる。

さて、とりあえずそういう細かいことは無視するとして、この統計情報(？)を利用して空色マスの数字を決めることはできないだろうか。

最初の方のマスは変化なし

(2,0)〜(8,2)に入るのは、それぞれ 3,6,9,4,6ではなくて、実際にはもっと可能性がある。最初の10000個しか調べていないために、そうなっただけなので、この部分は役に立たない情報として捨てよう。

残りの８個の空色マス ( (2,4)から(6,8) ) について考えよう。それぞれのマスには、どうも３〜５種類の数字を入れられるようだ。

ここに数字がないからといって、絶対に入らないと決めてはいけない。まだ、最初の10000個しか調べていないのだから、ここに現われていない数字を入れられる可能性もある。

さて、色々な可能性がある。回数の少ない順、つまりハイフン(-)の後の数字の少ない順にならべてみた。

(1,5) 5-986
(1,7) 7-1039
(7,7) 8-1349
   . . .
(6,8) 6-4503
(7,7) 7-4618
(1,7) 5-4922

最初の方、たとえば、(1,5)のマスに５、あるいは(1,7)のマスに７を入る場合は少ないが、(1,7)に５、(7,7)に７が入る場合は多いということだ。

さて、この表で少い方を選択すべきか、多い方を選択すべきか、いずれだろうか?

次のヒントの決め方

どう選択するかは簡単だ。

できるだけ制約が厳しくなるように、絞りこむように決めるのだから、

出現回数の少ない方を選択すべき

ただし、いつも一番出現回数の少ないものを選ぶのだと、ここまでのパターンに対して一意に決まってしまうので良くない。色々な問題ができることが望ましいので、出現回数のできるだけ少ない方の３パターン程度の中から適当に選ぶのが賢いやり方かと思う。

ということで、ここは２番目に出現回数の少ない

(1,7)=7  1039

を選んでみた。

ここで虱潰しをすると、次の情報が採れた。

(2,0)   3-10000
(1,1)   6-10000
(5,1)   9-10000
(7,1)   4-9528  8-472
(8,2)   1-4106  2-3840  6-2054
(2,4)   2-3618  4-1819  5-2030  6-2533
(1,5)   1-4042  3-1952  4-2057  5-1949
(7,5)   3-1007  4-138   6-1150  7-672   8-3554  9-3479
(0,6)   2-4171  3-3725  8-2104
(3,7)   1-1222  5-3705  8-1527  9-3546
(7,7)   1-3596  4-214   6-2785  8-1651  9-1754
(6,8)   2-1536  4-2268  6-2871  8-3325

回数の少ない方は、

(7,5) 4-138
(7,7) 4-214
(7,1) 8-472

となっている。

今回も、２番目に少ないのを選んでみた。

(7,7)=4  214

この考えで大丈夫かも知れない。どんどん試してみよう。

Home

パズル問題自動生成時代

ナンプレ