数独游戏九宫格回溯算法C++

### C++ 实现数独游戏九宫格回溯算法

为了实现数独游戏的解决过程，可以采用回溯算法来尝试不同的可能性并找到唯一解。下面是一个完整的C++代码示例，用于求解给定的部分填充好的数独谜题。

#### 完整代码示例

#include <iostream>
using namespace std;

const int N = 9;
bool isSafe(int board[N][N], int row, int col, int num);

// 打印解决方案
void printSolution(int board[N][N]) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
            cout << board[i][j] << " ";
        cout << endl;
    }
}

// 查找未分配位置
bool findEmptyLocation(int board[N][N], int &row, int &col) {
    for (row = 0; row < N; ++row)
        for (col = 0; col < N; ++col)
            if (board[row][col] == 0)
                return true;
    return false;
}

// 检查num是否已经在当前行使用过
bool usedInRow(int board[N][N], int row, int num) {
    for (int col = 0; col < N; ++col)
        if (board[row][col] == num)
            return true;
    return false;
}

// 检查num是否已经在当前列使用过
bool usedInCol(int board[N][N], int col, int num) {
    for (int row = 0; row < N; ++row)
        if (board[row][col] == num)
            return true;
    return false;
}

// 检查num是否已经被使用在指定3x3方框内
bool usedInBox(int board[N][N], int boxStartRow, int boxStartCol, int num) {
    for (int row = 0; row < 3; ++row)
        for (int col = 0; col < 3; ++col)
            if (board[row + boxStartRow][col + boxStartCol] == num)
                return true;
    return false;
}

// 检查当前位置放置num是否安全
bool isSafe(int board[N][N], int row, int col, int num) {
    return !usedInRow(board, row, num) &&
           !usedInCol(board, col, num) &&
           !usedInBox(board, row - row % 3 , col - col % 3, num);
}

// 尝试解决问题
bool solveSudoku(int board[N][N]) {
    int row, col;
    
    // 如果没有空位，则已经解决了整个板面
    if (!findEmptyLocation(board, row, col))
        return true;

    // 对于每一个可能的数字...
    for (int num = 1; num <= 9; ++num) {

        // ...如果它可以在该处被安全地放置，
        if (isSafe(board, row, col, num)) {

            // 放置这个数字，并假设它是正确的解答的一部分
            board[row][col] = num;

            // 继续尝试完成其余部分
            if (solveSudoku(board))
                return true;

            // 后退一步：移除最后放置的那个数字因为它不是有效的选择
            board[row][col] = 0;
        }
    }

    // 触发回溯机制
    return false;
}

// 主函数入口点
int main() {
    int grid[N][N] = {{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(grid) == true)
        printSolution(grid);
    else
        cout << "No solution exists";

    return 0;
}

此程序定义了一系列辅助功能来帮助验证候选值的安全性以及寻找下一个空白单元的位置。核心逻辑位于`solveSudoku`函数内部，其中包含了递归调用以探索所有潜在路径直到发现有效解为止[^1]。