Algorithm
本周选择的算法题是：Sudoku Solver。
规则
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: 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"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit or'.'.- It is guaranteed that the input board has only one solution.
Solution
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def backtrack(index) -> bool:
if index == len(empty): return True
i, j = empty[index]
for num in rows[i] & columns[j] & boxes[i//3*3+j//3]:
rows[i].remove(num)
columns[j].remove(num)
boxes[i//3*3+j//3].remove(num)
board[i][j] = str(num)
if backtrack(index+1): return True
rows[i].add(num)
columns[j].add(num)
boxes[i//3*3+j//3].add(num)
return False
rows = [set(range(1, 10)) for _ in range(9)]
columns = [set(range(1, 10)) for _ in range(9)]
boxes = [set(range(1, 10)) for _ in range(9)]
empty = []
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = int(board[i][j])
rows[i].remove(num)
columns[j].remove(num)
boxes[i//3*3+j//3].remove(num)
else:
empty.append((i, j))
backtrack(0)
Review
How to Implement a WYSIWYG Editor in SwiftUI
一个用 SwiftUI 实现 WYSIWYG 文本编辑器的例子。作者使用了 WebView 作为渲染视图，这和我们当初做邮件编辑器的想法类似，不过里面要解决的问题很多，其中也包括要实现一个多端复用的 Web 编辑器，为 Native 提供丰富的接口，并处理好 Native Web 容器的兼容性问题。
Tip
学习了部署鸿蒙环境。