c++实现

以下是C++实现八数码问题广度优先搜索的代码，其中用了STL中的队列和set数据结构：

#include <iostream>
#include <queue>
#include <set>
using namespace std;

const int target[9] = {1, 2, 3, 4, 5, 6, 7, 8, 0}; //目标状态
const int dx[4] = {-1, 0, 1, 0}; //四个方向的x坐标偏移量
const int dy[4] = {0, 1, 0, -1}; //四个方向的y坐标偏移量

struct state
{
    int board[3][3]; //棋盘状态
    int spaceX, spaceY; //空白格子的坐标
    int depth; //当前状态的深度
    int dist; //当前状态与目标状态的距离
    bool operator < (const state& s) const //重载小于号运算符，用于set排序
    {
        for (int i = 0; i < 9; i++)
        {
            if (board[i/3][i%3] == s.board[i/3][i%3]) continue;
            return board[i/3][i%3] < s.board[i/3][i%3];
        }
        return false;
    }
};

int getDist(state& s) //计算当前状态与目标状态的距离
{
    int res = 0;
    for (int i = 0; i < 9; i++)
    {
        if (s.board[i/3][i%3] == 0) continue;
        int tx = (s.board[i/3][i%3]-1) / 3;
        int ty = (s.board[i/3][i%3]-1) % 3;
        res += abs(i/3-tx) + abs(i%3-ty);
    }
    return res;
}

bool isTarget(state& s) //判断当前状态是否为目标状态
{
    for (int i = 0; i < 9; i++)
        if (s.board[i/3][i%3] != target[i]) return false;
    return true;
}

void printAns(state& ans) //输出解路径
{
    if (ans.depth == 0) return;
    printAns(ans.pre);
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cout << ans.pre.board[i][j] << " ";
    cout << endl;
}

void bfs(state& start) //广度优先搜索函数
{
    queue<state> q;
    set<state> visited;
    start.dist = getDist(start);
    q.push(start);
    visited.insert(start);
    while (!q.empty())
    {
        state cur = q.front(); q.pop();
        if (isTarget(cur))
        {
            printAns(cur);
            return;
        }
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.spaceX + dx[dir];
            int ny = cur.spaceY + dy[dir];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
            state next = cur;
            swap(next.board[cur.spaceX][cur.spaceY], next.board[nx][ny]);
            next.spaceX = nx;
            next.spaceY = ny;
            next.depth = cur.depth + 1;
            next.dist = getDist(next);
            if (visited.count(next)) continue;
            next.pre = cur;
            q.push(next);
            visited.insert(next);
        }
    }
    cout << "无解" << endl;
}

int main()
{
    state start;
    cout << "请输入初始状态：";
    for (int i = 0; i < 9; i++)
    {
        cin >> start.board[i/3][i%3];
        if (start.board[i/3][i%3] == 0)
        {
            start.spaceX = i/3;
            start.spaceY = i%3;
        }
    }
    start.depth = 0;
    bfs(start);
    return 0;
}

在运行程序时，需要输入初始状态，例如输入：

请输入初始状态：2 8 3 1 0 4 7 6 5

输出的解路径为：

1 2 3 
8 0 4 
7 6 5 

1 2 3 
8 4 0 
7 6 5 

1 2 3 
8 4 5 
7 6 0 

其中，空白格子用0表示。