37. 解数独

🔴   🔖  数组 哈希表 回溯 矩阵  🔗 力扣 LeetCode

题目

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules :

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:


Input: 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"]]

Output: [["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"]]

Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

题目大意

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

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

解题思路

这个问题的核心是使用 回溯法（Backtracking），逐步尝试将每个空格填充数字，并检查当前的填充是否符合数独规则。如果不符合规则，则回退到之前的状态继续尝试其他可能性，直到找到一个可行解。

1. 寻找空格：

   • 遍历整个数独，找到尚未填充数字的位置（即空格 ' . '），然后开始尝试填入数字。

2. 递归填充数字：

   • 尝试将数字 1-9 依次填入空格中，并在每次填入后，检查行、列、3x3 的小方格是否仍满足数独的规则。

3. 检查有效性：

   • 每次填入一个数字后，检查当前数独的有效性（即每行、每列、每个 3x3 小方格中是否包含重复的数字）。

4. 回溯：

   • 如果当前数字不满足规则，则回退到上一步，尝试填入下一个可能的数字。
   • 如果所有可能的数字都不符合规则，则返回到上一个空格的位置，继续尝试其他可能的数字。

5. 终止条件：

   • 当所有空格都填完，并且整个数独符合规则时，递归终止，数独被解出。

复杂度分析

• 时间复杂度：回溯法的时间复杂度非常难以精确估计，因为它取决于输入数独的复杂程度。在最坏情况下，时间复杂度可能会接近 O(9^m)，其中 m 是空格的数量。因为每个空格最多可以填入 9 个数字。
• 空间复杂度：O(1)，因为数独是在原数组上修改的，且只使用了少量额外空间用于递归栈。

代码

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
	const solve = (board) => {
		for (let i = 0; i < 9; i++) {
			for (let j = 0; j < 9; j++) {
				if (board[i][j] == '.') {
					// 尝试填入 1-9
					for (let num = 1; num <= 9; num++) {
						if (isValid(board, i, j, num + '')) {
							board[i][j] = num + '';
							// 递归求解
							if (solve(board)) {
								return true;
							}
							// 回溯
							board[i][j] = '.';
						}
					}
					// 若无法填入任何数字，返回 false
					return false;
				}
			}
		}
		// 数独已解决
		return true;
	};
	solve(board);
};

// 检查在 board[row][col] 放置 num 是否有效
var isValid = function (board, row, col, num) {
	for (let i = 0; i < 9; i++) {
		// 检查行和列
		if (board[i][col] == num || board[row][i] == num) {
			return false;
		}
		// 检查 3x3 小方格
		const boxRow = 3 * ((row / 3) | 0) + ((i / 3) | 0);
		const boxCol = 3 * ((col / 3) | 0) + (i % 3);
		if (board[boxRow][boxCol] == num) {
			return false;
		}
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
36	有效的数独	[✓]	数组 哈希表 矩阵	🟠	🀄️ 🔗
980	不同路径 III		位运算 数组 回溯 1+	🔴	🀄️ 🔗