한양과학기술고등학교

N-퀸 백트래킹 시각화

핵심 코드 (N-퀸)

def solve(n):
    cols, diag, anti = set(), set(), set()   # 이미 쓴 열 / ↘대각선(r-c) / ↙대각선(r+c)
    res = []

    def backtrack(r, board):
        if r == n:                       # 모든 행에 퀸을 놓았다 → 정답 하나 완성
            res.append(board[:]);  return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue                   # 가지치기: 이 칸은 공격당함 → 시도조차 안 함
            cols.add(c); diag.add(r - c); anti.add(r + c)
            board.append(c)
            backtrack(r + 1, board)      # 다음 행으로 전진
            board.pop()                    # ← 되돌리기(backtrack): 방금 놓은 퀸을 치운다
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)

    backtrack(0, [])
    return res

• 한 행에 퀸 하나로 고정하면 "행 충돌"은 자동으로 사라진다. 남은 검사는 열과 두 대각선뿐.
• 대각선은 좌표로 판별한다: ↘ 방향은 r - c 가, ↙ 방향은 r + c 가 같으면 같은 대각선.
• 전진할 때 상태(집합)에 표시를 추가하고, 되돌아올 때 정확히 그만큼 취소한다 → 상태를 항상 깨끗하게 유지.
• 가지치기가 빠를수록 방문 노드가 급감한다. N-퀸은 비트마스크로 열·대각선을 정수 3개로 표현하면 더 빨라진다.

왜 되돌아가면 빨라질까 — 탐색 트리와 가지치기