题解 | #数独#回溯

import sys

grid = [[0] * 10]
for s in sys.stdin:
    grid.append([0] + list(map(int, s.split(" "))))
# rows[i][j]表示第i行是否已使用数字j
rows = [[False] * 10 for _ in range(10)]
# cols[i][j]表示第i列是否已使用数字j
cols = [[False] * 10 for _ in range(10)]
# blks[i][j]表示第i个小正方形块是否已使用数字j
blks = [[False] * 10 for _ in range(10)]
for i in range(1, 10):
    for j in range(1, 10):
        num = grid[i][j]
        if num == 0:
            continue
        # 九个小正方形块的编号(1-9,行优先)
        b = (i - 1) // 3 * 3 + (j - 1) // 3 + 1
        rows[i][num] = cols[j][num] = blks[b][num] = True

def dfs():
    global grid, rows, cols, blks
    for i in range(1, 10):
        for j in range(1, 10):
            if grid[i][j] != 0:
                continue
            # print(i, j, grid[i][j])
            b = (i - 1) // 3 * 3 + (j - 1) // 3 + 1
            # 尝试填入1-9
            for k in range(1, 10):
                if rows[i][k] or cols[j][k] or blks[b][k]:
                    continue
                # 尝试填入k
                rows[i][k] = cols[j][k] = blks[b][k] = True
                grid[i][j] = k
                if dfs():
                    return True
                # 此路不通，回溯
                rows[i][k] = cols[j][k] = blks[b][k] = False
                grid[i][j] = 0
            # 1-9都无法填入grid[i][j]，此路不通
            return False
    return True

dfs()
for i in range(1, 10):
    print(" ".join(list(map(str, grid[i][1:]))))