*** 2000-09-16  高橋謙一郎さんのＨＰ（掲示板）に投稿　***

皆さん、ありがとうございます。deepgreenです。

幅優先探索の結果、２５手の解は存在しないことがわかりました。
（従って、２４手の解が最長手数となります。）

補足：幅優先探索の課題は、状態を記憶するスぺース量にあります。この場合
　　　も、単純な方式では３＾２２＝３．１４＊１０＾１０となり、破綻する。
　　　しかし、状態を記憶せず、生成できれば話は変わります。

［概要］
　　問題面ではなく解のｐｕｓｈパターンをベースに考えます。
　　ｐｕｓｈパターン（ｐ）に対して２６個の０解を重ねた重複解を生成し、
　　ｐの手数が最小となるのものを代表とする。

　　５ｘ５を以下の５つの領域に分割する。

　　　　ＡＡＡＢＢ
　　　　ＡＡＡＢＢ　　この分割は高橋さんと同じですね
　　　　ＣＣＥＢＢ
　　　　ＣＣＤＤＤ
　　　　ＣＣＤＤＤ

　　ｐｕｓｈパターンｐの各領域の手数をａ、ｂ、ｃ、ｄ、ｅとする。
　　０解のパターンからｅの地点は無条件に２としてよい。

　　探索時間を速くするため、予め各領域のｐｕｓｈパターン（３＾６個）に
　　ついて、重複解もふくめて手数を求めておく。

　　ｍ＝ａ＋ｂ＋ｃ＋ｄとなる（ａ，ｂ，ｃ，ｄ）の組み合わせパターンを生
　　成する。次に、（ａ，ｂ，ｃ，ｄ）を満たすすべてのｐｕｓｈパターンｐ
　　について、ｐが代表かどうかをテストする。

　　まず、ｍ＝２２から始めて、解が１つ見つかれば、ｍを＋１して、２３，
　　２４と探索を続ける。解が存在しないところで終了すればよい。
　　（ｍ＝２２は２４手の解の確認の意味で探索）

　（ａ、ｂ、ｃ、ｄ）の選び方
　　領域の対象性から、ａ，ｂ，ｃ，ｄは以下の条件の範囲に限定してよい。

　　　　ａ＞＝ｂ，ｃ，ｄ
　　　　ａ＝ｄのとき、ｂ＞＝ｃ　
　　　　ａ＜＝１２（領域の大きさは６なので）
　　
　（結果）
　　ｍ＝２２（２４手の解）は以下のパターンを検出したが、ｍ＝２３は
　　解が存在しなかった。

　　　　ｍ＝２２の解のパターン　　　　対応する問題面
　　　　　２２２０２　　　　　　　　　　２０２２２
　　　　　００００２　　　　　　　　　　０１２１１
　　　　　１０２０１　　　　　　　　　　００１１０
　　　　　２００２０　　　　　　　　　　０２０２０
　　　　　０２２２０　　　　　　　　　　２２００１

　　探索時間は、ThinkPad（Pentium　133MHz）で　１時間４４分