题解 | Sudoku

import sys
n = 9
sudoku = []
row_record = [[0]*n for _ in range(n)]
col_record = [[0]*n for _ in range(n)]
grid_record = [[[0]*n for _ in range(3)] for j in range(3)]
for line in sys.stdin:
    sudoku.append(list(map(int, line.split())))
blanklist = []
setlist = []
for i in range(n):
    for j in range(n):
        v = sudoku[i][j]
        if v != 0:
            row_record[i][v-1] = 1
            col_record[j][v-1] = 1
            grid_record[i//3][j//3][v-1] = 1
        else:
            blanklist.append((i, j))
def dfs():
    if len(blanklist)==0:
        return True
    i, j = blanklist.pop()
    setlist.append((i, j))
    for v in range(1, 10):
        if row_record[i][v-1] == 0 and col_record[j][v-1] == 0 and grid_record[i//3][j//3][v-1] == 0:
            sudoku[i][j] = v
            row_record[i][v-1] = 1
            col_record[j][v-1] = 1
            grid_record[i//3][j//3][v-1] = 1
            if dfs():
                return True
            row_record[i][v-1] = 0
            col_record[j][v-1] = 0
            grid_record[i//3][j//3][v-1] = 0
    sudoku[i][j] = 0
    blanklist.append(setlist.pop())
    return False
dfs()
for i in range(n):
    print(' '.join(map(str, sudoku[i])))

        

八皇后问题的变体。