[BOJ] 2580. 스도쿠 (🥇, 백트래킹)

🔗

풀이

스도쿠의 규칙에 맞게 각 빈칸에 숫자가 들어가는지 들어갈 수 있는 모든 숫자 조합을 다 넣어본다. 도중에 하나라도 규칙에 맞지 않는다면 백트래킹으로 가지를 쳐낸다.

빈칸이 속하는 행, 열, 3x3칸에 없는 숫자들을 교집합을 통해 구했다. 그런 다음 하나씩 넣어보고 만약 모든 칸을 다 채울 수 있었다면 True를 반환했다. 이렇게 되면 실제 배열에 그 값이 거꾸로 채워지면서 반환된다.

최종적으로 arr 배열을 출력하면 된다.

# pypy3 : 3480ms
# 스도쿠

def check_row(x):
    return {k for k in range(1, 10) if k not in arr[x]}

def check_col(y):
    return {k for k in range(1, 10) if k not in [arr[x][y] for x in range(9)]}

def check_rect(x, y):
    res = set(range(1, 10))
    for i in range(3*x, 3*x+3):
        for j in range(3*y, 3*y+3):
            res -= {arr[i][j]}
    return res

def find_blank(arr):
    blank = dict()
    for i in range(9):
        for j in range(9):
            if not arr[i][j]:
                blank[(i, j)] = rows[i]&cols[j]&rects[3*(i//3)+j//3]
    return blank

def check(x, y, k):
    return k in rows[x]&cols[y]&rects[3*(x//3)+y//3]
    
def dfs(i, keys, arr):
    if i == len(keys):
        return True
        
    x, y = keys[i]
    for k in blank[(x, y)]:
        if check(x, y, k):
            rows[x].remove(k)
            cols[y].remove(k)
            rects[3*(x//3)+y//3].remove(k)
            if dfs(i+1, keys, arr):
                arr[x][y] = k
                return True
            rows[x].add(k)
            cols[y].add(k)
            rects[3*(x//3)+y//3].add(k)
    return False

arr = [list(map(int, input().split())) for _ in range(9)]
rows = [check_row(i) for i in range(9)]
cols = [check_col(j) for j in range(9)]
rects = [check_rect(i, j) for i in range(3) for j in range(3)]
blank = find_blank(arr)
keys = list(blank.keys())

dfs(0, keys, arr)
for row in arr:
    print(*row)