15パズル・リターンズっす

勝手に「ペライニー」作って、送りつけてるっす。

NO!と言われる前に送りつけるっす。

何の機能もない、ただの基本プリムの塊っす。

ご安心くださいっす。

どうもぺんぎんっす( ◎v◎ )

随分前にやった、15パズル大会で作ったスクリプトの改造っす。

やろうやろうとは思ってたんっすけど、手が出てなかったっす。

今回、改造するにあたっての方針っす。

1.サイズが大きすぎるので、まずは15パズル→8パズルにする。

2.そのあとは8パズルを頑張って解く。

これは以前と全く同じっす。

スピードと手数と容量を考えていくと、結局これになったっす。

1.の部分がうまく作れれば、かなりの時間と手数の短縮になる予感っす。

というのも、8パズルに持っていくまでの過程は「幅優先探索」で作ってあるっす。

「反復深化探索」で書くとイイ感じになると予想してるっす。

大事な「枝刈り」のところの評価方法は、マンハッタン距離を採用っす。

8パズルにする=外側の1, 2, 3, 4, 5, 9, 13を確定させる

っていうことを考えると、そのほかのコマは「どうでも良い」っすから、

過程で、その「どうでも良いコマ」をかなりの頻度、動かす必要があるっす。

これを使うと、別の何かうまい評価方法がありそうな感じっす。

ま、作りながら考えるっす。