[백준] 2580번(python 파이썬)

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

 

백트래킹으로 구현할 수 있는 문제이다.

 

우선 index 0 ~ 80 의 칸을 검사한다.

 

해당 칸이 빈칸일경우 해당 칸에 들어갈 수 있는 숫자를 구한다.

def AbleNumber(n, m):
    ableNumber = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for i in range(9):
        if graph[n][i] in ableNumber:
            ableNumber.remove(graph[n][i])

    for i in range(9):
        if graph[i][m] in ableNumber:
            ableNumber.remove(graph[i][m])

    sub_n = n // 3
    sub_m = m // 3

    for i in range(sub_n * 3, sub_n * 3 + 3):
        for j in range(sub_m * 3, sub_m * 3 + 3):
            if graph[i][j] in ableNumber:
                ableNumber.remove(graph[i][j])
    return ableNumber

가능한 숫자를 구하면

 

해당 칸에 하나씩 넣으면서 재귀를 돌린다.

 

재귀를 돌리던도중에 해당 칸에 들어갈 숫자가 없으면 False를 반환을 하게된다. 그러면 이전 상태로 되돌아 가게되고

 

다음으로 가능한 숫자를 넣게된다.

 

이후에 다시 재귀를 돌려 다음 칸들을 확인한다.

 

graph = [list(map(int, input().split())) for _ in range(9)]

def BackT(idx):
    if idx == 81:
        return True

    for i in range(idx, 81):
        sub_n = i // 9
        sub_m = i % 9

        if graph[sub_n][sub_m] != 0:
            if i == 80:
                return True
            continue

        ableNumber = AbleNumber(sub_n, sub_m)
        for j in ableNumber:
            graph[sub_n][sub_m] = j
            if BackT(i + 1):
                return True
            graph[sub_n][sub_m] = 0
        return False
        

BackT(0)
for i in range(9):
    for j in range(9):
        print(graph[i][j], end=' ')
    print()