题解 | #Sudoku# 标准回溯 Python3

import enum
import sys
from collections import deque

# 处理输入
board = list(map(lambda line: list(map(int, line.split(" "))), sys.stdin.readlines()))

# 统计哪些位置需要求解
blank_pos = []
blank_pos2l = {}
L = 0
for irow, row in enumerate(board):
    for icol, char in enumerate(row):
        if char == 0:
            blank_pos.append((irow, icol))
            blank_pos2l[(irow, icol)] = L
            L += 1

# 根据当前解和题面查询某位置的当前值
def lookupB(sln, pos):
    m, n = pos
    return board[m][n] or (sln[blank_pos2l[(m, n)]] if blank_pos2l[(m, n)] < len(sln) else 0)
    
# 3x3 格内坐标转换
def i2mn(m, n, i):
    return (m // 3 * 3+ i // 3, n // 3 * 3 + i % 3)

# 根据当前部分解sln, 检查数字num是否适合填入位置pos
def check(num, pos, sln):
    m, n = pos
    count_row = sum(1 for i in range(9) if lookupB(sln, (m, i)) == num)
    if count_row > 1: return False
    count_col = sum(1 for i in range(9) if lookupB(sln, (i, n)) == num)
    if count_col > 1: return False
    count_blk = sum(1 for i in range(9) if lookupB(sln, i2mn(m, n, i)) == num)
    if count_blk > 1: return False
    return True

# 回溯 / DFS （等价）
Q = deque()
Q.append([])

sln = []
while Q:
    sln = Q.pop()
    l = len(sln)
    if l == L:
        break
    for nxt in range(1, 10):
        nxt_sln = sln + [nxt]
        if check(nxt, blank_pos[l], nxt_sln):
            Q.append(nxt_sln)

# 输出结果
for irow, row in enumerate(board):
    for icol, char in enumerate(row):
        print(
            lookupB(sln, (irow, icol)),
            end=" " if icol < 8 else ("\n" if irow < 8 else ""),
        )