题目的主要信息：

已知9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。

方法一：

采用递归。九宫格里一共有81个数字，给这些数字编号为0、1、2……80，从第0个数开始递归，当最后一个数字递归完后结束递归。用dfs进行递归，check函数判断当前填充的值是否满足每行每列不重复、且九宫格内不重复的条件。

dfs进行递归时，首先判断当前的值是否为0，如果是0，则需要推算当前值是1-9中的哪一个，用枚举方法依次尝试往下递归，如果flag为true，结束整个递归，否则恢复当前值为0，需要回溯；如果当前值不是0，直接往下一个位置递归。当遍历位置的编号为81时，表示0-80数字都已经推算完了，此时输出整个盘面，并置flag为true结束递归。 alt

具体做法：

#include <iostream>

using namespace std;

int num[9][9];//用于保存9x9盘面
bool flag = false;//flag为true时表示推算完成，结束递归

bool check(int n){//判断当前位置的值是否满足条件
    int h = n / 9;//行号
    int l = n % 9;//列号
    for (int i = 0; i < 9; ++i){//同一列中不能有重复
        if (i != h && num[i][l] == num[h][l]){
            return false;
        }
    }
    for (int j = 0; j < 9; ++j){//同一行中不能有重复
        if (j != l && num[h][j] == num[h][l]){
            return false;
        }
    }
    for (int i = h / 3 * 3; i < h / 3 * 3 + 3; ++i){//九宫格内不重复
        for (int j = l / 3 * 3; j < l / 3 * 3 + 3; ++j){
            if ((i != h || j != l) && num[i][j] == num[h][l]){
                return false;
            }
        }
    }
    return true;
}

void dfs(int n)
{
    if (n == 81){//如果已经递归到右下角，输出整个盘面，并置flag为true，结束递归
        for (int i = 0; i < 9; ++i){
            for (int j = 0; j < 8; ++j){
                cout << num[i][j] << ' ';
            }
            cout << num[i][8] << endl;
        }
        flag = true;
        return;
    }
    int h = n / 9;//行号
    int l = n % 9;//列号
    if (num[h][l] == 0){//如果当前位置为0，说明需要推算
        for (int i = 1; i <= 9; ++i){//枚举1-9的数字，判断哪个满足条件
            num[h][l] = i;
            if (check(n)){//判断当前数字是否满足条件
                dfs(n + 1);//如果满足条件继续往下递归
                if (flag){//如果flag为true表示整个盘面的递归结束了
                    return;
                }
            }
        }
        num[h][l] = 0;//需要回溯，恢复num[h][l]的值为0
    }else{//当前位置不为0，往下一格递归
        dfs(n + 1);
    }
}

int main()
{
    for (int i = 0; i < 9; ++i){
        for (int j = 0; j < 9; ++j){
            cin >> num[i][j];//输入9x9盘面
        }
    }
    dfs(0);//从左上角开始递归
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，盘面大小为9x9，是常数。
空间复杂度： $O (1)$ ，只用了9x9的常数空间。

方法二：

整体思想和方法一相同，简化了check函数。用row[9][9]记录每一行中有哪些数字，col[9][9]记录每一列有哪些数字，用block[3][3][9]记录九个九宫格中有哪些数字，输入9x9的盘面时，同时初始化row、col、block的值，若当前的值在i行、j列，值为num，则row[i][num-1]、col[j][num-1]、block[i/3][j/3][num-1]置为1，表示第i行已经有了数字num、第j列已经有了数字num，该位置所在的九宫格久了数字num。这样我们就可以简化check函数，判断当前的赋值是否满足条件时，如果row[h][num-1] == 1||col[l][num-1] == 1|| block[h/3][l/3][num-1]==1表示该数字在行或列或九宫格已经出现过了，不符合条件，返回false;否则，返回true。

需要注意的是，如果check函数返回true，需要更新row、col、block的值。同时，如果递归失败了，需要回溯row、col、block的值，以免影响递归。

具体做法：

#include <iostream>

using namespace std;

int num[9][9];//用于保存9x9盘面
int row[9][9]={0};
int col[9][9]={0};
int block[3][3][9]={0};
bool flag = false;//flag为true时表示推算完成，结束递归

bool check(int n,int num){//判断当前位置的值是否满足条件
    int h = n / 9;//行号
    int l = n % 9;//列号
    if(row[h][num-1] == 1||col[l][num-1] == 1|| block[h/3][l/3][num-1]==1){
        return false;
    }
    return true;
}

void dfs(int n){
    if (n == 81){//如果已经递归到右下角，输出整个盘面，并置flag为true，结束递归
        for (int i = 0; i < 9; ++i){
            for (int j = 0; j < 8; ++j){
                cout << num[i][j] << ' ';
            }
            cout << num[i][8] << endl;
        }
        flag = true;
        return;
    }
    int h = n / 9;//行号
    int l = n % 9;//列号
    if (num[h][l] == 0){//如果当前位置为0，说明需要推算
        for (int i = 1; i <= 9; ++i){//枚举1-9的数字，判断哪个满足条件
            num[h][l] = i;
            if (check(n,i)){//判断当前数字是否满足条件
                //更新每行、每列、每九宫格值的信息
                row[h][i-1] = 1;
                col[l][i-1] = 1;
                block[h/3][l/3][i-1] = 1;
                dfs(n + 1);//如果满足条件继续往下递归
                if (flag){//如果flag为true表示整个盘面的递归结束了
                    return;
                }
                //回溯
                row[h][i-1] = 0;
                col[l][i-1] = 0;
                block[h/3][l/3][i-1] = 0;
            }
        }
        num[h][l] = 0;//需要回溯，恢复num[h][l]的值为0
    }else{//当前位置不为0，往下一格递归
        dfs(n + 1);
    }
}

int main()
{
    for (int i = 0; i < 9; ++i){
        for (int j = 0; j < 9; ++j){
            int temp;
            cin >> num[i][j];//输入9x9盘面
            temp = num[i][j];
            if(temp!=0){//记录每行、每列、每九宫格值的信息
                row[i][temp-1] = 1;
                col[j][temp-1] = 1;
                block[i/3][j/3][temp-1] = 1;
            }
        }
    }
    dfs(0);//从左上角开始递归
    return 0;
}

复杂度分析：

时间复杂度： $O (1)$ ，盘面大小为9x9，是常数。
空间复杂度： $O (1)$ ，只用了9x9的常数空间。

题解 | #Sudoku#

题目的主要信息：

方法一：

方法二：