N-Queens 시각화
백트래킹으로 N개의 퀸을 서로 공격하지 않게 배치하는 과정을 관찰합니다
백트래킹★★☆
속도
1 / 1해 개수: 0시도 횟수: 0
보드 크기8 x 8
퀸공격 범위시도 중충돌
각 행에 퀸을 배치하며, 충돌이 발생하면 되돌아가는 과정을 관찰하세요.
각 행에 퀸을 배치하며, 충돌이 발생하면 되돌아가는 과정을 관찰하세요.
N-Queens 문제란?
N개의 퀸을 서로 공격하지 못하도록 배치하는 조합 최적화 문제입니다. 백트래킹의 대표적인 예제입니다.
사용 방법
- 1보드 크기를 4~12 사이에서 선택하세요
- 2재생 버튼으로 백트래킹 과정을 관찰하세요
- 3보라색 원은 배치된 퀸, 빨간 반투명은 공격 범위입니다
- 4노란색은 시도 중인 위치, 빨간 강조는 충돌입니다
- 5코드 탭에서 실행 줄이 하이라이트됩니다
동작 원리
- 1첫 번째 행부터 각 행에 하나의 퀸을 배치합니다
- 2같은 열 또는 대각선인지 확인합니다
- 3충돌이 없으면 다음 행, 있으면 다음 열을 시도합니다
- 4모든 열에서 충돌이면 이전 행으로 되돌아갑니다
- 5시간 복잡도 O(N!), 가지치기로 실제 탐색량은 적음
실무 활용
- •제약 만족 문제 — 스케줄링, 자원 할당
- •VLSI 회로 설계 — 충돌 없는 배치/배선
- •병렬 컴퓨팅 교육 — 탐색 트리 병렬화
- •AI 탐색 전략 벤치마크
비슷한 알고리즘
- •백트래킹 vs 분기한정법 — 분기한정법은 추가로 최적값 하한을 계산
- •스도쿠 풀기 — 같은 백트래킹 구조
- •그래프 색칠 — 인접 노드에 다른 색 배정
학습 팁
- •N=4에서 해가 2개뿐인 것을 확인하세요
- •N이 커질수록 시도 횟수가 급증합니다
- •빨간 공격 범위로 왜 배치 불가능한지 이해하세요
- •첫 번째 퀸 위치가 전체 탐색량에 큰 영향을 미칩니다
자주 묻는 질문
Q. N=1,2,3에도 해가 있나요?
A. N=1은 자명한 해, N=2와 N=3은 해가 없습니다.
Q. 시간 복잡도는?
A. 최악 O(N!), 가지치기로 실제 탐색량은 훨씬 적습니다.
Q. 8-Queens의 해는 몇 개?
A. 92개. 회전/대칭 제거 시 12개의 기본 해가 있습니다.