解数独

难度:

标签:

题目描述

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

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

数字 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] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

代码结果

运行时间: 528 ms, 内存: 15.1 MB

/*
  思路：
  使用Java Stream API 解决数独问题。
  1. 使用Stream对板中的元素进行过滤和映射。
  2. 在尝试放置每个数字时，使用Stream检查行、列和小方块的唯一性。
  3. 递归地填充空位，使用Stream简化代码。
*/
 
import java.util.stream.IntStream;
 
public class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
 
    private boolean solve(char[][] board) {
        return IntStream.range(0, 81)
            .mapToObj(i -> new int[] {i / 9, i % 9})
            .filter(cell -> board[cell[0]][cell[1]] == '.')
            .findFirst()
            .map(cell -> {
                int row = cell[0];
                int col = cell[1];
                return IntStream.range(1, 10)
                    .mapToObj(num -> (char) (num + '0'))
                    .filter(num -> isValid(board, row, col, num))
                    .anyMatch(num -> {
                        board[row][col] = num;
                        if (solve(board)) return true;
                        board[row][col] = '.';
                        return false;
                    });
            }).orElse(true);
    }
 
    private boolean isValid(char[][] board, int row, int col, char num) {
        return IntStream.range(0, 9).noneMatch(i -> board[row][i] == num || board[i][col] == num || board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num);
    }
}

解释

方法:

这个题解使用回溯法来解决数独问题。回溯法是一种通用的算法思路,适合由多个步骤组成的问题,并且每个步骤都有多个选项。通过尝试每一个选项,可以一步步构建问题的解,当某个步骤无法满足要求时,就回溯到上一个步骤,尝试其他选项。对于数独问题,从第一行第一列开始,尝试填入数字1-9。对于每个空格,先判断当前数字是否合法,如果合法就填入,然后递归地去填下一个空格,直到填完整个数独。如果中途发现无解,就回溯到上一个空格,尝试其他数字。

时间复杂度:

O(9^(n^2))

空间复杂度:

O(n^2)

代码细节讲解

🦆

为什么选择使用回溯法解决数独问题，而不是其他算法如动态规划或贪心算法？

▷

数独问题的本质是一个约束满足问题，其中每个数字的填充必须满足行、列以及3x3宫格的约束。回溯法适用于这种类型的问题，因为它可以通过试探和错误来找到问题的解。相比之下，动态规划适用于有最优子结构和重叠子问题的情况，而数独的每一步选择都依赖于整个盘面的状态，没有明显的最优子结构；贪心算法则是每一步都做出当下最优的选择，但对于数独来说，前面的选择直接影响后面的选择，一旦选择错误，整个数独就无法完成，因此贪心算法不适用。回溯法能够在每次选择失败时回退到上一步，是解决数独这种类型问题的理想选择。

🦆

在递归回溯时，是否有办法减少重复验证同一行或同一列已被排除的数字，以优化性能？

▷

可以通过维护额外的数据结构来优化性能，例如使用三个数组分别记录每行、每列以及每个3x3宫格中哪些数字已经被使用。这样，在验证数字是否可以放在某个位置时，只需查看相关数组的状态，而不必每次都遍历对应的行、列或宫格。这种方法可以显著减少验证过程中的重复操作，提高算法的效率。

🦆

如何确定在递归函数`backtrack`中已经找到了数独的唯一解，有什么特定的标志或条件？

▷

在`backtrack`函数中，当递归填充到最后一个空格之后，下一个递归调用的`i`参数将会是9（因为数独的索引是从0到8），这时表示所有的行已经被成功填充。若`backtrack`能够到达这一步，即i等于9时，就意味着找到了一个有效解，这时函数返回True。这个返回值向上递归传递，直到整个数独被成功解决。因此，特定的标志就是递归函数能够顺利到达i等于9的情况。

🦆

代码中的`valid`函数在判断数字合法性时为什么要分别检查行、列以及3x3宫，这三者的检查是否存在重叠的可能性？

▷

根据数独的规则，一个有效的数字填充必须满足同一行、同一列以及所在的3x3宫内没有重复数字。这三种检查针对的是不同的约束条件，不存在重叠的可能性。行检查确保没有行内重复，列检查确保没有列内重复，而3x3宫检查则确保在每个宫内没有重复。这三个条件是并列的，缺一不可，因此需要分别进行检查以确保数字的合法性。

相关问题

有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 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"]]
输出：true

示例 2：

输入：board = 
[["8","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"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

不同路径 III

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例 1：

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

示例 2：

输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径： 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

示例 3：

输入：[[0,1],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。

提示：

1 <= grid.length * grid[0].length <= 20

有效的数独外观数列