审题：

本题需要我们找出数独的解，并打印出来

时间复杂度分析：

本题是9*9的数独格子，所以数据量小于25，可以使用2^n的算法

思路：

方法一：深度优先搜索

首先确定搜索及插入策略：

我们采用逐个搜索插入数字1~9的策略，所以dfs的参数需要包括行数和列数。而插入需要满足的条件是行，列，九宫格都没有该数字。我们采用bool类型的row[行数][num]，col[列数][num]，matrix[行数/3][列数/3][num]来记录是否插入。

注意：

matrix表示的就是3*3的九宫格，而我们利用行数/3以及列数/3的方法可以使九宫格内的数据都被归类到一块，然后即可表示该num在九宫格内的插入状态

图示：

确定递归进入前提：

由于本题初始矩阵存在着一些给定的非0数据，所以我们遇到初始数据就直接进行下一个格子的dfs搜索即可

确定递归深入逻辑：

我们对1~9的数在当前坐标插入是否合法依次判断，若合法就将数字插入到结果数组上，并更新行，列，九宫格的bool数组状态。

不合法就继续判断下一个数字是否合法，直到循环退出了我们就返回false（因为此时所有数字都无法插入）

确定递归回溯逻辑：

由于数独只存在一个正确解法，所以我们不是对于每一次回溯都要回退插入状态的，只有当

dfs返回的是false才要回退，返回true说明找到了，不进行回退

确定递归退出逻辑：

当行数超出9时，说明全部插入成功了，直接返回true。

解题：

#include<iostream>
using namespace std;
int v[9][9];
bool row[10][10], col[10][10], matrix[10][10][10];

（1）main函数逻辑

int main()
{//录入数据for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){cin >> v[i][j];int num = v[i][j];//记录已有数字格子if (v[i][j] != 0){row[i][num] = col[j][num] = matrix[i / 3][j / 3][num] = true;}}}//搜索dfs(0, 0);//基0//输出for (auto& a : v){for (auto& b : a){cout << b << " ";}cout << endl;}return 0;
}

在录入数据的时候记得把已有数据的行/列/九宫格状态更新。

（2）dfs

//深度优先搜索
bool dfs(int rows, int cols)
{//结束条件if (rows > 8){return true;}//跳过已有数字的格子if (v[rows][cols] != 0){if (cols < 8){return dfs(rows, cols + 1);}else{return  dfs(rows + 1, 0);}}//递归for (int i = 1; i <= 9; i++){if (row[rows][i] || col[cols][i] || matrix[rows / 3][cols / 3][i]){}else{v[rows][cols] = i;matrix[rows / 3][cols / 3][i] = col[cols][i] = row[rows][i] = true;bool judge;if (cols < 8){judge = dfs(rows, cols + 1);}else{judge = dfs(rows + 1, 0);}//回溯数据if (!judge){v[rows][cols] = 0;matrix[rows / 3][cols / 3][i] = col[cols][i] = row[rows][i] = false;}else{return true;}}}return false;
}

（1）由于我们是一个个搜索，所以我们进入深层递归前需要进行判断，若列数没到9就可以进入行数不变，列数++的位置搜索，若列数超了，那就进入行数++，列数为1搜索。

（2）本题之所以从0索引开始，是为了支持行数/3和列数/3的算法，因为从1索引开始的话，我们的第三行/第三列就无法归为0九宫格，而是3/3==1归为1九宫格了

P1784 数独 - 洛谷