Algorithm Guidecomplexity: O(N!)

N-퀸 (N-Queens)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

N-Queens · N=4

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

Logic Node1 / 11

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

02 Understand It Simply

For Everyone

🔑Analogy

사람들을 서로 시야가 닿지 않게 한 줄씩 자리를 시도하며 앉히는 것과 같습니다.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 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 Frequently Asked Questions

FAQ

What is N-퀸 (N-Queens)?+

What is the time complexity of N-퀸 (N-Queens)?+

The time complexity of N-퀸 (N-Queens) is O(N!). Follow the step-by-step visualization to see exactly why.

Where is N-퀸 (N-Queens) used?+

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

What's a simple analogy for N-퀸 (N-Queens)?+

사람들을 서로 시야가 닿지 않게 한 줄씩 자리를 시도하며 앉히는 것과 같습니다.

→ Backtracking — see allRelated

Guide Progress0%