36. 有效的数独

python

python
展开代码
from typing import List
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # init data
        rows = [{} for i in range(9)] # 字典 哈希表 列表第一个字典：rows[0]这个字典是第一行的键值信息
        columns = [{} for i in range(9)] # 字典 哈希表
        boxes = [{} for i in range(9)] # 字典 哈希表
        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]  # 第i行  第j列  的元素
                if num != '.':
                    num = int(num)
                    box_index = (i // 3) * 3 + j // 3    # 在一个3*3方格里的index
                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1  # 第i行的rows字典里找这个元素，找不到就是0，加1后变成1. 找得到加上1后就会大于1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True
print(Solution().isValidSudoku([
  ["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"]  ]))

运行完毕后：

按健寻值的字典：

python
展开代码
rows = [{} for i in range(9)]
print(rows)
rows[0][1]=1
rows[0][3]=1
rows[1][1]=1
print(rows)

结果

python
展开代码
C:\Users\xd_du\Anaconda3\envs\py37\python.exe C:/Users/xd_du/PycharmProjects/wave/gendata.py
[{}, {}, {}, {}, {}, {}, {}, {}, {}]
[{1: 1, 3: 1}, {1: 1}, {}, {}, {}, {}, {}, {}, {}]
Process finished with exit code 0

37. 解数独

https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode-solution/

python
展开代码
from typing import List
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def dfs(pos: int):
            nonlocal valid
            if pos == len(spaces):
                valid = True
                return
            i, j = spaces[pos]
            for digit in range(9):
                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
                    board[i][j] = str(digit + 1)
                    dfs(pos + 1)   #递归
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
                if valid:
                    return
        line = [[False] * 9 for _ in range(9)]
        column = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
        valid = False
        spaces = list()
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i, j))
                else:
                    digit = int(board[i][j]) - 1
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
        dfs(0)
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"]]
Solution().solveSudoku(board)
for i in range(9):
    print(board[i])

python
展开代码
def check(matrix, row, col, value):
    """
    检测在(row,col)放value是否合适
    1.每行含1-9,不含重复值value
    2.每列含1-9,不含重复值value
    3.3*3区块含1-9,不含重复值value
    """
    # 检测每行
    for j in range(9):
        if matrix[row][j] == value:
            return False
    # 检测每列
    for i in range(9):
        if matrix[i][col] == value:
            return False
    # 检测元素所在3*3区域
    area_row = (row // 3) * 3
    area_col = (col // 3) * 3
    for i in range(area_row, area_row + 3):
        for j in range(area_col, area_col + 3):
            if matrix[i][j] == value:
                return False
    return True
def solveSudoku(matrix, count=0):
    """
    遍历每一个未填元素，遍历1-9替换为合适的数字
    """
    if (count == 81):  # 递归出口
        return True
    #行优先遍历
    row = count // 9  # 行标
    col = count % 9  # 列标
    if matrix[row][col] != 0:  # 已填充
        return solveSudoku(matrix, count=count + 1)
    else:  # 未填充
        for i in range(1, 10):
            if check(matrix, row, col, i):  # 找到可能的填充数
                matrix[row][col] = i
                if solveSudoku(matrix, count=count + 1):  # 是否可完成
                    return True  # 可完成
                # 不可完成
                matrix[row][col] = 0  # 回溯
        return False  # 不可完成
while True:
    try:
        matrix = []
        for i in range(9):
            matrix.append([int(i) for i in  input().split(' ')])#多维列表输入
        solveSudoku(matrix)
        for i in range(9):
            print( ' '.join(map(str, matrix[i])))
    except:
        break

生成一张标准数独地图

标准数独地图有17个数字提示，且是有唯一解的。