import sys
input = sys.stdin.readline
g = [list(map(int, input().split())) for _ in range(9)]
# 공백을 구함
blank = []
for i in range(9):
for j in range(9):
if g[i][j] == 0:
blank.append((i, j))
# 모든 공백에 대해 들어갈 수 있는 수를 구함
poss = [[] for _ in range(len(blank))]
for u in range(len(blank)):
x, y = blank[u]
# 집합에 1부터 9까지 담아줌
update = set(i for i in range(1, 10))
# 가로 탐색
# 같은 행에 있는 숫자들은 못들어가니까 빼줌
r_set = set(g[x])
update = update - r_set
# 세로 탐색
# 같은 열에 있는 숫자들은 못 들어가니까 빼줌
tmp = set()
for i in range(9):
if g[i][y] != 0:
tmp.add(g[i][y])
update = update - tmp
# 정사각형 탐색
# 같은 정사각형에 있는 숫자들은 못 들어가니까 빼줌
tmp = set()
nu, nv = x//3 * 3, y//3 * 3
for row in [nu, nu+1, nu+2]:
for column in [nv, nv+1, nv+2]:
if g[row][column] != 0:
tmp.add(g[row][column])
update = update - tmp
poss[u] = list(update)
# 그 자리에 들어갈 수 있는지 확인
def check(x, y, g):
for i in range(9):
if g[i][y] == g[x][y] and i != x:
return 0
for i in range(9):
if g[x][y] == g[x][i] and i != y:
return 0
nu, nv = x//3 * 3, y//3 * 3
for row in [nu, nu+1, nu+2]:
for column in [nv, nv+1, nv+2]:
if g[row][column] == g[x][y] and (row, column) != (x, y):
return 0
return 1
# 칸마다 가능한 숫자를 넣어서 정답을 구한다
def go(i, g, x, y):
if i != 0 and check(x, y, g) == 0:
return
if i == len(blank):
for r in range(9):
print(*g[r])
# 답이 여러 개인 경우 하나만 출력하기 위해 return 대신 exit
exit(0)
x, y = blank[i]
for p in poss[i]:
g[x][y] = p
go(i+1, g, x, y)
g[x][y] = 0
go(0, g, blank[0][0], blank[0][1])
처음에 빈칸마다 탐색해서 들어갈 수 있는 숫자 넣고 다시 탐색 반복 (시간초과)
한번만 탐색하고 재귀 돌리는 것으로 바꿈 (어떤 분의 풀이 참고..)