八数码问题广度优先C++

八数码问题是指在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字，另外一个格子为空格。空格周围的棋子可以移到空格中。给出一种初始布局和目标布局，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。广度优先搜索是一种解决八数码问题的常用算法，它可以保证找到最短路径。C++是一种常用的编程语言，可以用来实现八数码问题的算法。通过C++实现广度优先搜索算法，可以方便地输入和输出八数码问题的起始状态和终止状态，并找到最短路径。

相关问题

用c++编写用深度优先算法和广度优先算法解决八数码问题

好的，我可以为您讲解一下如何用C++编写用深度优先算法和广度优先算法解决八数码问题。

八数码问题是一种经典的搜索问题，旨在找到一种移动拼图块的方式，以使得初始状态变为目标状态。其中，每个拼图块只能移动到空格上，而且只能沿横向或纵向移动。这个问题可以使用深度优先算法和广度优先算法进行解决。

首先，我们需要定义一个八数码状态的数据结构。一种常见的表示方式是使用一个一维数组来表示状态，其中0表示空格。例如，初始状态[1,2,3,4,0,5,6,7,8]可以表示为：

1 2 3
4   5
6 7 8

接下来，我们可以使用一个搜索树来表示所有可能的状态。搜索树的根节点为初始状态，每个节点表示一个状态，其子节点是通过移动一块得到的所有可能状态。我们可以使用一个队列来实现广度优先算法，或使用递归函数来实现深度优先算法。

下面是一种使用广度优先算法解决八数码问题的C++代码实现：

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

const int N = 9;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

struct State {
    int a[N];
    int pos;
    int steps;
};

bool check(const State& s) {
    for (int i = 0; i < N; i++) {
        if (s.a[i] != i) return false;
    }
    return true;
}

