引自：启发式搜索解决八数码问题_哔哩哔哩_bilibili

#include<queue>
#include<iostream>
#include "math.h" 
#include "stdlib.h"  
#include<stack>
#define num 9
//伪代码
/*
1 读取初始状态和目标状态，通过逆序数奇偶性判断能否到达。
2 将初始节点压入open表中
3 取出open表中估计值最小的节点，放入close表
4 判断该节点是否为目标节点，不是的话，拓展该节点，将子节点放入open表，返回上一步
5 将该节点压入栈中，并将指针指向父节点
6 如果父节点不为空，继续5
7 如果栈不为空，出栈并输出该节点。 
*/ 
using namespace std;
struct Node{
    int state[9];  //用一维数组存储方阵 
    struct Node* parent;
    int value;
    int depth;
    friend bool operator < (Node A, Node B) //按照value值+depth值小的方案构造优先级队列
    {
        return A.value+A.depth > B.value+B.depth ;//最小优先队列 
    }
};

priority_queue<Node> openTable;     //优先级队列，open表
queue<Node> closeTable;     //普通队列，close表
stack<Node> Path;     //最终路径，用栈存储 
int count1=0,count2=0; //用来判断两个路径的奇偶性。
int  judge(Node& S,Node& G){
    /*初始化*/
    S.parent=NULL;  S.depth=0;  S.value=0;
    G.parent=NULL;  G.depth=0;  G.value=0;   
     cout<<"请输入初始状态\n";
     for(int i=0;i<num;i++)
         cin>>S.state[i];
     cout<<"请输入目标状态\n";
      for(int i=0;i<num;i++)
          cin>>G.state[i];        
          // 将方阵变成线性数列后，计算初始状态和目标状态的逆序数奇偶性是否一致判断是否有解，一致则有解，否则无解。
      for(int i=0;i<=num-2;i++)  
          for(int j=i+1;j<num;j++)
            if(S.state[i]>S.state[j]&&S.state[i]*S.state[j]!=0) 
                count1++; 
       for(int i=0;i<=num-2;i++)
          for(int j=i+1;j<num;j++)
            if(G.state[i]>G.state[j]&&G.state[i]*G.state[j]!=0)
                count2++;
       if(count1%2==count2%2)
       {
           return 1;
            
       }
           return 0;
}

int value(Node A,Node G)//  计算每个数字当前状态与最终状态的曼哈顿距离 之和作为代价 
{
    int count=0,begin[3][3],end[3][3];           //count记录所有棋子移动到正确位置需要的步数
    for(int i = 0; i < num; i++){
        begin[i/3][i%3]=A.state[i];  //将一维数组的值转赋值给二维数组 
        end[i/3][i%3]=G.state[i];   //将一维数组的值转赋值给二维数组 
    }
    for(int i = 0; i < 3; i++)   //检查当前图形的正确度
        for(int j = 0; j < 3; j++)
        {
            if(begin[i][j] != end[i][j])
            {
                for(int k=0; k<3; k++)
                    for(int w=0; w<3; w++)
                        if(begin[i][j] == end[k][w])
                            count = count + fabs(i-k*1.0) + fabs(j-w*1.0); //累加计算每个数字当前状态与最终状态的曼哈顿距离 
            }
            else{
                continue; 
            }
        }
    return count +A.depth;   //返回估计值 

}

bool equal(Node S, Node G)  //判断两个方阵是否相等。 
{
    for (int i = 0; i <= 8; i++)
    {
        if (S.state[i] != G.state[i])
        {
            return false;
        }
    }
    return true;
}

//产生新节点，加入OPEN表
void creatNode(Node& S, Node G)
{
    /* 计算原状态下,空格所在的行列数，从而判断空格可以往哪个方向移动 */
    int blank; //定义0的下标
    for(blank=0;blank<9&&S.state[blank]!=0;blank++) ;//找到0的位置 
    int x =blank / 3, y = blank % 3; //获取0所在行列编号
    for (int d = 0; d < 4; d++) //找到S扩展的子节点，加入open表中
    {   
        int newX=x,newY=y;//新0坐标
        Node tempNode;
        /*移动数字0*/
        if(d==0)  newX = x -1;  //向左 
        if(d==1)     newY = y -1;  //向下 
        if(d==2)  newX = x +1;   //向右 
        if(d==3)     newY = y +1;   //向上 
        int newBlank = newX * 3 + newY; //0新的位置
        if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3) //如果移动合法
        {
            /* 交换格子的内容*/
            tempNode = S;
            tempNode.state[blank] = S.state[newBlank];
            tempNode.state[newBlank] =0;
            if ( S.parent!=NULL&&(*S.parent).state[newBlank] == 0) //如果新节点和爷爷节点一样，舍弃该节点
            {
                continue;
            }
            /* 把子节点都加入open表中 */
            tempNode.parent = &S;
            tempNode.value = value(tempNode, G);
            tempNode.depth = S.depth + 1;
            openTable.push(tempNode);
        }
    }
}

int main()
{
    Node S0,Sg;  // S0 初始状态  Sg 最终状态 
    if(!judge(S0,Sg))  
    {cout<<"此题无解！";
        return 0;
    }
        openTable.push(S0);   //入队  将初始节点压入open表 
        while (true)
        {
            closeTable.push(openTable.top()); //将open表中优先级最高(估计值最小)的元素压入close表中
            openTable.pop(); //剔除open表中优先级最高的元素
            if (!equal(closeTable.back(), Sg)) //如果当前棋局与目标棋局不相同，则拓展当前节点，
            {
            creatNode(closeTable.back(), Sg);
            }
            else
            {
                break;
            }
        }
        Node tempNode;   //临时变量暂存队前数据
        tempNode = closeTable.back();  //back  返回队列的最后一个元素即最后入队的元素 
        while (tempNode.parent != NULL)
        {
            Path.push(tempNode);//入栈 
            tempNode = *(tempNode.parent);//指向父节点
        }
        Path.push(tempNode);
        cout << "至少要移动" << Path.size() - 1 << "步" << endl;
        /* 输出方案 */
        while (Path.size() != 0)
        {
            for (int i = 0; i <= 8; i++)
            {
                cout << Path.top().state[i]<<" ";
                if((i+1)%3==0)
                    cout <<endl;                
            }
            Path.pop();
            cout<<"-------"<<endl; 
            cout << "\n";
        }    
    return 0;
}