8퀸 난제는 체스판 위에 8개의 퀸을 서로 공격하지 않도록 배치하는 고전적인 백트래킹 문제다. 이번 글에서는 재귀적 접근과 반복적 접근 두 가지 방식으로 해결해본다.

재귀적 백트래킹

재귀 방식은 현재 행에 퀸을 배치하고, 유효성 검증 후 다음 행으로 진행하는 구조다. 모든 행에 성공적으로 배치되면 해답을 출력한다.

#include <iostream>
#include <cmath>

const int SIZE = 8;
int board[SIZE + 1];
int solutionCount = 0;

bool isSafe(int row) {
    for (int prev = 1; prev < row; ++prev) {
        if (board[prev] == board[row]) 
            return false;
        if (std::abs(prev - row) == std::abs(board[prev] - board[row])) 
            return false;
    }
    return true;
}

void displaySolution() {
    std::cout << "해 " << ++solutionCount << ": ";
    for (int i = 1; i <= SIZE; ++i)
        std::cout << board[i];
    std::cout << '\n';
}

void placeQueenRecursive(int currentRow) {
    if (currentRow > SIZE) {
        displaySolution();
        return;
    }
    
    for (int col = 1; col <= SIZE; ++col) {
        board[currentRow] = col;
        if (isSafe(currentRow)) {
            placeQueenRecursive(currentRow + 1);
        }
    }
}

반복적 백트래킹

재귀 호출 대신 명시적 스택을 사용하여 동일한 로직을 반복문으로 구현할 수 있다. 스택의 각 인덱스가 행을, 저장된 값이 열을 나타낸다.

#include <iostream>
#include <cmath>

const int BOARD = 8;
int stack[BOARD + 1];
int totalSolutions = 0;
int stackTop;

void printBoardState() {
    std::cout << "해 " << ++totalSolutions << ": ";
    for (int i = 1; i <= BOARD; ++i)
        std::cout << stack[i];
    std::cout << '\n';
}

bool validatePosition(int level) {
    for (int prior = 1; prior < level; ++prior) {
        if (stack[prior] == stack[level]) 
            return false;
        if (std::abs(prior - level) == std::abs(stack[prior] - stack[level])) 
            return false;
    }
    return true;
}

void solveIterative() {
    stackTop = 1;
    stack[stackTop] = 0;
    
    while (stackTop > 0) {
        stack[stackTop]++;
        
        while (stack[stackTop] <= BOARD && !validatePosition(stackTop))
            stack[stackTop]++;
        
        if (stack[stackTop] <= BOARD) {
            if (stackTop == BOARD) {
                printBoardState();
            } else {
                stack[++stackTop] = 0;
            }
        } else {
            stackTop--;
        }
    }
}

핵심 원리

백트래킹의 본질은 깊이 우 탐색(DFS)을 기반으로 한 상태 공간 탐색이다. 핵심 전략은 다음과 같다.

• 현재 경로가 유망한지 검증
• 유망하면 다음 단계로 전진
• 유망하지 않거나 막다른 곳이면 이전 상태로 후퇴
• 모든 가능성을 소진할 때까지 반복

알고리즘 프레임워크 비교

void recursiveBacktrack(int k) {
    if (k > n) {
        // 해답 처리
        return;
    }
    for (int i = lower; i <= upper; i++) {
        state[k] = i;
        if (feasible(k))
            recursiveBacktrack(k + 1);
    }
}

void iterativeBacktrack() {
    initialize();
    int pos = 1;
    while (pos > 0) {
        advanceState(pos);
        if (valid(pos) && pos == n) 
            recordSolution();
        else if (valid(pos)) 
            pos++;
        else 
            pos--; // 백트래킹
    }
}

복잡도 분석

8퀸 문제의 시간 복잡도는 이론적으로 O(N^N)이나, 백트래킹의 가지치기로 실제 탐색 공간은 크게 줄어든다. 8퀸의 경우 총 92개의 해가 존재하며, 대략 15,720번의 노드 방문으로 모든 해를 찾을 수 있다.

공간 복잡도는 재귀의 경우 호출 스택 깊이 O(N), 반복의 경우 명시적 스택 O(N)으로 동일하다.