算法题目

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

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

算法示例

注意事项

一个有效的数独（部分已被填充）不一定是可解的。

空白格用 '.' 表示。

常用算法：数组，哈希表，矩阵

解题思路

将行、列、小格子数组数据转换为哈希表进行判断解题，遍历的数据在行、列、小格子里则跳过，否则添加；

代码如下

from collections import defaultdict
from typing import List

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 将数组转化为哈希表解题
        row, col, sqrt = defaultdict(set), defaultdict(set), defaultdict(set)
        for i in range(9):
            for j in range(9):
                tmp = board[i][j]
                if tmp == ".":
                    continue
                grid = i // 3 * 3 + j // 3  # 计算九宫格位置
                # if tmp in row[i] or tmp in col[j] or tmp in sqrt[grid]:
                if tmp in (row[i] | col[j] | sqrt[grid]):
                    return False
                row[i].add(tmp)
                col[j].add(tmp)
                sqrt[grid].add(tmp)
        return True

数独进阶版

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

常用算法：数组 回溯 矩阵

算法示例

解题思路

使用回溯进行处理，通过列、行遍历，进行判断当前获取的数字是否在行、列和小格子里，如果存在则进行后续判断，否则赋值；

代码如下

from typing import List
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        回溯法
        def backtrack(path, selected):
            if 满足停止条件：
                res.append(path)
            for 选择 in 选择列表：
                做出选择
                递归执行backtrack
                撤销选择
        """

        def backtrack(board, i, j):
            # 回溯
            if j == 9:  # 列遍历完，遍历行
                return backtrack(board, i + 1, 0)

            if i == 9:  # 行遍历完，结束
                return True

            if board[i][j] != ".":  # 非空进行下一个
                return backtrack(board, i, j + 1)
            for t in range(1, 10):
                if not self.check(board, i, j, str(t)):  # 判断选择的字符是否满足要求
                    continue
                board[i][j] = str(t)  # 做选择，赋值
                if backtrack(board, i, j + 1):  # 递归调用
                    return True
                board[i][j] = '.'  # 撤销选择
        backtrack(board, 0, 0)

    def check(self, board, row, col, s):
        # 检查数字是否在行、列和小格子里
        for i in range(9):
            if board[row][i] == s:
                return False
            if board[i][col] == s:
                return False
            if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == s:
                return False
        # for i in range(9):
        #     if s in [board[row][i], board[i][col], board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3]]:
        #         return False
        return True

总结

人生苦短，我用python！

#python##学习##学习打卡#