12枚のノートっす

ノートPCを忘れたまま、県外に出てたっす。

あやうく死亡説が出るところだったっす。

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

15パズルっす。

相当パワーアップするんっすけど、容量が足りないっす。

方法は

[準備]

1, 2, 3, 4のパネルと空白(16)の全配置パターンについて、

1-4のパネルが正しい位置に揃うまでの最小手数を求める。

64KBの制限があるため、複数のノートカードに分割して書いておく。

[求め方]

1.初期配置の1-4のパネルと空白に注目して、ノートから、

　初期配置から1-4が揃うまでの手数を読み込む。

2.1手進めた盤面についても同様に、ノートから読み込む。(最大で4通り)

3.最も小さい手数の方に進める。

最初に準備しておけば、あとは単純っす。

これを実行するためには、たぶん10枚のノートが少なくとも必要っす。

でも分かりやすくするため、12枚でやった方が良いと思うっす。

12枚のノートに

1行あたり14*13通りの盤面の手数を

16*15行に

書いて行くと、これで全パターンが書けるっす。

524,160通りになるっす。

64進数くらいを作っておけば、文字1つが数字1つに対応するっすから、

容量に収まると思うっす。

同時に1, 5, 9, 13のパネルについても調べながら動かしていくと、

さらに手数が短くなるっすね。

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

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

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

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

ご安心くださいっす。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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