Compute the tiles-out-of-place and Manhattan-distance heuristics for an 8-puzzle state, and confirm Manhattan dominates (is more informed).

Answer

goal = {1: (0, 0), 2: (0, 1), 3: (0, 2), 8: (1, 0), 0: (1, 1), 4: (1, 2), 7: (2, 0), 6: (2, 1), 5: (2, 2)} state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]] def tiles_out_of_place(s): n = 0 for r in range(3): for c in range(3): tile = s[r][c] if tile != 0 and goal[tile] != (r, c): n += 1 return n def manhattan(s): total = 0 for r in range(3): for c in range(3): tile = s[r][c] if tile != 0: gr, gc = goal[tile] total += abs(gr - r) + abs(gc - c) return total t = tiles_out_of_place(state) m = manhattan(state) print(f"tiles_out_of_place = {t}") print(f"manhattan = {m}") print(f"Manhattan dominates: {m >= t}")