Algorithm Guidecomplexity: O(N!)

N-퀸 (N-Queens)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

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 쉽게 이해하기

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

Guide Progress0%