8パズルの最短での解き方 How to solve 8 Puzzle

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_B

Submission

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3610307#1

参考

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2084544#1

解法

• 各盤面を状態としたbfs

ポイント

• map<Puzzle, bool>で「その状態はすでに来たことがあるか？」を管理
• mapにPuzzleを入れるために、Puzzleには比較オペレータ "<" を定義しておく

かかった時間

• 1sec制限
• CPU: 00:33 sec

15パズルだと工夫が必要？

• 上記解法だとTLEするのだろう
• 参考実装 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2085078#1
• 8パズルの解法を出してみた→MLE
  • http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3610331#2
  • 答えが18になる（手数が多い）テストケースでMLE
  • 幅優先は状態が増えすぎるとMLEする

15 Puzzle 15パズルも解いたよ！

#AOJ 15 PuzzleをIDA*で解いたぽよ。8 Puzzleだと幅優先でいけたので「最小手数なら幅優先最高！」って思ってたら15 PuzzleではMLEして通用せず、IDA*でdfsすることに。

— peroon_cp (@peroon_cp) 2019年5月30日

• http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3611312
• 8, 15パズルの解法は下記本のラストに載っていた

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造