비재귀적 공간 효율적인 블라인드 접근법을 통한 N-퀸 문제의 모든 가능한 해 찾기

N-퀸 문제는 NxN 체스판 위에 N개의 체스 퀸을 놓되, 서로 공격할 수 없도록 배치하는 문제이다. 체스 퀸은 수평, 수직, 대각선 방향으로 이동할 수 있으므로, 퀸의 이웃 위치는 이 세 방향 모두에서 충돌이 발생하지 않도록 배치되어야 한다. 과학자들은 분기 계수(branching factor)가 거의 선형적으로 증가한다는 사실을 인정하고 있다. 너비 우선 탐색(Breadth-First Search, BFS), 깊이 우선 탐색(Deepth-First Search, DFS), 백트래킹(backtracking) 알고리즘과 같은 인공지능 탐색 기법을 활용하여, 많은 학자들이 이 문제를 분석하고 N-퀸 문제의 가능한 해를 계산하기 위한 다양한 기법을 도출해냈다. BFS와 DFS와 같은 무지식 탐색(informed search)을 포함한 블라인드 접근 방식은 모두 재귀(recursion)를 사용한다. 또한 백트래킹 역시 이 문제의 해를 찾기 위해 재귀를 활용한다. 그러나 이러한 모든 재귀 알고리즘은 제한된 시스템 스택(system stack)을 사용하므로, N의 값이 작더라도 시스템 메모리를 빠르게 고갈시킬 수 있으며, 이는 시스템의 성능에 따라 달라진다. 본 논문은 위의 문제를 다루며, 시스템 메모리 절약을 목적으로 비재귀적 깊이 우선 탐색(DFS) 기반의 접근 방식을 제안한다. 본 연구에서는 깊이 우선 탐색(DFS)을 무지식 탐색 또는 비정보 탐색 기법으로 활용하였다. 실험적 연구 결과는 시간 및 공간 복잡도 측면에서 의미 있는 성과를 도출하였다.