백준 2580번 스도쿠

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

2580번: 스도쿠

스도쿠를 입력받고 0에 해당하는 빈칸을 채우는 문제다.

 

백트래킹을 통해서 풀어보았다.

# 스도쿠 채우기
def sudoku(n):
    if n == len(blank):	# 빈칸을 모두 채우면
        for i in range(9):
            for j in range(9):
                print(arr[i][j], end=' ')	# 완성된 스도쿠 출력
            print()
        exit(0)	# 하나의 완성된 스도쿠 출력시 종료

    for i in range(1, 11):
        if i == 10:		# 1 ~ 9 모두 빈칸에 넣을 수 없는 경우 (전에 넣었던 숫자가 틀린 경우)
            arr[blank[n][0]][blank[n][1]] = 0	# 해당 빈칸을 다시 0으로 하고
            return		# 함수를 종료하여 백트래킹
        arr[blank[n][0]][blank[n][1]] = i	# 1 ~ 9 숫자를 넣어보고
        if condition(blank[n]):	# 조건에 부합하면 다음 빈칸으로 넘어감
            sudoku(n+1)


# 조건
def condition(b):
    value = arr[b[0]][b[1]]		# 해당 빈칸의 값
    for i in range(9):
        if i != b[1] and arr[b[0]][i] == value:     # 행 검사
            return False
        if i != b[0] and arr[i][b[1]] == value:     # 열 검사
            return False
    square_y = relocate(b[0])
    square_x = relocate(b[1])
    for i in range(square_y, square_y + 3):     # 작은 사각형 검사
        for j in range(square_x, square_x + 3):
            if (i != b[0] or j != b[1]) and arr[i][j] == value:
                return False
    return True		# 모든 검사 통과시 조건 부합


# 9분할
def relocate(n):    # 작은 사각형 검사를 위한 좌표 설정
    if 0 <= n < 3:
        return 0
    elif 2 < n < 6:
        return 3
    else:
        return 6


# main
arr = [[0 for _ in range(9)] for _ in range(9)]		# 빈 스도쿠 생성
blank = []	# 빈칸의 좌표를 담을 배열
for i in range(9):
    arr[i] = list(map(int, input().split()))
    for j in range(9):
        if arr[i][j] == 0:
            blank.append((i, j))    # 빈칸 좌표 튜플로 저장
sudoku(0)	# 첫 빈칸부터 채우기

스도쿠를 입력받고 0에 해당하는 빈칸 좌표를 튜플로 배열에 저장한다.

 

빈칸에 숫자를 넣어가면서 스도쿠 조건에 맞는지 확인한다.

 

스도쿠 조건을 확인하는 condition 함수에선 행, 열, 작은사각형에 해당 숫자가 다른칸에 있는지 검사한다.

 

해당 숫자가 조건에 맞으면 다음 빈칸으로 넘어가고 틀리면 다음 숫자를 넣는다.

 

i가 10이 되면 1 ~ 9 의 모든 숫자들이 조건에 맞지 않는다는 뜻이므로 해당 칸에 0을 넣어 다시 빈칸으로 만들고

이전 빈칸으로 백트래킹하여 다른 숫자를 넣도록 한다.

 

그렇게 모든 빈칸을 채우면 스도쿠를 출력한다.