ALDS1_13_C: 15 Puzzle (続き4 IDA*)

反復深化とくらべて幅優先が遅いってことはない気がするんだけど

IDA*のサンプルコードを参考にして直してみた

def solve(init):
    def dfs(depth, s, prev):
        if s.d == 0:
            return s.c
        if depth + s.d > limit:
            return None

        for h in [-1, 1, -4, 4]:
            c = s.z % 4
            r = s.z // 4
            if (
                (c == 0 and h == -1)
                or (c == 3 and h == 1)
                or (r == 0 and h == -4)
                or (r == 3 and h == 4)
                or (prev == -h)
            ):
                continue

            ns = s.dup()
            ns.z += h
            ns.d -= State.MDT[ns.z][ns.b[ns.z] - 1]
            ns.d += State.MDT[s.z][ns.b[ns.z] - 1]
            ns.b[s.z], ns.b[ns.z] = ns.b[ns.z], ns.b[s.z]
            ns.c += 1
            res = dfs(depth + 1, ns, h)
            if res:
                return res

    for limit in range(init.d, 100):
        s = init.dup()
        res = dfs(0, s, 0)
        if res is not None:
            return res
    else:
        return False

26番(43手)までクリアして27番(43手)でTLE
最長は25番の44手
17番(28手)はたった 00.03s でクリア

なんでこっちのがそんなに速いの？
毎回イチからやりなおしてるのに・・・
履歴をsetに覚えさせるあたりが重かった？
それともなにか根本的におかしかったか

あとマンハッタン距離を求めてるんだから終了判定は
マンハッタン距離=0でよかった
これは無駄なことしてた

27番もローカルでやってみると12.687sだし
最終テスト28番(45手)も12.799s
書き方でなんとかなる範囲かもしれないけどまあこれくらいでいいか