ホームページ目次前の話次の話

馬鹿独による掃海作業でユニーク問題を見つける方法

2006年10月11日

前回の図を再掲しておく。 この状態から、解がユニークになる場合を網羅する方法を今日は書こう。

解のパターンを全部記憶する必要はなくて、 まだ決っていないマス (5,0), (5,1), (0,3), (1,3), (0,4), (7,4), (4,7) にだけ注目してみよう。この7個所が同じものは、問題として (つまり問題として見せる空色のマス部分)は一致するので多重解となり、 捨てなくてはならない。

まだ未決定のマスの夫々の組み合わせが何回出現するかを数えればよい。 右下のマスまで詰って完成したとき、未決定のマスがどう決ったかだけに注目し、 そのパターンが初出だったらカウントを1にし、既に出現しているパターンだったら+1するだけだ。 実に簡単だ。このやり方で、馬鹿独式に舐めつくせば、ユニーク解か、多重解かが分かる。

解が存在しないパターンは、馬鹿独式に舐め尽しても出てこない。 当然、こういうパターンもある。 だから、馬鹿独式に調べたとき、出てくる水色マスの数字パターンには、少なくとも1つは解が存在する。 つまり、問題として成立するのは、解が1つのものだけで、 複数存在してしまったパターンを捨てればよい。

ある程度決ってしまったら、あとは馬鹿独式に掃海作業をやってしまうのである。 馬鹿独は、掃海作業にはうってつけである。

このパターンだが、最初に全ての可能なパターンを用意しておくと破綻しやすい。 未決定が7マスあった場合には、最大9の7乗になる。 これは、387420489であり、あまりにも大きな数になる。 だから、出現したパターンだけを記憶するようにしないといけないので、ちょっと工夫が必要だ。

この方法で、図の場合について舐め尽すと、解総数8876のうち、解がユニークになるのは たった6パターンであることが分った。 ユニークなのが0パターンだったら、既に破綻しているので、やり直すしかない。

ユニークな6パターンが分れば、それらの中からこれはというのを選べばよい。 どれを選んでも、一応問題としては成立している。 後は、難易度、面白さ等を考えてその中から1つを選べばよいだけだ。

せっかく6つも問題ができたのだからと、全部使いたい欲張りもいるだろう。 しかし、この6つの問題は、どうしてもかなり似た問題になっていて、 同じ問題集に入れられると、「前にやったのと同じような問題だな」という悪い印象を 与えることが必至であるので、1つだけ採用して、後は潔く捨ててしまおう。 どれを選ぶかは重要な問題だが、今日はその説明を省略する。

なお、ナンプレ自動生成では、この掃海作業以前の段階でも馬鹿独を利用している。 そのうち説明しようかと思う。

これだけ説明してしまったら、自動生成プログラムを作れる人が増えるに違いない。 では、作ってみよう。

ナンプレ自動生成のプレゼン資料


ホームページ目次前の話次の話