八数码问题也称为九宫问题。在 3×3 的棋盘，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字 0 来表示），与空 格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

该问题可用A*启发式搜索算法求解。

A*算法的估价函数如下: 

        其中启发函数可选择w(n)和p(n)两种，本文以w(n)为例编写程序

本文以如下情况为例进行分析：

                若着眼在数码上，则相应的操作算子就是数码的移动，可知共有4(方向)*8(码的个数)=32 种算子，设计起来较为复杂。

                若着眼在空格上，则相应的操作算子就是空格的移动，在最理想的情况下【即空格在棋盘正中间时】，最多有4种算子【上移up,下移down,左移left，右移right】，设计较为简单。

                综上所述，本程序选择着眼于空格，使用上下左右四种操作算子进行程序编写

                可将数码在3*3棋盘上的分布抽象为一维数组，这样每次空格的移动就等价于交换一维数组种两个元素的位置，如下图所示:

 至此，数码的移动问题转换成了寻找两个待交换元素在数组中的下标并交换的问题

✅2023/12/17修正：

下图搜索树中的A(4)应该修改为A(6)

因为此时序列中共有：

2,8,3,1,6,4,(0),7,5 六个元素（标红）不在【目标位置】

1,2,3,8,(0),4,7,6,5（目标序列）

由上图的搜索树可知：

        树上的任意一个节点应该包含如下信息：

                ·该节点在树中的深度

                ·该节点的估价函数值 f(n)

                · 该节点的数码序列【抽象为一维数组】

由上表可知:

        open表中存放的是按估价函数值排序的节点，closed表存放的是每次从循环从open表中取出的第一个节点，直到取出节点的数码序列等于最终的数码序列,算法结束。 

首先明确： 八数码问题是存在无解的情况的，在编写程序时，首先就需要判断初始序列和目标序列之间的变换是否是有解的，若将无解的两个序列执行算法，算法将陷入死循环

        两个状态有无解的判断，由两个序列的逆序数奇偶性决定，若两序列的逆序数同为奇数或同为偶数，则两序列的变换有解，否则无解。

        何为逆序数？ 如何求逆序数？ 看这篇文章，这里不多赘述  逆序数文章

前一次执行UP操作，下一次迭代时应该禁用DOWN操作

前一次执行LEFT操作，下一次迭代应该禁用RIGHT操作 ，

反之亦然，目的是为了避免出现死循环

具体示例如下图:        

                总之，操作算子的选择在不考虑②中的约束条件时，其选取是的结果是十分固定的，例如0位置只能选择DOWN和RIGHT，5位置只能选择LEFT，UP和DOWN。在实际程序中可根据元素在数组中的位置+约束条件得到此次可选择的操作算子。

        经过如上分析可知，要实现算法，关键要设计出搜索树中每个节点的数据结构，本次设计的结构如下:

程序使用了numpy包，运行前请自行安装

另外在调试过程中使用了很多print语句查看结果，现已注释，若不需要请自行删除