Brute Force의 O(N^N) 복잡도를 Backtracking으로 O(N!)까지 최적화한 N-Queens 설계

Context

모든 가능한 퀸 배치 조합을 탐색하는 Brute Force 방식의 극심한 비용 문제 발생. $N \times N$ 보드 내 모든 셀에 퀸을 배치한 후 유효성을 검사하는 구조로 인해 $O(N^N)$의 시간 복잡도를 가지는 비효율적 아키텍처임.

Technical Solution

• Column-wise Placement 전략을 통한 탐색 공간의 획기적 축소
• 퀸 배치 전 isSafe 함수를 통한 제약 조건 사전 검증으로 불필요한 재귀 호출 차단
• 유효하지 않은 경로 발견 시 즉시 이전 상태로 복구하는 Backtracking 메커니즘 적용
• 행과 열 및 대각선 방향의 충돌 여부를 실시간으로 확인하는 Constraint Checking 로직 구현
• 재귀적 구조를 통한 모든 유효한 보드 구성의 완전 탐색 수행

Impact

시간 복잡도를 $O(N^N)$에서 $O(N!)$으로 단축하여 연산 효율성 개선.