审题本题需要我们找出数独的解并打印出来时间复杂度分析本题是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。解题#includeiostream using namespace std; int v[9][9]; bool row[10][10], col[10][10], matrix[10][10][10];1main函数逻辑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; }在录入数据的时候记得把已有数据的行/列/九宫格状态更新。2dfs//深度优先搜索 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/31归为1九宫格了P1784 数独 - 洛谷