37. 解数独(Hard)

题目描述

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

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

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
• 空白格用 '.' 表示。

样例

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

题目解析

深度搜索 + 回溯法，和N皇后一样，就是不断修改数组的状态，检查是否符合规则。

本题只要找到一个答案即可，所以需要进行剪枝。

回溯剪枝的代码如下:

def backtracking(数组):
     for (i, j) in (数组各个位置)
         for (数字) in （0 - 9）
             if backtracking(状态):  # 剪枝
                 return True 
         return False # 数字遍历结束都无法找到
     return True # 所有格子走完(填完)

虽然 N皇后 和 解数独 问题是回溯算法中的 Hard 难度的问题，难点部分主要是在 isValid 函数上。

但是从回溯问题来说，并没有前面的一些 递增子序列，分割回文串等难。

Python示例

def backtracking(board):
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] != ".":
                continue
            for k in range(1, 10):
                if isValid(i, j, str(k), board):
                    board[i][j] = str(k)
                    if backtracking(board):
                        return True  
                    board[i][j] = '.'
            return False 
    return True 

def isValid(r, c, number, board):
    # 条件1. 数字 1-9 在每一行只能出现一次
    for i in range(9):
        if board[r][i] == number:
            return False 
    # 条件2. 数字 1-9 在每一列只能出现一次。
    for i in range(9):
        if board[i][c] == number:
            return False 
    # 条件3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    start_row = 3 * (r // 3) 
    start_col = 3 * (c // 3) 
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == number:
                return False 
    return True 

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        backtracking(board)