c++深度优先搜索解决八数码问题

在C++中，深度优先搜索（Depth-First Search，DFS）可以用于解决八数码（又称数独）问题。这是一种回溯算法的应用，通过递归的方式来尝试填充九宫格，使得每一行、每一列以及每个小宫格（3x3）内的数字都不重复，且满足1到9的范围。

以下是使用DFS解八数码问题的一个简单示例：

#include <vector>
using namespace std;

bool is_valid(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)
            return false;
    
    // 检查3x3小宫格
    int boxRow = row - row % 3;
    int boxCol = col - col % 3;
    for (int i = boxRow; i < boxRow + 3; ++i)
        for (int j = boxCol; j < boxCol + 3; ++j)
            if (board[i][j] == num)
                return false;
    
    return true;
}

void solveSudoku(vector<vector<int>>& board, int row, int col) {
    if (row == 9) { // 如果填完了所有的格子，成功解题
        cout << "Solution found:\n";
        for (auto& row : board)
            for (auto& num : row)
                cout << num << ' ';
        cout << endl;
        return;
    }

    // 对当前位置所有可能的数字进行尝试
    for (int num = 1; num <= 9; ++num) {
        if (is_valid(board, row, col, num)) {
            board[row][col] = num; // 尝试填写
            // 继续向下一个空格搜索
            solveSudoku(board, row + 1, col);
            // 回溯：如果下一层无法找到解决方案，则撤销当前决策并尝试下一个数字
            if (board[row][col] != num)
                board[row][col] = 0; // 清除并回退到上一步
        }
    }
}

// 主函数：初始化并开始搜索
int main() {
    vector<vector<int>> board(9, vector<int>(9, 0));
    // 初始化部分数字作为起始状态...
    solveSudoku(board, 0, 0);
    return 0;
}

在这个例子中，`solveSudoku`函数首先检查当前位置是否为空，然后对所有合法数字进行尝试，如果找到一个可行的数字就继续向下探索，否则回溯至上一个格子继续尝试其他数字。当填完所有格子时，找到了一个解。