[BOJ, Python] 2580 - 스도쿠 ( with Backtracking )

2580번: 스도쿠

백준 단계별로 풀기에서 퇴각검색 카테고리에 속해 있는, N - Queen 다음으로 나오는 문제이다. N - Queen 문제를 완벽히 익히고 나면 구현하는 데에 어려움이 없겠지만, 파이썬은 요구 시간이 좀 짜서 빠른 입출력과 3중 반복문을 한 개의 반복문으로 줄이는 등 여러 노력 끝에 AC를 받아낼 수 있었다.

import sys

# 스도쿠 판과 아직 채워지지 않은 칸의 좌표를 담을 리스트
sodoku = list()
blank = list()

# 입력, 빈칸의 좌표 채우기
for _ in range(9):
    sodoku.append(list(map(int, sys.stdin.readline().split())))

for x in range(9):
    for y in range(9):
        if sodoku[x][y] == 0:
            blank.append([x, y])

# 해당 (x, y)좌표에 r이라는 숫자가 들어갈 수 있는지 체크
def check(x, y, r):

	# 같은 행, 열에 있는 경우
    for i in range(9):
        if sodoku[x][i] == r:
            return False

        if sodoku[i][y] == r:
            return False
	
    # 같은 3 x 3 칸에 있는 경우
    row = x // 3 * 3
    col = y // 3 * 3

    for p in range(3):
        for q in range(3):
            if sodoku[row + p][col + q] == r:
                return False
	
    # 그 외에는 모두 참 출력
    return True

def solve(r):
	# 현재 채워넣은 수와 원래 빈칸의 개수가 동일할 때 완성된 판 출력 후 exit
    if r == len(blank):
        for i in sodoku:
            print(*i, end= "\n")
        sys.exit()
        
    x = blank[r][0]
    y = blank[r][1]
    
    # 1 ~ 9 까지의 숫자 사용, 백트래킹
    for k in range(1, 10):
        if check(x, y, k):
            sodoku[x][y] = k
            solve(r + 1)
            sodoku[x][y] = 0

solve(0)