一、题目
1、算法题目
“编写程序，填写数独剩余空格，解数独。”
题目链接：
来源：力扣（LeetCode）
链接：37. 解数独 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例图：
网络异常，图片无法展示
|
示例 1： 输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示： 复制代码
二、解题
1、思路分析
这个题考虑按行解题的顺序，通过递归+回溯枚举所有可能的填法，当递归到最后的时候，仍然是合理的答案，说明我们找到了答案。
在递归的过程中，发现当前格子不能填下任何一个数字，那么就进行回溯。
2、代码实现
代码参考：
public class Solution { //九列 List<Dictionary<int, bool>> liCol = new List<Dictionary<int, bool>>(); //九行 List<Dictionary<int, bool>> liRow = new List<Dictionary<int, bool>>(); //3*3格子 九个 List<Dictionary<int, bool>> liBox = new List<Dictionary<int, bool>>(); char[][] boardAllres = null; public void SolveSudoku(char[][] board) { //判断一共有多少个数字 int hasNumCount = 0; Dictionary<int, bool> dicAllTemp = new Dictionary<int, bool>(); //创建一个键值对集合存储数字是否出现过 for (int i = 1; i <= 9; i++) { dicAllTemp.Add(i, false); } for (int i = 0; i < 9; i++) { //存储对应的九列 liCol.Add(new Dictionary<int, bool>(dicAllTemp)); //存储对应的九行 liRow.Add(new Dictionary<int, bool>(dicAllTemp)); //存储对应的九个3*3格子 liBox.Add(new Dictionary<int, bool>(dicAllTemp)); } //遍历整个集合 将已出现的数字赋值为true for (int i = 0; i < board.Length; i++) { for (int j = 0; j < board[0].Length; j++) { if (board[i][j] != '.') { int temp = board[i][j]-48; liRow[i][temp] = true; liCol[j][temp] = true; int count = (i / 3)*3 + j / 3; liBox[count][temp] = true; hasNumCount++; } } } Recursive(board, hasNumCount, 0, 0); board= boardAllres; } public bool Recursive(char[][] board, int hasNumCount,int i,int j) { //81个数字代表已经填满了 直接返回结果 if (hasNumCount==81) { boardAllres = board; return true; } for (; i < board.Length; i++) { for (j=0; j < board[0].Length; j++) { if (board[i][j] == '.') { //查出该行对应的所有未使用的数字 一次遍历填入 List<int> liRes = liRow[i].Where(e => e.Value == false).Select(e => e.Key).ToList(); foreach (var item in liRes) { //判读位于那个格子 int count = (i / 3) * 3 + j / 3; if (liCol[j][item] == false && liBox[count][item] == false && liRow[i][item] == false) { //总数+1 对应的位置赋值为true hasNumCount++; liRow[i][item] = true; liCol[j][item] = true; liBox[count][item] = true; //之所以加48为了将数字转为char类型存进去 board[i][j] =(char)(item+48); //递归 存在不符合就返回 结果为true只有一种情况 那就是已经完成了 if (Recursive(board, hasNumCount, i, 0)) { return true; } //不符合 将操作撤回到之前 hasNumCount--; board[i][j] = '.'; liRow[i][item] = false; liCol[j][item] = false; liBox[count][item] = false; } } return false; } } } return false; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ：
空间复杂度：
三、总结
遍历过程之后，进行递归和回溯枚举，这个还是很难的。
要思考好边界问题，还有回溯到当前递归层时，其他变量的复原问题。
