The square puzzle problem is defined as follows:

On a 3x3 square, each of 8 tiles is labeled with an integer in 1..8; the same integer cannot be used twice. The 9^th tile is empty. All tiles can slide, one at a time, up, down, left, or right, swapping their position with the empty tile. Given an initial tile placing, slide tiles appropriately to achieve a given final placing.

See below for an initial state and a final (goal) state:

1	2	3
	7	4
6	8	5

--> to

1	2	3
8		4
7	6	5

Pick a representation scheme and show the initial and goal states in that scheme.

Define the state transition operators.

Define one cost function g(n) and at least two heuristic functions h₁(n) and h₂(n). Briefly compare the two heuristic functions and comment on their admissibility. Which one would you, eventually, prefer?

Apply Best-First-Search with both heuristics and briefly comment on it.

Apply A* with both heuristics and briefly comment on it.