利用A*算法实现八数码难题(九宫重排)的搜索。

八数码难题是一种经典的搜索问题，也称作九宫重排。该问题是将一个 $3 \times 3$ 的棋盘上的数字按照特定规则进行移动，最终达到指定的目标状态。其中初始状态和目标状态如下：

初始状态：

2 8 3 
1 6 4 
7 0 5 

目标状态：

1 2 3 
8 0 4 
7 6 5 

在移动的过程中，可以将数字 0 称为空格，将数字与空格进行交换，每次只能交换相邻的数字和空格，如图所示：

2 8 3          2 0 3          2 8 3
1 6 4    ->    1 6 4    ->    1 6 4
7 0 5          7 8 5          7 4 5

这样的移动操作可以看作是一种状态转移操作，因此可以利用搜索算法求解八数码难题。其中，A*算法是一种启发式搜索算法，可以在较短的时间内找到最优解。

A*算法的核心是利用一个估价函数来评估当前搜索状态的“好坏”，根据这个估价函数来决定下一步搜索哪些状态。对于八数码难题，可以将每个状态看作是一个 9 维的向量，每个维度表示数字 0-8 在棋盘上的位置。对于当前状态 $s$，定义 $h(s)$ 为该状态与目标状态之间的曼哈顿距离，即所有数字在当前状态与目标状态中的横向和纵向距离之和，如下所示：

2 8 3          1 2 3
1 6 4    ->    8 0 4
7 0 5          7 6 5

h(s) = 1 + 2 + 1 + 1 + 1 + 1 + 2 + 1 + 2 = 12

因此，在A*算法中，每次选择下一步搜索的状态时，选择 $f(s) = g(s) + h(s)$ 最小的状态，其中 $g(s)$ 表示从初始状态到状态 $s$ 的路径长度。同时，为了避免陷入环路，需要记录已经被访问过的状态，并且保证每个状态只被访问一次。

下面是利用A*算法求解八数码难题的Python代码：