[백준] 2239 스도쿠(Back Tracking)

문제 분석

“가로 축, 세로 축, 3*3 박스 내에 1~9 중에서 겹치는 수”를 고려해서 문제를 해결할 때 답이 나오지 않는 경우가 존재한다.
그럴 때는 이전 칸으로 돌아가서 조건에 맞는 다른 수로 수정해야 한다. -> 백트래킹 사용

알고리즘

1. 스도쿠에 빈 공간이 있는지 확인한다. -> find_empty() 함수
2. 빈 공간이 없다면 스도쿠 완성이므로 종료한다.
3. 빈 공간이 있으면 해당 좌표를 반환한다. (i,j)
4. 빈 공간에 어떤 값이 들어갈 수 있는지 탐색한다.
   • 찾았다면 스도쿠에 채워넣는다.
   • 찾지 못한다면 백 트래킹을 한다.

스도쿠에 빈 공간 확인하기

• 스도쿠 전체를 확인하며 0인 공간을 찾는다. 찾을 경우 좌표를 반환한다.
• 0인 공간이 없다면 None을 반환한다.

빈 공간에 들어갈 수 있는 값인지 확인하기

• 가로 축, 세로 축, 3*3 박스 내에 동일한 값이 없으면 스도쿠에 채워 넣는다.
• 동일한 값이 있다면 False를 반환한다.

이 때, 33 박스의 범위는 (col/3 3, row/3 * 3)을 시작으로 3만큼 더해주면 된다.

코드

def find_empty():
    for i in range(9):
        for j in range(9):
            if p[i][j] == 0:
                return i, j
    return None, None

def valid(col, row, val):
    # 가로 축
    for i in range(9):
        if p[col][i] == val:
            return False
    # 세로 축
    for i in range(9):
        if p[i][row] == val:
            return False
    # 3*3 보드
    box_col = col//3 * 3
    box_row = row//3 * 3
    for i in range(box_col, box_col+3):
        for j in range(box_row, box_row+3):
            if p[i][j] == val:
                return False
    return True
    
def dfs():
    col, row = find_empty()
    if col == None:
        return True
    
    for i in range(1,10):
        if valid(col, row, i):
            p[col][row] = i
            if dfs():
                return True
            p[col][row] = 0
    return False

p = []

for _ in range(9):
    p.append(list(map(int, input())))

dfs()

for i in range(9):
    for j in range(9):
        print(p[i][j], end = "")
    print()