import sys
input = sys.stdin.readline
sudoku = []
for i in range(9):
sudoku.append(list(map(int,list(input().strip()))))
def check(y,x,n):
for i in range(9):
if sudoku[y][i] == n or sudoku[i][x] == n:
return False
for i in range(3):
for j in range(3):
if sudoku[y-y%3+i][x-x%3+j] == n:
return False
return True
finish = False
def solsudoku(y,x):
global finish
if finish:
return
if x==9:
solsudoku(y+1,0)
return
if y==9:
finish=True
return
if sudoku[y][x] != 0:
solsudoku(y,x+1)
return
for i in range(1,10):
if check(y,x,i):
sudoku[y][x] = i
solsudoku(y,x+1)
if not finish:
sudoku[y][x] = 0
solsudoku(0,0)
for i in sudoku:
print("".join(map(str,i)))
전형적인 백트래킹 문제이다.
check함수를 이용해서 가로, 세로, 작은사각형 내에 같은 숫자가 있는지 확인하고 없으면 해당 숫자로 바꾼뒤 재귀호출하는 방식이다.
이 문제도 파이썬이 파이썬해서 pypy3로 제출하였다.
오늘의 교훈) 파이썬은 구리다