题意分析

数独是一种经典的逻辑游戏，目标是在一个 $9 \times 9$ 的网格中填入数字 $1$ 到 $9$，使得每一行、每一列和每一个 $3 \times 3$ 的子方块都包含 $1$ 到 $9$ 的所有数字，且不重复。

解题思路

1. 回溯法：

   • 从左上角开始，逐个单元格尝试填入数字。
   • 对于每个空单元格，尝试填入 $1$ 到 $9$ 的数字，检查是否满足数独规则。
   • 如果填入的数字合法，则递归处理下一个单元格。
   • 如果填入的数字导致后续无解，则回溯并尝试下一个数字。

2. 数独规则检查：

   • 检查当前数字是否在当前行、当前列和当前 $3 \times 3$ 子方块中已经存在。

3. 终止条件：

   • 所有单元格都被合法填满，则找到一个解。

C++ 代码实现

#include <iostream>
#include <vector>

using namespace std;

// 检查数字 num 是否可以填入 board[row][col]
bool isValid(vector<vector<int>>& board, int row, int col, int num) {
    // 检查当前行
    for (int i = 0; i < 9; ++i) {
        if (board[row][i] == num) return false;
    }
    // 检查当前列
    for (int i = 0; i < 9; ++i) {
        if (board[i][col] == num) return false;
    }
    // 检查当前 3x3 子方块
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[startRow + i][startCol + j] == num) return false;
        }
    }
    return true;
}

// 回溯法解决数独
bool solveSudoku(vector<vector<int>>& board) {
    for (int row = 0; row < 9; ++row) {
        for (int col = 0; col < 9; ++col) {
            if (board[row][col] == 0) { // 找到空单元格
                for (int num = 1; num <= 9; ++num) { // 尝试填入 1-9
                    if (isValid(board, row, col, num)) {
                        board[row][col] = num; // 填入数字
                        if (solveSudoku(board)) return true; // 递归解决
                        board[row][col] = 0; // 回溯
                    }
                }
                return false; // 无解
            }
        }
    }
    return true; // 所有单元格填满
}

int main() {
    int T;
    cin >> T; // 读取测试用例数量
    while (T--) {
        vector<vector<int>> board(9, vector<int>(9));
        for (int i = 0; i < 9; ++i) {
            string row;
            cin >> row;
            for (int j = 0; j < 9; ++j) {
                board[i][j] = row[j] - '0'; // 将字符转换为数字
            }
        }
        solveSudoku(board); // 解决数独
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                cout << board[i][j]; // 输出结果
            }
            cout << endl;
        }
    }
    return 0;
}

代码解释

1. isValid 函数：

   • 检查数字是否可以填入指定位置，确保不违反数独规则。

2. solveSudoku 函数：

   • 使用回溯法递归解决数独问题。

3. main 函数：

   • 读取输入数据，调用 solveSudoku 解决问题，并输出结果。

复杂度分析

1. 时间复杂度：
   • 最坏情况下，回溯法的时间复杂度为 $O(9^{n})$，其中 $n$ 是空单元格的数量。
2. 空间复杂度：
   • 需要 $O(9 \times 9)$ 的空间存储数独棋盘。