Bitmasking 기반 N-Queens 제약 조건 검사를 Constant Time으로 최적화

Context

기존 N-Queens 해결 방식은 퀸의 공격 범위를 확인하기 위해 다차원 배열이나 반복문을 통한 탐색이 필요함. 이로 인해 각 위치의 유효성 검사 과정에서 발생하는 시간 복잡도가 전체 성능의 병목 지점으로 작용함.

Technical Solution

• 정수형 변수를 비트 배열로 활용하여 Column, Main Diagonal, Anti-Diagonal의 점유 상태를 관리하는 Bitmasking 도입
• Bitwise OR 연산을 통해 세 가지 제약 조건을 통합하고 NOT 연산으로 배치 가능한 Safe Position을 즉시 도출
• Two's Complement 특성을 이용한 available & -available 연산으로 가장 우측의 가용 비트를 단일 퀸 위치로 빠르게 선정
• 재귀 호출 시 Shift 연산(<< 1, >> 1)을 통해 다음 행으로 이동함에 따라 대각선 공격 범위가 자동으로 갱신되는 구조 설계
• available & (available - 1) 연산을 통해 처리 완료된 비트를 제거하며 효율적인 Backtracking 루프 구현