python 有效的数独多种解法

编程小白狼

发布于 2024-12-31 08:20:25

6100

代码可运行

文章被收录于专栏：编程小白狼编程小白狼

运行总次数：0

代码可运行

解法一：暴力枚举法

最简单的方法是对于每一行、每一列和每一个 3x3 的九宫格，分别判断其中是否有重复的数字。具体实现如下：

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 检查行
        for i in range(9):
            nums = set()
            for j in range(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] in nums:
                    return False
                nums.add(board[i][j])
        
        # 检查列
        for j in range(9):
            nums = set()
            for i in range(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] in nums:
                    return False
                nums.add(board[i][j])
        
        # 检查 3x3 的九宫格
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                nums = set()
                for k in range(3):
                    for l in range(3):
                        if board[i+k][j+l] == '.':
                            continue
                        if board[i+k][j+l] in nums:
                            return False
                        nums.add(board[i+k][j+l])
        
        return True

解法二：使用哈希表

可以使用哈希表来保存每一行、每一列和每一个 3x3 的九宫格中出现的数字。具体实现如下：

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [{} for i in range(9)]
        cols = [{} for i in range(9)]
        boxes = [{} for i in range(9)]
        
        # 遍历数独
        for i in range(9):
            for j in range(9):
                # 如果当前格子为空，则跳过
                if board[i][j] == '.':
                    continue
                
                num = int(board[i][j])
                box_idx = (i // 3) * 3 + j // 3
                
                # 如果当前数字已在当前行、当前列或者当前九宫格中出现过，则返回 False
                if num in rows[i] or num in cols[j] or num in boxes[box_idx]:
                    return False
                
                # 否则将当前数字加入到对应的哈希表中
                rows[i][num] = rows[i].get(num, 0) + 1
                cols[j][num] = cols[j].get(num, 0) + 1
                boxes[box_idx][num] = boxes[box_idx].get(num, 0) + 1
                
        return True

由于数独中的数字只有 1 到 9 这九个数字，因此可以使用二进制数来表示某个数字是否出现过。具体实现如下：

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [0] * 9
        cols = [0] * 9
        boxes = [0] * 9
        
        # 遍历数独
        for i in range(9):
            for j in range(9):
                # 如果当前格子为空，则跳过
                if board[i][j] == '.':
                    continue
                
                num = int(board[i][j])
                box_idx = (i // 3) * 3 + j // 3
                
                # 如果当前数字已在当前行、当前列或者当前九宫格中出现过，则返回 False
                if rows[i] & (1 << num) or cols[j] & (1 << num) or boxes[box_idx] & (1 << num):
                    return False
                
                # 否则将当前数字加入到对应的位运算中
                rows[i] |= (1 << num)
                cols[j] |= (1 << num)
                boxes[box_idx] |= (1 << num)
                
        return True