[leetcode] 37. 解数独

文章目录

题目描述
解题方法
- dfs
- - java代码
  - 复杂度分析
相似题目

题目描述

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 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"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
在这里插入图片描述

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

解题方法

dfs

一看题目大家都知道用dfs，但是dfs怎么写，是一件值得思考的事情。

首先，dfs一定要有起始条件，我们填数字肯定是从头开始填，那我们需要设置dfs的起点为数组坐标（0,0）位置。有了起点那我们也得有终点吧，那终点在哪呢？当然是数组坐标的末尾了，我们取终点坐标为（9,0）好啦。

有了开始和结束条件，我们下一步就要写dfs的主要逻辑了。那到底怎么写呢？我来一步步帮大家梳理下。

在本题中，dfs就是给当前字符赋值，然后遍历下一个字符。我们遍历到的字符无非是两种，一种是'.'，一种是1~9。遍历到1~9时，此时字符是数字，我们只需要遍历下一个字符就好了；而当遍历到'.'时，我们需要给当前字符赋值，我们可以从1开始赋值，赋值后需要检查当前字符是否符合规则。如果符合，则继续往后进行dfs遍历；否则，则给当前字符赋值下一个数字。当后续dfs尝试所有数字后都不符合规范，此时就要回溯到上一个dfs，对上一个dfs的字符在剩下的数字中重新赋值。

这样一梳理，思路是不是就清晰了。什么？看完还是一个头两个大！那还是直接看代码吧。

java代码

public void solveSudoku(char[][] board) {dfs(board, 0, 0);
}public boolean dfs(char[][] board, int i, int j) {if (i == 9) {return true;}// nextI和nextJ是下一个遍历的字符位置int nextI = i;int nextJ = j;if (j == 8) {nextI++;nextJ = 0;} else {nextJ++;}if (board[i][j] != '.') {return dfs(board, nextI, nextJ);}for (char num = '1'; num <= '9'; num++) {if (isValidSudoku(board, i, j, num)) {board[i][j] = num;if (dfs(board, nextI, nextJ)) {return true;} else {// 以当前输入的数字进行后续dfs时，后续dfs返回false，则当前字符需要重新置为'.'board[i][j] = '.';}}}return false;
}// 检查当前数字是否符合数独规则
public boolean isValidSudoku(char[][] board, int i, int j, char c) {for (int row = 0; row < 9; row++) {// 行是否合法if (board[row][j] == c)return false;}for (int col = 0; col < 9; col++) {// 列是否合法if (board[i][col] == c)return false;}for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++) {// 小的3*3格子是否合法for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++) {if (board[row][col] == c)return false;}}return true;
}