N-Queen
후보 열은 세 집합으로 즉시 걸러낸다
현재 행의 각 열을 col, row-col, row+col 집합으로 판정하면 재귀 전에 충돌 후보를 제거할 수 있다.
Q 배치됨
안전 후보
열 충돌
대각선 충돌
row 2 후보 판정
4x4 예시
c0
c1
c2
c3
r0
.
Q
.
.
r1
.
.
.
Q
r2
OK
col
diag
col
r3
.
.
.
.
사용 중인 열
{1, 3}
왼쪽 대각선
row-col = {-1, -2}
오른쪽 대각선
row+col = {1, 4}
| 후보 | 집합 검사 | 판정 |
|---|---|---|
| c0 | 열, 두 대각선 모두 비어 있음 | 재귀 진행 |
| c1 | col 집합에 이미 있음 |
제거 |
| c2 | row+col = 4가 이미 있음 |
제거 |
| c3 | col 집합에 이미 있음 |
제거 |
1현재 행 선택
2열 집합으로 1차 제거
3두 대각선 집합 검사
4안전 후보만 재귀
5되돌아오며 표시 해제
핵심: 충돌 검사는 후보 생성 직후에 끝내고, 재귀 이후에는 같은 열과 대각선 표시를 반드시 되돌린다.