MinとMax(ナンプレソフトをつくる)

先日問題パターンの情けないナンプレソフトをリリースしてしまいなんとかまともな問題を作ろうとしたものの、連日の飲み飲み飲み飲み飲み飲みでまったく手が出てないったらありゃしない感じで、自堕落な生活を続ける今日この頃、皆様いかがお過ごしでしょうか。

さて、飲み生活もようやく終わりが見えてきたので先日開発を再開しました。
とりあえず、今までの生成ロジックだと横方向のパターンが単純化してしまうため、なんとか乱数を使ってばらばらのパターンを導き出そうと考えました。
とはいうものの、完全にランダムで問題を作成すると完成するのに日が暮れることは必至です。
ですので、マスに数字を置くたびにナンプレのルールに基づいて発生する乱数の絞込みを行い、解として成立しない数値を排除する…という方法をとりました。
＃Ｗｅｂには信じられないほど高速で問題生成するものもありますね。世の中には頭の良い人がいるものです。

しかし、単純にマスを左上から右方向に順番に埋めていったところ、７行目あたりで行き詰まり、いつまでたっても解が生成されません。
そこで、選択のパターンを平準化する…つまり、各マスの選択可能な数字の数がなるべく同じになる(つまり、選択可能な数字の数が最大のものを選ぶ)ように数字を埋めるマスを選んでいくという方法にしてみたところ、なんとか解が生成できるようになりました。
ただ、その試行回数が３００回とか４００回とかになるためはたしてWZERO3でまともな時間で問題作成できるのか心配でした。
なんとか試行回数を減らすことが出来ないのかと考えたところ、ふと、今まで選択可能な数字の数を最大としていたものを最小にしてみたところ、なんと１〜２回で求まるようになりました。
ためしに１０万回生成させてみたところ、その平均数は１．５５程度。最大で１３回試行という結果に…。
ほとんど乱数任せの生成ロジックなのになんでだ？とよくよく考えて見たところ、実は
１．制約の少ない段階に選択の余地がないマスを埋めるため解が成立しやすい
２．後半にむけてなるべく選択の余地が多くなる方向に動く。

という２つの特徴がかみ合って、手詰まりになりにくいことが伺えました。
＃頭がわるくかつ算数が大嫌いなので数学的に導くことはできません（汗）

しかし、比較的ランダムに作成しても解が成立するってことは、ナンプレのパターンは以外と豊富なのかもしれませんね。
そういう意味でも良く出来たパズルだと思います。

しかし、もともと最大で判定していたものを最小に切り替えるだけでこうも性能に差がでるなんて…、アルゴリズムって本当に恐ろしいですね。
上記のロジックの実装は終わったものの、問題の仕上げである穴あけロジックに不満があるため、まだ公開はしていません。
もうしばらくお待ちください。