Recall that we came up with two different heuristics for the 8-puzzle by relaxing problem constraints. In an 8-puzzle, the set of valid actions are described by the following statement: A tile can move from square A to square B if A is adjacent to B and B is blank. We can generate three relaxed problems (leading to three admissible heuristic functions) by removing one or both of the above conditions: . A tile can move from square A to square B if A is adjacent to B A tile can move from square A to square B if B is blank . A tile can move from square A to square B Recall that the first relaxation gives us the sum-of-Manhattan-distances heuristic, and the third relaxation gives us the number-of-misplaced-tiles heuristic. The second relaxation leads to a relaxed problem, whose (optimal) solution is known as Gaschnig's heuristic (Gaschnig, 1979). (a) Explain why Gaschnig's heuristic is at least as accurate as the number-of-misplaced-tiles heuristic. Hint: Observe that since both are admissible heuristics, it is equivalent to showing that: 0 Number of misplaced tiles Gaschnig's heuristic