[パズル]碁石拾い

日本古来からある碁石を使ったパズル「碁石拾い」を解くプログラムです。

ルールは、

1.縦・横に進みながら碁石を拾ってゆく。
2.途中の石は必ず取らなければならない。
3.どこから拾い始めてもよい。
4.碁石のない場所で曲がることは出来ない。また、元の方向へ引き返すことは出来ない。

です。詳しくは、
ニコリのパズルー碁石ひろい
パズル遊びへの招待 碁石拾い

などを参照してください。



※ボード上でクリックすると石を置くことができます。

今回作成したプログラムでは、どこから拾い始めても良いということなので、石が置いてあるすべての場所に対して、その位置を開始位置として、深さ優先の探索で解を求めています。
n個の石が置いてある場合は、n回探索を行いますので、最大で n個の解が求まることになりますが(開始位置によっては、解が求まらない場合もあります)、そのなかで最も移動距離の少ない解をひとつだけ選んでいます。

SolveInnerが、引数 p を開始位置とした時の解を求めるメソッドです。ここから呼び出される下位ルーチンはありますが、その骨格はとても単純なものになっています。再帰処理の威力ですね。
なお、1回の探索では、解が求まったところで探索を終了しています(すべてのパターンを探索していない)。そのため、最適解が見つかる保証はありません。
最適解を求めようとすると、膨大な探索を行うことになり、現実的な時間で探索が終わらない可能性もあったため、このようなロジックにしています。

見つかった解を表示している処理では、石を点滅させながら順に石を拾っています。
この部分は、Silverlightのアニメーションの機能を使っても出来そうな気がしますが、コードでアニメーション機能を実現させるのは結構面倒なので、SilverlightのDispatcherTimer クラスを使って、自力で点滅させています。

以下にソースコードを示します。

※このプログラムは、そのほかのプログラムでも利用する Board, BoardCanvasクラスを利用しています。Board, BoardCanvasクラスのソースコードはこちらに掲載しています。

■Hiroigo.cs


■MainPage.xaml.cs
 
 
■MainPage.xaml
  

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