题解 | #Sudoku#

from collections import defaultdict
import copy


grid = []
for _ in range(9):
    grid.append([int(i) for i in input().split()])


def solve_sudo(grid):
	# 查找待填位置
    zeros = []
    for i in range(9):
        for j in range(9):
            if grid[i][j]==0:
                zeros.append((i,j))
	# 每个待填位置查找候选数字
    waits = dict()
    for i,j in zeros:
		# 初始化候选数字为都可选，然后删掉不可选的
        wait = [1]*10
        temp = []
		# 在第几个3*3小方块
        iloc,jloc = i//3,j//3
		# 同小方块存在的数
        s_grid = []
        for row in range(iloc*3,iloc*3+3):
            s_grid.extend(grid[row][jloc*3:jloc*3+3])
        for k in range(9): # 候选数中删掉该行的数
            wait[grid[i][k]] = 0
        for k in range(9): # 候选数中删掉该列的数
            wait[grid[k][j]] = 0
        for k in s_grid: # 候选数中删掉该小方块的数
            wait[k] = 0
        for k in range(1,10):
            if wait[k]:
                temp.append(k)
        waits[(i,j)] = temp
	# 待填空的数之间哪些数相关
    connects = defaultdict(list)
    le = len(zeros)
    for i in range(le-1):
        for j in range(i+1,le):
            x1,y1 = zeros[i]
            x2,y2 = zeros[j]
            if x1==x2 or y1==y2 or (x1//3==x2//3 and y1//3==y2//3):
                connects[(x1,y1)].append((x2,y2))
    len_need = le
    ans = []
	
	
    def dfs(zeros, waits):
		# 确定第一个，然后更新后续的候选列表
        for w in waits[zeros[0]]:
			# 尝试
            ans.append(w)
            if len(ans)==len_need:
                return
            nex_waits = copy.deepcopy(waits)
            for friend in connects[zeros[0]]:
				# 如果使用有序数组会快一点
                if w in nex_waits[friend]:
                    nex_waits[friend].remove(w)
            dfs(zeros[1:], nex_waits)
			# 尝试成功，停止循环
            if len(ans)==len_need:
                return
			# 尝试失败，回溯
            ans.pop()
    dfs(zeros, waits)
    for idx, (x,y) in enumerate(zeros):
        grid[x][y] = ans[idx]
    for l in grid:
        print(' '.join([str(i) for i in l]))


solve_sudo(grid)

首先查找待填位置，然后查找待填位置处的候选数字，还需要找到待填位置之间的互斥关系，最后用dfs+回溯艰难完成本题