2009年04月26日

[パズル]オセロ最短詰め

  
問題
黒と白のプレイヤーが二人で協力して、番面の石を黒か白一色にする最短の手順を求めよ。
石を裏返すルールはオセロのルールをそのまま採用する。

『ナノピコ教室』では、最短の9手解をひとつだけ求めるプログラムを作ってください、という問題ですが、ここでは、すべての解を求めるプログラムをC#で書いてみることにしました。
ただし、最初の一手は、どこに打っても、回転させれば同じことになるので、 3−4固定にしています。

プログラムを作っていざ実行したら、予想以上に時間がかかってしまいます。
そのため、スレッドを起動し、キーボードから Q が押されるまで、解を求め続けることにしました。

これまでこのブログに掲載してきたパズルの問題は、探索するのに深さ優先のアルゴリズムを採用していましたが、ここでは、幅優先のアルゴリズムを採用しています。こうすることで、最短手から解を表示するようにできます。

ちょっと苦労したのは、これまでのパズルは、プレイヤーはひとりだったわけですが、このパズルはプレイヤーが2人いるので、その制御に手こずりました。

実は、この文章を書きながら、プログラムを実行させているのですが、まだ全部求め終わっていません。

と、ここまで書いたら、OutOfMemoryExceptionが発生してしまいました。
プログラム内で用意しているキューがメモリを食いつぶしてしまったみたいです。 求めた結果のいくつかを検証してみましたが、合っているようなので、 考え方自体はよいと思うのですが。。。
たしかに、キューに入っている数がものすごく多いので、この数だけ、Boardオブジェクトのクローンを作っているので、メモリのバカ食いです。

10手解も含めて求めようとしていたので、これは諦めて、9手解のすべてを求めるように修正しました。

10手解まで求めようとすると、もっとメモリを使わないようにデータ構造・アルゴリズムまで含めて設計し直しが必要そうです。そこまでの気力がないので、とりあえず、このままコードを掲載します。

興味のある方、是非、直してください。


※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。


 

この記事へのトラックバックURL