정의

N-Queens는 N x N 체스판에 N개의 퀸을 서로 공격하지 못하게 배치하는 문제입니다. 백트래킹을 사용하여 가능한 모든 배치를 탐색하면서, 불가능한 경우 바로 되돌아갑니다.

핵심 특성

• ✓한 행에 하나의 퀸만 배치 가능
• ✓같은 열, 대각선에 다른 퀸이 없어야 함
• ✓불가능하면 이전 상태로 백트래킹
• ✓가지치기(pruning)로 탐색 공간 축소

시간 복잡도