算法题（103）：数独

审题：

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

时间复杂度分析：

本题是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 数独 - 洛谷