跳至主要內容

37. 解数独


37. 解数独open in new window

🔴   🔖  数组 哈希表 回溯 矩阵  🔗 力扣open in new window LeetCodeopen in new window

题目

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:

![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku- by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png)

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有效的数独open in new window[✓]数组 哈希表 矩阵
980不同路径 IIIopen in new window位运算 数组 回溯 1+