题目的主要信息：

• 输入已知数字的$9\ast 99*9$盘面数组，空缺位以数字0表示
• 在空位填上1-9的数字，使每一行、每一列、每一个$3\ast 33*3$方块内数字不重复

方法一：递归

具体做法：

我们用一个数组记录每行1-9是否出现过，一个数组记录每列1-9是否出现过，一个数组记录每个方块1-9是否出现过。然后我们遍历整个数组，遇到0，就将其位置加入待数字的位置数组，遇到其他数字就在上述三个数组中记录其出现过了。

然后我们递归遍历每个空缺位置，填入1-9中的每个满足在上述三个数组中都没出现过的情况，将其置为出现，然后进入下一轮递归。当所有空缺都填满了就代表结束。当遍历完1-9都找不到说明前面填错了，因此我们每个递归后面加一个回溯，将在数组中记录的出现再改回没出现，直到遇到结束标识为止。

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int> > sudoku(9, vector<int>(9, 0)); //记录数独矩阵
vector<vector<bool> > col(9, vector<bool>(9, false)); //记录每列1-9是否有被使用过
vector<vector<bool> > row(9, vector<bool>(9, false)); //记录每行1-9是否有被使用过
vector<vector<vector<bool> > > block(3, vector<vector<bool>>(3, vector<bool>(9, false))); //记录每个方块1-9是否有被使用过
vector<pair<int, int> > space; //记录空缺的位置
 
void dfs(int pos, bool& valid){ //dfs搜索每一种情况
    if(pos == space.size()){ //填充到空缺结尾，结束
        valid = true;
        return;
    }
    auto p = space[pos];
    for(int i = 0; i < 9 && !valid; i++){ //遍历1-9，尝试每个数字
        //行列块都没有这个数字才能使用
        if(!row[p.first][i] && !col[p.second][i] && !block[p.first / 3][p.second / 3][i]){
            row[p.first][i] = true;
            col[p.second][i] = true;
            block[p.first / 3][p.second / 3][i] = true;
            sudoku[p.first][p.second] = i + 1;
            dfs(pos + 1, valid); //递归找下一个
            row[p.first][i] = false; //回溯
            col[p.second][i] = false;
            block[p.first / 3][p.second / 3][i] = false;
        }
    }
}

int main(){
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++){ //输入矩阵
            cin >> sudoku[i][j];
            if(sudoku[i][j] == 0) //如果缺少，坐标加入缺少的数组
                space.push_back(make_pair(i, j));
            else{ //否则行列块都记录这个数字出现过了
                int num = sudoku[i][j];
                col[j][num - 1] = true;
                row[i][num - 1] = true;
                block[i / 3][j / 3][num - 1] = true;
            }
        }
    bool valid = false;
    dfs(0, valid);
    for(int i = 0; i < 9; i++){ //输出
        for(int j = 0; j < 9; j++){
            cout << sudoku[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，输入已经定下了是$9\ast 99*9$的矩阵，因此不管怎么递归回溯，都是常数时间
• 空间复杂度：$O(1)O(1)$，所有记录的数组都是常数空间

方法二：递归空间优化（位运算）

具体做法：

方法一我们使用9个长度的数组代表1-9是否出现过，这里我们可以改进一下，每一行每一列每一个方块用一个数就可以记录。

用该数的最后一位为表示1出现过，倒数第二位为1表示2出现过，以次类推。比如100010001就表示1、5、9出现过。然后我们用逐位异或操作(^)可以实现对某个为止出现的数字统计，也可以用逐位异或操作将其还原。

这样我们递归的时候就可以舍弃更多空间的数组，采用位运算来优化。比较1-9是否出现过时，我们用一个1左移相应数字的掩码与每个位置记录的数字做位与运算，如果位与结果有不为0，说明该位置为1，不可以添加这个数字了。

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int> > sudoku(9, vector<int>(9, 0)); //记录数独矩阵
vector<int> col(9, 0); //用数字记录每列1-9是否有被使用过
vector<int> row(9, 0); //用数字记录每行1-9是否有被使用过
vector<vector<int> > block(3, vector<int>(3, 0)); //用数字记录每个方块1-9是否有被使用过
vector<pair<int, int> > space; //记录空缺的位置

void flip(int i, int j, int num){ //将第num位由0变成1或者由1变回0
    row[i] ^= (1 << num);
    col[j] ^= (1 << num);
    block[i / 3][j / 3] ^= (1 << num);
}

void dfs(int pos, bool& valid){ //dfs搜索每一种情况
    if(pos == space.size()){ //填充到空缺结尾，结束
        valid = true;
        return;
    }
    auto p = space[pos];
    for(int i = 0; i < 9 && !valid; i++){ //遍历1-9，尝试每个数字
        int mask = 1 << i; //找打第i位
        //后续三个第i位都不能为1才代表可以使用该数字
        if(!(mask & row[p.first]) && !(mask & col[p.second]) && !(mask & block[p.first / 3][p.second / 3])){
            flip(p.first, p.second, i); //第i位置为1
            sudoku[p.first][p.second] = i + 1;
            dfs(pos + 1, valid); //递归找下一个
            flip(p.first, p.second, i); //回溯
        }
    }
}

int main(){
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++){ //输入矩阵
            cin >> sudoku[i][j];
            if(sudoku[i][j] == 0) //如果缺少，坐标加入缺少的数组
                space.push_back(make_pair(i, j));
            else{ //否则行列块都记录这个数字出现过了
                int num = sudoku[i][j];
                flip(i, j, num - 1);
            }
        }
    bool valid = false;
    dfs(0, valid);
    for(int i = 0; i < 9; i++){ //输出
        for(int j = 0; j < 9; j++){
            cout << sudoku[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(1)O(1)$，输入已经定下了是$9\ast 99*9$的矩阵，因此不管怎么递归回溯，都是常数时间
• 空间复杂度：$O(1)O(1)$，所有记录的数组都是常数空间