36. 有效的数独(遍历一次 9+9+9个字典 哈希) 37. 解数独
程序员文章站
2022-07-14 14:13:33
...
36. 有效的数独
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"] ]))
运行完毕后:
按健寻值的字典:
rows = [{} for i in range(9)]
print(rows)
rows[0][1]=1
rows[0][3]=1
rows[1][1]=1
print(rows)
结果
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/
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])
生成一张标准数独地图
标准数独地图有17个数字提示,且是有唯一解的。
上一篇: Ruby和Rails的缺点