题解 | Sudoku

import sys

lines = sys.stdin.readlines()
matrix = []
for line in lines:
    matrix.append(list(map(int,line.strip().split())))

def is_legal(x,y,val):
    if val in matrix[x]:return False
    for row in range(9):
        if matrix[row][y] == val:return False 
    m,n = x // 3,y // 3
    for i in range(m*3,m*3+3):
        for j in range(n*3,n*3+3):
            if matrix[i][j] == val:return False
    return True

def sudoku(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == 0:
                for val in range(1,10):
                    if is_legal(i,j,val):
                        matrix[i][j] = val
                        if sudoku(matrix):
                            return True
                        matrix[i][j] = 0  # 每次选择val都是执行一个分支，在这个分支走到dead end后若要回溯走其他分支，则要先重置到没有选择val时的状态
                return False
    return True

if sudoku(matrix):
    for row in matrix:
        print(" ".join(list(map(str,row))))

二刷错误：

1.在检查填入的数字是否合法时，生成了大量列表，占用大量内存；判断块合法时生成了子矩阵，更是错误（列表的元素还是列表，判断in 永远返回false）

2.填入的取值范围是1-9：range(1,10)

3.nums[i][j] = 0即状态重置的位置：应该放在每次val分支的递归之后，递归返回False就重置，保证每条支路的清洁