解数独

1. 题目描述

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

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

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 数独部分空格内已填入了数字，空白格用 '.' 表示。

输入：

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

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

2. 分析

可以用回溯法解决这个问题，这是一种深度优先搜索（DFS）的技巧，用于求解满足某些条件的所有解，特别适合这种具有约束条件的搜索问题。

回溯法思路：

我们从空格开始，尝试填入 1 到 9 中的每个数字，检查当前数字是否满足数独的约束条件。如果满足条件，则继续填充下一个空格。如果填充完成，则返回。 如果发现某个数字无法填充，回溯到上一步，尝试另一个数字。 有效性检查：

对每个空格，我们需要确保： 该数字没有在当前行出现。 该数字没有在当前列出现。 该数字没有在当前 3x3 宫内出现。

算法步骤： 递归函数：实现一个递归函数来遍历每个空格。 有效性检查函数：检查在特定位置放置一个数字是否满足数独规则。 回溯：尝试填入数字，如果满足条件则递归，直到解决问题，否则回溯。

代码构造： 1.is_valid 函数：检查给定位置（row, col）是否可以填入数字 num。它分别检查当前行、当前列以及当前 3x3 宫内是否有重复数字。 2.solve 函数：这个函数是回溯的核心。它遍历整个数独棋盘，找到空格（即值为 '.' 的位置），然后尝试填入所有可能的数字（从 '1' 到 '9'）。对于每个数字，使用 is_valid 检查是否可以填入。如果可以，则递归填充下一个空格。如果无法继续填充，就回溯并尝试下一个数字。 3.递归终止条件：如果棋盘上没有空格（即每个格子都已经填满），则表示数独已解出，递归结束。 4.输出：当递归成功结束后，数独棋盘 board 会被填充为解答，并最终打印出结果。

3. 代码

def solveSudoku(board):
    def is_valid(board, row, col, num):
        # 检查行
        for i in range(9):
            if board[row][i] == num:
                return False
        # 检查列
        for i in range(9):
            if board[i][col] == num:
                return False
        # 检查3x3宫
        start_row, start_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(start_row, start_row + 3):
            for j in range(start_col, start_col + 3):
                if board[i][j] == num:
                    return False
        return True

    def solve(board):
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':  # 找到空格
                    for num in '123456789':  # 尝试所有数字
                        if is_valid(board, row, col, num):
                            board[row][col] = num  # 放置数字
                            if solve(board):  # 递归
                                return True
                            board[row][col] = '.'  # 回溯
                    return False  # 如果没有数字可以放，回溯
        return True  # 如果填满了整个板子

    solve(board)

# 示例用法：
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"]
]

solveSudoku(board)

# 打印结果
for row in board:
    print(row)