ホームページ目次2014-09-02(前)2014-09-15(次)

高専からのインターンがヒント数17個のナンプレ問題自動生成にチャレンジ

2014年9月13日


前回は、インターンが子供向けの言語Scratchで、ナンプレの問題の自動生成にチャレンジした話を書いた。 人工知能を使った自動生成で、ヒント数(数字の個数)が25個の問題を作ったのだが、 もっとヒント数の少ない問題を自動生成してみたいという。

でも、それは企業秘密で教えられないんだ、なんてことは全然なくて、ずいぶん前からナンプレの問題の自動生成する方法はソースコードの公開を含めて行っているのだ。だから、誰だって、ちょっとプログラムができて、ちょっとパズルが分かればできるのだ。なぜ皆やらないのだろうか。

せっかくインターンシップで、ナンプレの自動生成を習得したので、もっとヒント数の少ない場合、たとえば最も少ないヒント数17個の問題を作ってみたいという希望なのだ。

若者の夢はできるだけ叶えてあげるべきだということで、対応することにした。

ヒント数25個の問題を作るのも、17個の問題を作るのも、原理は同じなのだ。 ただし、ヒント数が減ると、問題の自動生成に成功する確率が極端に減ってしまうのだ。 なので、このまま、Scratchで挑戦する訳には行かない。 Scratchで挑戦したら、走らせても、問題ができるのは1年後とかで、インターン期間が終わってしまうのだ。

ということで、インターンが使える言語のうちで、実行速度が速い言語を聞いてみた。 とりあえず、Javaを知っているというので、Javaで自動生成をすることになった。 インターン期間が数日しか残っていなかったので、ユーザインターフェイスは全部無視して、テキストで結果を印字するだけのプログラムを作ってもらった。

基本アルゴリズムはScratchと同じなので、Scratchで書いたレベルを、Javaで書きなおしてもらった。 さらに、プログラムを高速にするためのチューニングをやってもらった。

ヒント数25の時は、ヒントの位置は全部最初に指定していたのだが、ヒント数17の場合には同じ戦略では撃沈するのだ。 それで、問題の数字の値を自動調整するだけではなく、数字の位置も自動調整するようにした。

で、ヒント数25とかで動くことを確認し、ヒント数を少しずつ減らしていったのだ。 ヒント数20までは、問題は秒速で生成できるのだ。 でもヒント数19,18となるに連れて、待ち時間が長くなったが、待っている間にできた。

そして、ついに、ヒント数17の問題ができるかどうか、確認することになったが、いつまで経過しても問題が作れない。 何か間違えたかな。 そうかも知れない。 でも、ヒント数18まで減らして大丈夫だったのだから、プログラムはミスってないと思えるのだ。

ということで、退社時間が来たので、そのまま走らせて翌朝出てきたら、結果がでていた。 その問題がこれだ。


ホームページ目次2014-09-02(前)2014-09-15(次)