[BOJ] 2580번 스도쿠 (Python)

import sys
input = sys.stdin.readline

def check(x, y, candidate_num):
    # 가로 체크
    for i in range(9):
        if candidate_num == maps[x][i]:
            return False
    # 세로 체크
    for i in range(9):
        if candidate_num == maps[i][y]:
            return False
    # 같은 네모박스 체크  
    start_x = x//3 * 3
    start_y = y//3 * 3
    for i in range(3):
        for j in range(3):
            if candidate_num == maps[start_x+i][start_y+j]:
                return False
    return True


def dfs(fill_idx):
    # 채워야 될게 다 채워졌으면
    if fill_idx == len(space_to_fill):
        for row in maps:
            print(*row)
        sys.exit(0)

    x,y = space_to_fill[fill_idx]
    for candidate_num in range(1, 10): # 다 넣어보기
        # 숫자 중복 확인
        if check(x, y, candidate_num):
            maps[x][y] = candidate_num
            dfs(fill_idx+1)
            maps[x][y] = 0


maps = [list(map(int, input().split())) for _ in range(9)]
space_to_fill=[]
for i in range(9):
  for j in range(9):
    if maps[i][j] == 0:
      space_to_fill.append((i,j))
dfs(0)