ちょっとご無沙汰してます。deepgreenです。

１３パズルの最長手数解を求めた結果を以下に報告します。

【問題の定義】

　以下の局面を最終局面とする１３パズルの最長手数を求める問題です。
　
　　　　１　２　３　＋
　　　　４　５　６　７　　　＋：ダミー（移動不可）
　　　　８　９　ａ　ｂ　　　＊：スペース
　　　　＋　ｃ　ｄ　＊　

　この１３パズルの局面の数は、１４！／２＝４３，５８９，１４５，６００通りあり、１局面を１ビットで表現
　したとしてもメモリ不足で幅優先探索では解けません。これを、２ステップサーチ＋斜軸対称性を利用して局面
　の数を削減すると、３＊１３！／２＝９，３４０，５３１，２００通りとなるが、まだとどきません。
　（高橋謙一郎さんの分析：２００４．０２．０６の書き込み）

　今のところ、これ以上の改善は思いつかないので、別のアプローチを採用した。といっても新しいものではなく
　以前に１５パズルの最長手数へのアプローチ（これは挫折した）を簡略化したもの＋上記の２ステップサーチ＋
　斜軸変換を適用しただけです。

【結果】

　・最長手数　　　　　７４手　（下記の１通り。この解は斜軸変換しても変わらない）
　　　　
　　　　　　　　　　　＊　ｂ　７　＋
　　　　　　　　　　　ｄ　ａ　６　３
　　　　　　　　　　　ｃ　９　５　２
　　　　　　　　　　　＋　８　４　１

　・探索時間　　　　約１９時間
　・使用ＰＣ　　　　ＣＰＵ：Ｐｅｎｔｉｕｍ４　１．４ＧＨｚ
　　　　　　　　　　メモリ：５１２ＭＢ　（約４００ＭＢのハッシュテーブルを使用）

　　なお、高橋謙一郎さんの１５パズルのソルバーを改造して使用させていただきました。
　　このソルバーなくして、この問題の解決はありえません。ありがとうございます。　

【解法】

（１）基本的な考え

　　すべての生成局面を記憶するだけのメモリを容易できないので、最長手数の局面に近いものを絞り込んで、個々
　　の局面を解いて、最長手数となる局面を求める。そのため、以下の様なSubGoalを設ける。

　　　　初期局面              　 SubGoal                          Goal
         (Ｘ)                 (ｓ1)        (ｓ2)                 (Ｇ)
      ＋−−−−＋　　　 　＋−−−−＋  　＋−−−−＋          ＋−−−−＋
　　　｜　　　　｜　H1　　　｜1 2 3 +｜　  ｜1 2 3 +｜   H2　　　｜1 2 3 +｜
　　　｜　　　　｜ ------> ｜4 5 6 7｜ or ｜4 5 6 7｜  ------>　｜4 5 6 7｜
　　　｜　　　　｜　　　　　｜8 9 ? *｜　  ｜8 9 ? ?｜　   　　　｜8 9 a b｜　
　　　｜　　　　｜　　　　　｜+ c ? ?｜　  ｜+ c * ?｜     　　　｜+ c d *｜
　　　＋−−−−＋　　　　　＋−−−−＋　  ＋−−−−＋　　　　　＋−−−−＋
　　　　　　　　　　　　　　注：？にはａ，ｂ，ｄが入る
　　　　　�@SubGoalは、Goalの部分解となっているように選ぶ。
　　　　　　初期局面（Ｘ）を解く過程で必ずSubGoalの(s1) (s2)のいずれかを通る。
　　　　　�ASubGoal−＞Goalでは？の部分の数字以外は移動しない。
　　　　　�BSubGoalからGoalはなるべく近くに選ぶ。
　　　　　�Cただし、SubGoalから最も遠い局面を幅優先探索で解けること。（あまりGoalに近すぎないこと）
　　　　　　このSubGoalの場合は、２ステップサーチ＋斜軸対象性を使用すれば、３＊13P10＝3,113,510,400局面
　　　　　　となり、１局面を１ビットとすると約４００ＭＢのハッシュ用メモリがあればよい。

　　　一般に、
     　　 (Ｘ)−＞(Ｇ)への最短手数を　　　　　 Ｈ
      　　(Ｘ)−＞SubGoal(Ｓ)への最短手数を　　Ｈ１
      　　(Ｓ)−＞(Ｇ)への最短手数を　　　　　　Ｈ２

　　　とすると、　Ｈ１　＜　Ｈ　＜＝　Ｈ１＋Ｈ２　となる。即ち、（Ｈ１＋Ｈ２）は（Ｘ）の上限値の１つと
　　　なっている。さらに、Ｈ１は、（Ｘ）の下限値である。（SubGoalとして部分解を選んでいるので）
　　　一方、Ｈ２は、？の数字の並びに依存してきまるが、いずれにせよ１〜５手の範囲である。つまり、

           Ｈ１　＜　Ｈ　＜＝　（Ｈ１＋５）

      となる。このことは、SubGoalを最終局面とする最長手数をｎとすると（ｎはＨ１の最大値）
　　　もとの問題の最長手数は、(ｎ＋１)手〜(ｎ＋５）手の範囲に存在することを意味する。　

　　　従って、SubGoalを最終局面とする手数ｎ〜ｎ−５の範囲の局面に絞って、もとの問題の手数を調べればよい。

（２）具体的な解法

　　�@　２ステップサーチ＋斜軸対象性を使用した探索により、SubGoalを最終局面とする奇数局面の最長手数ｏ
　　　　を求める。その結果，ｏ＝６８が得られる。
　　　　　ａ）手数ｏ　　の局面の数は、４０　　　
　　　　　ｂ）手数ｏ−２の局面の数は、２８６１
　　　　　ｃ）手数ｏ−４の局面の数は、７１１６８

    �A　ａ），ｂ），ｃ）の順に問題の生成（？をａ，ｂ，ｄに置換）と解法を行い、もとの問題が奇数局面の範囲
　　　　で最長手数となる局面を探索する。

　　　　ｅｘ．６８手の局面の例	          (p1)           (p2)          (p3)
　　　　　　　　?  *  7  +               b  *  7  +     a  *  7  +    d  *  7  +
　　　　　　　　?  ?  6  3    ----->     d  a  6  3     b  d  6  3    a  b  6  3
               c  9  5  2               c  9  5  2     c  9  5  2    c  9  5  2
               +  8  4  1               +  8  4  1     +  8  4  1    +  8  4  1

　　　　今回の場合、幸運なことに、ａ）を解いた段階で７３手（６８＋５）の解が得られた為、ｂ），ｃ）の処理は
　　　　不要となった。

　　�B　上記で求めたすべての７３手の局面(実は斜軸対称性を除くと１つ）について、７４手の局面が存在するか
　　　　どうかの検査を行う。（この手順は、２ステップサーチの最終処理と同じなので省略）
　　　　この結果、以下の１通りの局面のみが７４手であることが判明した。

           ７３手の局面              ７４手の局面
      　  　ｂ  *  7  +              *  b  7  +
　  　      ｄ ａ  6  3 　　---->     d  a  6  3
        　  c  9  5  2               c  9  5  2
         　 +  8  4  1               +  8  4  1

（３）補足

　　　１３パズルのソルバーが必要となったが、高橋謙一郎さんの１５パズルソルバーをちょっと改造して使用した。

以上