The new 8-puzzle has 8 tiles as usual, but each tile may move Up, Up-Right, Right, Down-Right, Down, Down-Left, Left and Up-Left. The cost of a regular move (Up, Down, Left, or Right) is 1, and the cost of a diagonal move (Up-Right, Down-Right, Down-Left, and Up-Left) is 1.4 (approximately =1.414).
Please use the A * search method to find a solution, and show the generated search tree with marked expansion order numbers and costs along with detailed major steps and relevant explanations clearly.
The objective of the A* search algorithm is to find a path from an initial state to a goal state that minimizes the cost function $f(s)$ where
$$ f(s) = g(s) + h(s) \\[10pt] \text{where } g(s) : \text{Cost to reach } s_{n+1} \text{ from } s_{n} \\[10pt] \text{ and } h(s) : \text{Estimated cost to reach } s_{goal} \text{ from } s_{n} $$
Given an initial state $s_o \in \R^{3\times3}$, the problem can be defined recursively by the following algorithm
$$ s_{n+1} = \argmin f(s'_n)= \argmin [~h(s'_n)+g(s'_n)~] \\[10pt] s'_n \in S(s_n) $$
where $S(s_n)$ is the search space of $s_n$ and contains all the possible next states of $s_n$ as determined by the position of the empty tile.
Assumption: No swapping elements that are already in the correct position.