八数码问题题解

解题思路

算法选择

使用广度优先搜索（BFS）算法，因为：

1. BFS按层搜索，保证找到的解决方案是最短路径（最少交换次数）
2. 八数码问题的状态空间相对较小（9! = 362880种可能状态）
3. BFS能够系统地探索所有可能的状态转移

关键数据结构

struct qj {
    vector<vector<char>> arr;  // 当前3×3矩阵状态
    int dep;                   // 已走步数（深度）
    pair<int, int> place;      // 空白格位置
};

状态表示

使用vector<vector<char>>表示3×3矩阵状态，用集合set<vector<vector<char>>>记录已访问状态，避免重复处理。

代码实现详解

1. 初始化与输入处理

vector<vector<char>> math(3, vector<char>(3));
vector<vector<char>> goal(3, vector<char>(3));
set<vector<vector<char>>> vis;

// 定义目标状态
goal[0][0] = '1', goal[0][1] = '2', goal[0][2] = '3';
goal[1][0] = '4', goal[1][1] = '5', goal[1][2] = '6';
goal[2][0] = '7', goal[2][1] = '8', goal[2][2] = 'x';

// 读取输入并记录初始空白格位置
pair<int, int> st;
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        cin >> math[i][j];
        if (math[i][j] == 'x') {
            st.x = i;
            st.y = j;
        }
    }
}

2. BFS初始化

queue<qj> q;
qj start;
start.arr = math;
start.dep = 0;
start.place = st;
q.push(start);
vis.insert(math);

3. 方向数组定义

定义四个移动方向（上、下、左、右）：

int dx[4] = {0, 0, 1, -1};  // 行方向变化
int dy[4] = {1, -1, 0, 0};  // 列方向变化

4. BFS核心循环

while (!q.empty()) {
    auto a = q.front();
    q.pop();
    
    vector<vector<char>> now_arr = a.arr;
    int depth = a.dep;
    auto p = a.place;
    
    // 检查是否达到目标状态
    if (now_arr == goal) {
        cout << depth << '\n';
        return 0;
    }
    
    // 尝试四个方向的移动
    for (int k = 0; k < 4; k++) {
        int nx = p.x + dx[k];
        int ny = p.y + dy[k];
        
        // 检查新位置是否合法
        if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
        
        // 创建新状态并交换
        vector<vector<char>> narr = now_arr;
        swap(narr[nx][ny], narr[p.x][p.y]);
        
        // 如果新状态未访问过，加入队列
        if (vis.find(narr) == vis.end()) {
            vis.insert(narr);
            qj next;
            next.arr = narr;
            next.dep = depth + 1;
            next.place = {nx, ny};
            q.push(next);
        }
    }
}

算法流程

1. 初始化：读取初始状态，记录空白格位置
2. BFS准备：将初始状态加入队列和已访问集合
3. 状态扩展：对于每个出队状态： 如果是目标状态，返回步数否则尝试四个方向的移动对于每个合法移动，生成新状态如果新状态未访问，加入队列
4. 终止条件：找到目标状态或队列为空（无解）

复杂度分析

• 时间复杂度：O(9!) = O(362880)，最坏情况下需要遍历所有可能状态
• 空间复杂度：O(9!)，需要存储所有已访问状态