駒の最短移動問題

ふと引っかかった問題。
駒をある位置から別の位置に移動させる際の最短手数はいくつなのだろうか？
しばらく考えたが、これは漏れの知能レベルでは難題だ。

単純な方法

基本的にヒューリスティックに規則を見いだして場合分けすれば済む話だが、見いだしたロジックに今ひとつ自信がない。
そこで探索してチェックしようと思いつくわけだが、単純にやると、たとえば金のように6方向に動ける駒で8手先の移動まで列挙する場合、出発位置と目標位置を変える度に6^8=160万通りについて調べねばならない。まだ金は解が必ずあるだけマシだが、角や桂馬だと到達不能マスがあるからしばしば骨折り損だ。しかも飛び駒で9手先まで調べる必要は無いように思えるが、どこまで調べれば反証した(移動不能と結論していい)ことになるのか、その限界もはっきりしない。

改善

位置p1からp2に至る最小手数の手筋Tminが存在したとして、それが途中で位置pmを経由するとする。
駒の移動可能規則が一定なら、p1からpmに至る手数は、Tminにおけるp1からpmまでの手数を下回り得ない(下回るならTminが最小手数の手筋であるという仮定に矛盾する)。この事実を利用して枝刈りすると、概ね5千手未満の列挙で済むようになった。これは完全探索であり、到達不能ならば探索終了時にそれとわかる。
しかしこの便利な事実は駒の移動可能規則が一定の場合しか成立しないっぽい。将棋では駒は成ることができ、それを経由した場合も含む最短手数を知りたいのだが上記アルゴリズムのままでは解けない(と決まったわけではないが、常に解けるものなのか自明ではない)かもしれない。
今日はここまで。

雑感2

しかしこんな問題は、たいていのケースについて、人間なら一瞬で解いてしまう。これは通常なら指数関数的に爆発する探索の計算量を指数関数的に削減する手段の存在を示唆しているように思える。
たぶんそれは論理パズルを論理パズルとして解こうとする限り見えてこない類の手段だろう。
つか概ねその首根っこを掴みつつある気がするがどうなんだろ、、