ALDS1_13_B: 8 Puzzle

ふつうは15パズルなやつの3x3版
たぶん計算量がそれほどでもないって意味

ハッシュと幅優先探索を使う
幅優先はわかる
この手のやつは深さ優先でやるととんでもない深みにはまって
帰ってこないということはこの間何かで教訓を得た
ハッシュってなんだ何に使うんだ

ちょっとほか考えよう
盤面は3x3の配列で覚えることにしよう
で、0の場所を覚えておくのがいいのかな
0が上下左右どっちに動くかをキューに入れつつ盤面を変えていく
いや、盤面をキューに入れるのがいいのか？どっちだ？盤面かな？
で盤面が[[1,2,3],[4,5,6],[7,8,0]]になったらおしまい

あ、ここでハッシュ使えるかな終わった判定に
いやそんな局所的に使うわけではあるまい
盤面をハッシュにすると・・・？
一度出てきた盤面が再度出てきたときに探索を打ち切る、ってのができるか
そうかそれだなきっとな

どんなハッシュ関数を作ればいい？
単純には9桁の整数ってのも考えられるけど10億通り分のハッシュ覚える？
メモリ足りないよ
8までしか数字がないことを考慮してもまだ4億通り近くある
それより絞れる・・・？
1ビットで表せばメモリ足りるけど
あ、9マスのうち8個決まれば残り1個も決まるから
0から8の数字を8個覚えられればいいのか
それなら4300万通りくらいだからバイトの配列なら40MBで済む
そういうことでいいんだろうか

それくらいにして探索の方考えよう
ハッシュは別にsetとかdictでも代用できるだろうし