void print(const State& s) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << s.a[i * 3 + j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int bfs(const State& start) {
    queue<State> q;
    vector<State> vis;
    q.push(start);
    vis.push_back(start);
    while (!q.empty()) {
        State s = q.front();
        q.pop();
        if (check(s)) return s.steps;
        for (int i = 0; i < 4; i++) {
            int nx = s.pos / 3 + dx[i], ny = s.pos % 3 + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
            State t = s;
            swap(t.a[s.pos], t.a[nx * 3 + ny]);
            t.pos = nx * 3 + ny;
            t.steps++;
            bool ok = true;
            for (int i = 0; i < vis.size(); i++) {
                if (vis[i].pos == t.pos && vis[i].a == t.a) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                q.push(t);
                vis.push_back(t);
            }
        }
    }
    return -1;
}

int main() {
    State start;
    for (int i = 0; i < N; i++) {
        cin >> start.a[i];
        if (start.a[i] == 0) start.pos = i;
    }
    start.steps = 0;
    cout << bfs(start) << endl;
    return 0;
}

这个实现中，我们定义了一个State结构体来表示八数码状态，其中a数组存储状态，pos表示空格位置，steps表示移动步数。check函数用于判断是否到达目标状态，print函数用于输出状态。

在bfs函数中，我们使用一个队列q和一个vector vis来实现广度优先搜索。每次从队列中取出一个状态，尝试通过移动一块来得到所有可能的状态，然后将未访问过的状态加入队列中。如果已经访问过，则不再加入队列。

这个实现中，我们使用了一个check函数来判断是否到达目标状态，但实际上也可以在枚举状态时直接判断。另外，我们可以使用一个pre数组来记录状态的前驱节点，以便输出路径。

接下来，我们看一下如何使用深度优先算法解决八数码问题。这个实现中，我们使用了递归函数来实现深度优先搜索。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int N = 9;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

struct State {
    int a[N];
    int pos;
    int steps;
};

bool check(const State& s) {
    for (int i = 0; i < N; i++) {
        if (s.a[i] != i) return false;
    }
    return true;
}

void print(const State& s) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << s.a[i * 3 + j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool dfs(const State& s, int depth, int limit, vector<State>& vis, stack<State>& path) {
    if (check(s)) {
        while (!path.empty()) {
            print(path.top());
            path.pop();
        }
        print(s);
        return true;
    }
    if (depth + s.steps > limit) return false;
    for (int i = 0; i < 4; i++) {
        int nx = s.pos / 3 + dx[i], ny = s.pos % 3 + dy[i];
        if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
        State t = s;
        swap(t.a[s.pos], t.a[nx * 3 + ny]);
        t.pos = nx * 3 + ny;
        t.steps++;
        bool ok = true;
        for (int i = 0; i < vis.size(); i++) {
            if (vis[i].pos == t.pos && vis[i].a == t.a) {
                ok = false;
                break;
            }
        }
        if (ok) {
            vis.push_back(t);
            path.push(t);
            if (dfs(t, depth + 1, limit, vis, path)) return true;
            path.pop();
        }
    }
    return false;
}

int iddfs(const State& start) {
    vector<State> vis;
    stack<State> path;
    for (int limit = 0; ; limit++) {
        vis.clear();
        path.push(start);
        vis.push_back(start);
        if (dfs(start, 0, limit, vis, path)) return limit;
        path.pop();
    }
    return -1;
}

int main() {
    State start;
    for (int i = 0; i < N; i++) {
        cin >> start.a[i];
        if (start.a[i] == 0) start.pos = i;
    }
    start.steps = 0;
    cout << iddfs(start) << endl;
    return 0;
}

这个实现中，我们定义了一个dfs函数来实现深度优先搜索，并使用一个limit参数来控制搜索深度。在dfs函数中，我们首先判断当前状态是否为目标状态，如果是，则输出路径并返回true。否则，如果当前深度加上移动步数已经超过了限制，则返回false。然后，我们枚举所有可能的状态，并判断是否已经访问过，如果未访问过，则递归调用dfs函数。如果递归调用返回true，则表示已经找到了目标状态，否则需要弹出当前状态。

在iddfs函数中，我们使用一个循环来不断增加限制，直到找到目标状态或搜索到最大深度为止。

这个实现中，我们使用了一个vis数组来记录已经访问过的状态，以便避免重复访问。另外，我们使用了一个path栈来记录路径，以便输出路径。在输出路径时，我们可以从栈顶往栈底依次输出状态。

需要注意的是，八数码问题并不是所有情况下都有解的。如果初始状态与目标状态不可达，则算法会一直搜索下去，直到达到限制深度为止。因此，在实际应用中，需要对问题进行判断，以避免无谓的计算。

C++用广度优先搜索解决八数码问题

八数码问题是一道经典的搜索问题，可以使用广度优先搜索进行求解。这里给出一个使用 C++ 实现的八数码问题的广度优先搜索算法。

#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;

const int N = 3; // 数码的行列数
const int M = N * N; // 数码的总个数

// 定义状态结构体
struct State {
    string s; // 数码串
    int x, y; // 0 的坐标
    int step; // 步数
    string path; // 路径

    bool operator==(const State& t) const {
        return s == t.s;
    }

    // 计算哈希值
    size_t hash() const {
        return std::hash<string>()(s);
    }
};

// 定义哈希表
struct HashTable {
    size_t operator()(const State& t) const {
        return t.hash();
    }
    bool operator()(const State& a, const State& b) const {
        return a == b;
    }
};

// 定义移动数组：上下左右四个方向
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char direction[] = {'u', 'd', 'l', 'r'};

// 判断是否合法状态
bool valid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 计算下标
int get_index(int x, int y) {
    return x * N + y;
}

// 初始化状态
State init_state() {
    string s;
    int x = 0, y = 0;
    cout << "请输入八数码初始状态（0 表示空格）：" << endl;
    for (int i = 0; i < M; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            x = N - 1;
            y = N - 1;
        } else {
            x--;
            y = i % N;
        }
        s += to_string(x * N + y); // 将坐标转化为数字串
    }
    return {s, x, y, 0, ""};
}

// 打印状态
void print_state(const State& state) {
    for (int i = 0; i < M; i++) {
        int x = state.s[i] / N;
        int y = state.s[i] % N;
        cout << state.s[i] << " ";
        if (y == N - 1) {
            cout << endl;
        }
    }
    cout << "步数：" << state.step << endl;
    cout << "路径：" << state.path << endl;
}

// 判断是否为目标状态
bool is_target(const State& state) {
    return state.s == "012345678";
}

// 搜索八数码
void bfs(State start) {
    queue<State> Q; // 存放状态的队列
    unordered_set<State, HashTable, HashTable> vis; // 存放已访问的状态的哈希表
    Q.push(start); // 将起点加入队列
    vis.insert(start); // 标记起点已被访问
    while (!Q.empty()) { // 只要队列不空，就一直搜索
        State t = Q.front(); // 取出队首状态
        Q.pop(); // 弹出队首状态
        for (int i = 0; i < 4; i++) { // 枚举四个方向
            int x = t.x + dx[i];
            int y = t.y + dy[i];
            if (valid(x, y)) { // 如果移动后的坐标合法
                int j = get_index(x, y);
                State next = t;
                swap(next.s[j], next.s[get_index(t.x, t.y)]); // 移动数码
                next.x = x;
                next.y = y;
                next.step++;
                next.path += direction[i]; // 记录路径
                if (!vis.count(next)) { // 如果移动后的状态没有被访问过
                    Q.push(next); // 将状态加入队列
                    vis.insert(next); // 标记状态已被访问
                    if (is_target(next)) { // 如果找到目标状态，输出结果
                        cout << "找到目标状态：" << endl;
                        print_state(next);
                        return;
                    }
                }
            }
        }
    }
    cout << "无解" << endl;
}

int main() {
    State start = init_state();
    bfs(start);
    return 0;
}

在这个实现中，我们定义了一个状态结构体，包含了数码串、0 的坐标、步数和路径。我们使用一个哈希表来存放已访问的状态，使用一个 queue 存放待搜索的状态。首先，我们从起点开始搜索，将起点加入队列并标记为已访问。然后，只要队列不空，就不断取出队首状态 t 并枚举四个方向。如果移动后的坐标合法，我们就可以得到移动后的状态 next，计算该状态的哈希值并查看是否已经被访问过。如果没有被访问过，我们将该状态加入队列并标记为已访问。如果找到目标状态，我们就输出结果并结束搜索。如果队列为空，说明无解。