Algorithm Guidecomplexity: O(N!)

N-퀸 (N-Queens)

N×N 체스판에 서로 공격하지 못하도록 N개의 퀸을 놓는 문제입니다. 한 행씩 퀸을 시도하고 열·대각선 충돌을 검사하며, 막히면 직전 선택으로 되돌아가는(backtrack) 전형적인 백트래킹입니다.

01N-퀸 (N-Queens)

알고리즘 작동 원리 탐색

4-퀸 문제. 4×4 판에 서로 공격하지 못하도록 퀸 4개를 놓습니다. 한 행에 하나씩, 열·대각선이 겹치지 않게 시도합니다.

Row 0 · 첫 행의 (0,0)에 퀸을 놓습니다.

Row 1 · (1,1)은 대각선 충돌. (1,2)는 안전하므로 퀸을 놓습니다.

Row 2 · 네 칸 모두 열 또는 대각선에서 충돌합니다. 놓을 곳이 없습니다.

되돌아가기(backtrack) · Row 1의 퀸을 한 칸 옮겨 (1,3)에 다시 놓습니다.

Row 2 · 이번엔 (2,1)이 안전합니다. 퀸을 놓습니다.

Row 3 · 마지막 행의 모든 칸이 충돌합니다. 다시 막혔습니다.

연쇄적으로 되돌아가 Row 0의 퀸까지 (0,1)로 옮기고, 그 가지부터 다시 탐색합니다.

Row 1 (1,3), Row 2 (2,0)을 차례로 안전하게 배치합니다.

Row 3 · (3,2)에 마지막 퀸을 놓습니다. 어떤 퀸과도 충돌하지 않습니다 — 네 퀸 완성!

해 [1, 3, 0, 2] 발견. 충돌이 보이면 즉시 되돌아가 가지를 쳐내므로, 전체 N! 배치를 다 보지 않고 해에 도달합니다.

Live Python

1def solve(row, board, n):

2 if row == n:

3 return board[:] # 해 발견

4 for col in range(n):

5 if safe(board, row, col):

6 board.append(col) # 배치

7 res = solve(row + 1, board, n)

8 if res: return res

9 board.pop() # 되돌아가기

10 return None

1 / 11

02 쉽게 이해하기

For Everyone

🔑핵심 동작

한 줄에 하나씩 놓아 보고, 앞서 놓인 말과 같은 열이나 대각선에 걸리면 그 자리를 물립니다. 끝까지 막히면 앞 줄로 돌아가 다른 칸을 고릅니다.

💡쉽게 말하면

한 행에 퀸을 하나씩 놓아보고, 열·대각선이 겹치면 즉시 직전 선택으로 되돌아가 다른 칸을 시도합니다.

안 되는 가지를 빨리 쳐내 전체 N!을 다 보지 않아요.

📍어디에 쓰나

–제약 충족 문제
–좌석·자원 배치
–퍼즐 풀이

03 파이썬 구현 코드

N-퀸 (N-Queens)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def solve_n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    board, solutions = [], []

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            board.append(col)
            backtrack(row + 1)
            board.pop()
            cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)

    backtrack(0)
    return solutions

04 자주 묻는 질문

FAQ

N-퀸 (N-Queens)란 무엇인가요?+

N-퀸 (N-Queens)의 시간복잡도는 어떻게 되나요?+

N-퀸 (N-Queens)의 시간복잡도는 O(N!) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

N-퀸 (N-Queens)은(는) 어디에 사용하나요?+

제약 충족 문제, 좌석·자원 배치, 퍼즐 풀이.

N-퀸 (N-Queens)를 쉽게 비유하면?+

한 줄에 하나씩 놓아 보고, 앞서 놓인 말과 같은 열이나 대각선에 걸리면 그 자리를 물립니다. 끝까지 막히면 앞 줄로 돌아가 다른 칸을 고릅니다.