题解 | Sudoku

Idxs = tuple[int, int, int]
zeros = set[Idxs]()
boxs = dict[int, list[Idxs]]()
rows = list[list[str]]()
for r in range(9):
    row = []
    for c, v in enumerate(input().split()):
        b = r // 3 * 3 + c // 3
        idxs = (r, c, b)
        if v == "0":
            zeros.add(idxs)
        boxs.setdefault(b, []).append(idxs)
        row.append(v)
    rows.append(row)


def valid(p: Idxs):
    r, c, b = p
    v = rows[r][c]
    for x in range(9):
        if x != r and v == rows[x][c]:
            return False
        if x != c and v == rows[r][x]:
            return False
        br, bc, _ = boxs[b][x]
        if br != r and bc != c and v == rows[br][bc]:
            return False
    return True


def dfs():
    for p in zeros.copy():
        zeros.remove(p)
        for x in "123456789":
            rows[p[0]][p[1]] = x
            if valid(p) and dfs():
                return True
        rows[p[0]][p[1]] = "0"
        zeros.add(p)
        return False
    return True


if not dfs():
    print("no answer")
print("\n".join(" ".join(row) for row in rows))