이번 문제는 백트레킹을 통해 해결하였다. 우선 0으로 채워져있는 위치의 인덱스를 리스트에 담고, 이 리스트를 백트레킹을 통해 순회하도록 하였다. 이 과정에서 행과 열을 모두 확인하고, 현재 위치가 속한 작은 사각형을 확인하여 들어가고자 하는 수와 같은 값이 존재하지 않을 경우에만 값을 넣도록 하였다. 이 과정을 반복하다가 cur 인자가 0들을 담은 리스트의 길이와 같아졌을 때, grid를 출력하고, 프로그램을 종료하도록 작성하였다.

Code

grid = [list(str(input())) for _ in range(9)]
answer = []
zeros = []
for i in range(9):
    for j in range(9):
        if grid[i][j] == '0':
            zeros.append((i, j))
def chk_rc(r, c, num):
    for i in range(9):
        if grid[r][i] == num:
            return False
        if grid[i][c] == num:
            return False
    return True
def chk(r, c, num):
    nr, nc = (r//3) * 3, (c//3) * 3
    for i in range(3):
        for j in range(3):
            if grid[nr+i][nc+j] == num:
                return False
    return True
def make_grid(cur):
    if cur == len(zeros):
        for i in range(9):
            print(''.join(grid[i]))
        quit()
    y, x = zeros[cur]
    for num in range(1, 10):
        if chk_rc(y, x, str(num)) and chk(y, x, str(num)):
            grid[y][x] = str(num)
            make_grid(cur+1)
            grid[y][x] = '0'
make_grid(0)