동작 원리

이 장에서는 작은 예제 두 개를 손으로 따라가며 백트래킹이 실제로 어떻게 움직이는지 봅니다. 먼저 가지치기가 없는 조합 생성을 추적하고, 다음으로 4-Queens에서 제약 검사와 되돌아가기가 어떻게 맞물리는지 확인합니다. 마지막으로 같은 원리가 스도쿠에서 어떻게 쓰이는지 살펴봅니다.

예제 1: 조합 C(4, 2)

[1, 2, 3, 4]에서 2개를 고르는 조합을 만듭니다. 순서만 다른 중복을 피하려고 다음 선택은 항상 지금 고른 수보다 뒤에서 시작합니다. 이것만으로도 [2, 1] 같은 가지가 처음부터 생기지 않습니다.

def combine(n, k):
    result, path = [], []

    def dfs(start):
        if len(path) == k:
            result.append(path[:])
            return
        for x in range(start, n + 1):
            path.append(x)        # 선택
            dfs(x + 1)            # 탐색
            path.pop()            # 되돌리기

    dfs(1)
    return result

print(combine(4, 2))
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

호출 순서를 표로 따라가 보면 path가 늘었다 줄었다 하는 모습이 보입니다.

여기에 가지치기를 하나 더할 수 있습니다. 남은 수가 채워야 할 개수보다 적으면 더 볼 필요가 없으므로, 반복 범위를 range(start, n - (k - len(path)) + 2)로 줄이면 [4]처럼 끝까지 가도 2개를 채울 수 없는 가지를 아예 만들지 않습니다.

예제 2: 4-Queens

4×4 판에 퀸 4개를 서로 공격하지 않게 놓습니다. 한 행에 퀸을 하나씩 놓는다고 정하면 행 충돌은 저절로 사라지고, 열과 두 대각선만 검사하면 됩니다. 같은 대각선 위의 칸은 row - col 값이 같고, 반대 방향 대각선 위의 칸은 row + col 값이 같습니다.

def is_safe(queens, row, col):
    # queens[r] = r행에 놓은 퀸의 열
    for r, c in enumerate(queens):
        if c == col or r - c == row - col or r + c == row + col:
            return False
    return True

열 번호로 첫 번째 해를 찾기까지의 과정입니다.

0행 0열에서 시작한 가지 전체에서 해가 없다는 것을 확인하는 데 몇 걸음이면 충분했습니다. 4^4 = 256가지 배치를 모두 만드는 대신, 실제로 방문한 노드는 루트를 포함해 17개뿐입니다(두 해를 모두 찾을 때까지).

def solve(n):
    solutions = []

    def place(queens):
        row = len(queens)
        if row == n:
            solutions.append(queens[:])
            return
        for col in range(n):
            if is_safe(queens, row, col):
                queens.append(col)
                place(queens)
                queens.pop()

    place([])
    return solutions

print(solve(4))  # [[1, 3, 0, 2], [2, 0, 3, 1]]

예제 3: 스도쿠의 제약 검사

스도쿠도 같은 틀입니다. 빈 칸 하나를 골라 1부터 9까지 넣어 보고, 같은 행, 같은 열, 같은 3×3 상자에 이미 있는 숫자는 건너뜁니다. 넣을 수 있는 숫자가 하나도 없으면 앞 칸으로 돌아가 다른 숫자를 시도합니다.

def can_place(board, r, c, d):
    if any(board[r][j] == d for j in range(9)):
        return False
    if any(board[i][c] == d for i in range(9)):
        return False
    br, bc = 3 * (r // 3), 3 * (c // 3)
    return all(board[i][j] != d
               for i in range(br, br + 3)
               for j in range(bc, bc + 3))

실제 풀이기는 후보가 가장 적은 칸부터 채우는 방식(MRV, minimum remaining values)을 더해 탐색량을 크게 줄입니다. 후보가 하나뿐인 칸을 먼저 채우면 잘못된 가지가 훨씬 일찍 드러나기 때문입니다.

정리

• 백트래킹은 path를 하나 두고 선택과 되돌리기를 짝지어 깊이 우선으로 내려갑니다.
• 제약 검사는 새 선택이 기존 부분해와 충돌하는지만 보면 되도록 설계하는 것이 좋습니다.
• 4-Queens에서는 0행 0열 가지가 몇 걸음 만에 잘렸고, 이런 조기 차단이 백트래킹의 핵심입니다.