The image below shows a common $8-$puzzle game. You need to transform the given scrambled configuration into

the correct placement.

For ease of implementation on a computer, we have simplified the above puzzles into numbers and saved them

as the matrix below. Specifically, you may choose to represent the blank space as either $0$ or $9.$

Requirement

You need to solve this problem using the A$*$ algorithm, and you may choose any rational heuristic to use.

$(10$ points$)$ Submission & coding Quality $(10$ points$).$

$(20$ points$)$ Briefly explain the reasoning for choosing this heuristic and how it works.

$(25$ points$)$ Pseudocode.

$(25$ points$)$ Code implementation.

$(20$ points$)$ Complexity analysis.