c++深度优先算法解决八数码问题代码

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。在解决八数码（也称为数独）问题时，DFS可以用来尝试填充空白格子，通过递归的方式，直到找到解决方案或者确定无法找到合法解。

下面是一个简单的C++ DFS 解决八数码问题的代码示例：

#include <vector>
using namespace std;

bool isValid(vector<vector<int>>& board, int row, int col, int num) {
    // 检查行、列和宫格是否已包含该数字
    for (int i = 0; i < 9; ++i) {
        if (board[row][i] == num || board[i][col] == num ||
            board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == num) {
            return false;
        }
    }
    return true;
}

void solveSudoku(vector<vector<int>>& board, int row, int col) {
    if (row == 9) { // 如果已经填完一行，移动到下一行
        col = 0;
        row++;
    } else if (col >= 9) { // 如果当前列已满，移动到下一列
        row++;
        col = 0;
    } else if (board[row][col] != 0) { // 如果格子已有数字，跳过此格
        return solveSudoku(board, row, col + 1);
    }

    // 遍历1到9的所有数字
    for (int num = 1; num <= 9; ++num) {
        if (isValid(board, row, col, num)) {
            board[row][col] = num; // 尝试放置数字

            // 递归处理下一个格子
            if (solveSudoku(board, row, col + 1)) {
                return true; // 找到了解决方案
            }

            // 回溯，如果当前选择导致无法解决问题，则恢复原状态并尝试下一个数字
            board[row][col] = 0;
        }
    }
    return false; // 无解，回溯到上一格
}

// 示例用法
int main() {
    vector<vector<int>> board = {{5, 3, 0, 0, 7, 0, 0, 0, 0},
                                 {6, 0, 0, 1, 9, 5, 0, 0, 0},
                                 {0, 9, 8, 0, 0, 0, 0, 6, 0},
                                 {8, 0, 0, 0, 6, 0, 0, 0, 3},
                                 {4, 0, 0, 8, 0, 3, 0, 0, 1},
                                 {7, 0, 0, 0, 2, 0, 0, 0, 6},
                                 {0, 6, 0, 0, 0, 0, 2, 8, 0},
                                 {0, 0, 0, 4, 1, 9, 0, 0, 5},
                                 {0, 0, 0, 0, 8, 0, 0, 7, 9}};
    
    if (!solveSudoku(board, 0, 0)) {
        cout << "No solution exists." << endl;
    } else {
        for (const auto& row : board) {
            for (int num : row) {
                cout << num << " ";
            }
            cout << endl;
        }
    }

    return 0;
}