https://www.acmicpc.net/problem/2580

• 백트래킹으로 열, 행, 주변 박스 검사

• 시간 복잡도를 줄이기 위해, 0인 값만 검사하는 for문 추가
  • 첫 답안에 행의 모든 수를 검사해서 시간초과 발생

import sys
read = sys.stdin.readline
# 입력이 너무 적으면 input()써라

n = 9
answer = [list(map(int, read().split())) for _ in range(n) ]
nxt = []

for r in range(n):
    for c in range(n):
        if answer[r][c] == 0:
            nxt.append((r, c))
            
def check_row(k_r, k):  
    for c in range(n):
        if answer[k_r][c] == k:
            return False

    return True            

def check_col(k_c, k):
    for r in range(n):
        if answer[r][k_c] == k:
            return False

    return True
    
def check_around(r, c, k):    
    r = r // 3 * 3
    c = c // 3 * 3
    
    for x in range(r, r+3):
        for y in range(c, c+3):
            if answer[x][y] == k:
                return False
    
    return True
        
def solve(k): 
    if k == len(nxt):
        for row in answer:
            print(' '.join(map(str, row)))
        sys.exit(0)

    r, c = nxt[k]
    
    for num in range(1, n+1):
        if check_row(r, num) and check_col(c, num) and check_around(r, c, num):
            answer[r][c] = num
            solve(k+1)
            answer[r][c] = 0  
    

solve(0)