基于C++的八数码问题BFS实现：状态生成与去重方案

嘿，我来帮你搞定八数码问题的BFS实现！你的基础代码已经搭好了架子，接下来我们重点解决状态生成和冗余状态去重的问题，同时补全完整的BFS流程，让每一步生成的状态都能清晰展示出来。

核心思路梳理 #

• 状态表示：把3x3棋盘转换成字符串（比如目标状态就是"123456780"），这样既方便存储，又能快速判断状态是否重复。
• 去重机制：用unordered_set<string>记录已经探索过的状态，彻底避免重复处理同一个状态导致的冗余计算。
• 状态生成：找到空白格（0）的位置，尝试向上下左右四个方向移动，生成合法的新状态（不能移出棋盘边界）。
• BFS流程：用队列存储待处理的状态，每次取出队首状态，生成所有合法子状态，检查是否是目标状态；如果不是，就把未探索过的状态加入队列和已探索集合。

关键函数实现 #

1. 状态转换辅助函数 #

把二维数组和字符串互相转换，方便存储和展示：

// 二维数组转字符串
string stateToString(int arr[3][3]) {
    string s;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            s += to_string(arr[i][j]);
        }
    }
    return s;
}

// 字符串转二维数组
void stringToState(string s, int arr[3][3]) {
    int idx = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            arr[i][j] = s[idx++] - '0';
        }
    }
}

2. 状态生成函数 #

找到空白格的位置，生成所有合法的相邻状态：

vector<string> generateStates(string currentState) {
    vector<string> states;
    int arr[3][3];
    stringToState(currentState, arr);
    
    // 定位空白格（0）的位置
    int x, y;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (arr[i][j] == 0) {
                x = i;
                y = j;
                break;
            }
        }
    }
    
    // 四个移动方向：上、下、左、右
    int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    for (auto& dir : dirs) {
        int nx = x + dir[0];
        int ny = y + dir[1];
        // 检查是否在棋盘范围内
        if (nx >= 0 && nx < 3 && ny >=0 && ny <3) {
            // 交换空白格和相邻位置，生成新状态
            swap(arr[x][y], arr[nx][ny]);
            states.push_back(stateToString(arr));
            // 交换回去，不影响原数组的后续处理
            swap(arr[x][y], arr[nx][ny]);
        }
    }
    return states;
}

完整修改后的代码 #

我把这些逻辑整合到你的类中，调整了成员变量并补全了BFS搜索流程：

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

class Puzzle {
private:
    int initial[3][3];
    const int goal[3][3] = {{1,2,3}, {4,5,6}, {7,8,0}};
    queue<string> stateQueue;
    unordered_set<string> explored;
    
    // 二维数组转字符串
    string stateToString(int arr[3][3]) {
        string s;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                s += to_string(arr[i][j]);
            }
        }
        return s;
    }
    
    // 字符串转二维数组
    void stringToState(string s, int arr[3][3]) {
        int idx = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                arr[i][j] = s[idx++] - '0';
            }
        }
    }
    
    // 生成所有合法相邻状态
    vector<string> generateStates(string currentState) {
        vector<string> states;
        int arr[3][3];
        stringToState(currentState, arr);
        
        // 找到空白格位置
        int x, y;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (arr[i][j] == 0) {
                    x = i;
                    y = j;
                    break;
                }
            }
        }
        
        // 四个方向移动
        int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        for (auto& dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                swap(arr[x][y], arr[nx][ny]);
                states.push_back(stateToString(arr));
                swap(arr[x][y], arr[nx][ny]); // 恢复原状态
            }
        }
        return states;
    }
    
    // 展示当前状态
    void showState(string state) {
        cout << "\n--- 当前状态 ---\n";
        int arr[3][3];
        stringToState(state, arr);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }
    }
    
    // 检查是否达到目标状态
    bool isGoal(string state) {
        return state == stateToString(const_cast<int(*)[3]>(goal));
    }

public:
    void generatePuzzle() {
        cout << "\n*** 创建初始状态（输入0-8）***\n";
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cout << "输入 [" << i << "][" << j << "] 的值: ";
                cin >> initial[i][j];
            }
        }
    }
    
    // 执行BFS搜索
    void solve() {
        string startState = stateToString(initial);
        stateQueue.push(startState);
        explored.insert(startState);
        
        cout << "\n=== BFS搜索过程 ===";
        while (!stateQueue.empty()) {
            string current = stateQueue.front();
            stateQueue.pop();
            
            showState(current);
            
            if (isGoal(current)) {
                cout << "\n✅ 找到目标状态！搜索完成。\n";
                return;
            }
            
            vector<string> nextStates = generateStates(current);
            for (string s : nextStates) {
                if (explored.find(s) == explored.end()) {
                    explored.insert(s);
                    stateQueue.push(s);
                }
            }
        }
        
        cout << "\n❌ 无法到达目标状态！\n";
    }
};

int main() {
    Puzzle p1;
    p1.generatePuzzle();
    p1.solve();
    return 0;
}

代码说明 #

• 状态表示：用字符串存储状态，解决了二维数组无法直接入队/去重的问题，操作效率更高。
• 状态生成：通过定位空白格并尝试四个方向移动，确保只生成合法的相邻状态，每次交换后恢复原数组避免干扰后续操作。
• 去重机制：unordered_set<string>的查找时间复杂度是O(1)，能快速判断状态是否已被处理，彻底杜绝冗余计算。
• BFS流程：队列的层级遍历特性保证了找到的是最短路径，同时每一步都会展示当前状态，符合你要查看所有生成状态的需求。

内容的提问来源于stack exchange，提问作者afrasiyab haider