풀이 nqueens처럼 해당 가로, 세로 부분이 다 다른지 확인해주면 된다

import sys
lst = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]

lst_t = list(map(list, zip(*lst)))

blank = []
for i in range(9):
   for j in range(9):
       if lst[i][j] == 0:
           blank.append((i,j))
def checkRow(x, a):
   for i in range(9):
       if a == lst[x][i]:
           return False
   return True
def checkCol(y, a):
   for i in range(9):
       if a == lst[i][y]:
           return False
   return True
def checkRect(x,y,a):
   nx = x // 3 * 3
   ny = y // 3 * 3
   for i in range(3):
       for j in range(3):
           if a == lst[nx+i][ny+j]:
               return False
   return True
def dfs(idx):
   if idx == len(blank):
       for i in range(9):
           print(*lst[i])
       exit()

   for i in range(1, 10):
       x = blank[idx][0]
       y = blank[idx][1]

       if checkRow(x, i) and checkCol(y,i) and checkRect(x,y,i):
           lst[x][y] = i
           dfs(idx+1)
           lst[x][y] = 0
dfs(0)