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

馬鹿独を利用してナンプレ自動生成を行なった

2006年10月9日

馬鹿独というのをだいぶ前に発表していたのだが、 今回、自作の問題に入れ替えて再びお目にかけることにした。 これは、ナンプレ(あるいは数独とも呼ばれるらしい)を解くプログラムで、 丹念に、真面目に調べて尽す方法を採用している。 ただし、あまににも糞真面目なので、馬鹿独という名称になってしまった。

さて、今回は、このプログラムを眺めていれば、問題の自動生成の方法を 誰もが思いつくと思うのだが、どうもそうではないらしいので、 説明を加えることにした。あたり前のことを書くのは面倒なので、 途中を省略するかも知れないが、途中は適当に補完されたし。

肝心なことは、どんな問題でも、十分な時間、あるいはステップを積めば、 馬鹿独方式で必ず解くことができるのは分るだろう。 そして、この方法ならプログラムは非常に簡単だ。 延々と再帰するだけだなので、私のような初心者でも可能だ。 右下のマスまでちゃんと数字を入れることができれば、 全部のマスに数字がはいった訳で、それはルールに合致した解である。

「問題を解く」のと、「問題を作る(作問という)」のは大いに違いがある。 解ける人は沢山いても、作れる人は本当に少ない。 作問の途中の段階では、解が1つだけか、複数解を避けられない状態か、 もう解は存在しないのか、などの色々な状態が考えられる。 問題の作り方は、 ナンプレを作ってみよう! で詳しく説明しているので、そちらを見て欲しい。

初出数字が24個の問題を作るとすれば、いきなり24個は普通は置かない。 少しずつ数字を決めていき、様々な理由で決ってしまう白マス部分も決めならが 問題を作っていくわけである。 ちゃんとした問題を作るときには、24個の数字を決めたとき、解が1つでなければならない。 0個でも、2個以上でもいけない。

では、途中の段階ではどうだろうか。たとえば、24個のうちの20個の数字を決めた 段階ではどういう状態であろうか。20個の数字を決めた中途半端な状態で馬鹿独方式で 解く、あるいは調べ尽すとどういうことが分るであろうか。 複数個の解が出てくる訳である。

右の図は、水色のマスが最初に数字を置く場所で、24マスある。 これは、自動生成プログラムの途中状態である。 水色7マスの数字が決っていない。 白マスに既に数字が入っているが、そこは必然的にその数字に決ってしまう。 正確には理由はちょっと違うのだが、 とにかく白マスでも数字を決められるところは決めている。

これだけの数字が決った状態で馬鹿独式に解くと幾つの解が存在するであろうか。 自動生成プログラムでは、この解を数えている。この場合は、8876個の解が存在した。 コンピュータにとっては、この位の数のデータは扱いやすい量である。

さて、どういうアルゴリズム、策略、謀略を使ったのか、思い出してから続きを書くことにしよう。

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


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