Algo · backtrack

N-Queen 가지치기 탐색 트리

한 행에 하나씩 퀸을 놓으며 열과 대각선 충돌을 검사하고 실패한 분기는 즉시 되돌아갑니다.

탐색 단계

n-queen

현재 행에서 가능한 열 후보를 나열합니다.

충돌 없는 위치에 퀸을 임시 배치합니다.

열과 양쪽 대각선이 안전한지 봅니다.

다음 행으로 내려가 같은 검사를 반복합니다.

막히면 배치를 제거하고 다음 후보를 시도합니다.

row → candidate col → 안전성 점검 → recurse → backtrack

N-Queen은 모든 배치를 그리는 문제가 아니라 불가능한 배치를 얼마나 빨리 잘라내는지가 핵심입니다.