0037. 解数独 #

标签：数组、回溯、矩阵
难度：困难

题目大意 #

给定一个二维的字符数组 board 用来表示数独，其中数字 1-9 表示该位置已经填入了数字，. 表示该位置还没有填入数字。

现在编写一个程序，通过填充空格的方式来解决数独问题，最终不用返回答案，将题目给定 board 修改为可行的方案即可。

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗直线分隔的 3 * 3 宫格内只能出现一次。

解题思路 #

使用回溯算法求解。对于每一行、每一列、每一个数字，都需要 1 重 for 循环来遍历，这样就是 3 重 for 循环。

对于第 i 行、第 j 列的元素来说，如果当前位置为空位，则尝试将第 k 个数字置于此处，并检验数独的有效性。如果有效，则继续遍历下一个空位，直到遍历完所有空位，得到可行方案或者遍历失败时结束。

遍历完下一个空位之后再将此位置进行回退，置为 .。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution:
    def backtrack(self, board: List[List[str]]):
        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 self.isValid(i, j, k, board):
                        board[i][j] = str(k)
                        if self.backtrack(board):
                            return True
                        board[i][j] = '.'
                return False
        return True

    def isValid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:
        for i in range(0, 9):
            if board[row][i] == str(val):
                return False

        for j in range(0, 9):
            if board[j][col] == str(val):
                return False

        start_row = (row // 3) * 3
        start_col = (col // 3) * 3

        for i in range(start_row, start_row + 3):
            for j in range(start_col, start_col + 3):
                if board[i][j] == str(val):
                    return False
        return True

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