C++ 백트래킹으로 N-퀸(N-Queen) 문제 해결하기

N-퀸(N-Queen) 문제는 체스판 위에 N개의 퀸을 배치하되, 어떤 퀸도 다른 퀸을 공격할 수 없도록 만드는 배치를 찾는 고전적인 알고리즘 문제입니다.

체스의 퀸은 가로, 세로, 대각선 어느 방향으로든 이동하며 공격할 수 있습니다. 따라서 모든 퀸은 서로 다른 행, 서로 다른 열, 그리고 서로 다른 대각선 위에 위치해야 합니다.

이 글에서는 0과 1로 이루어진 이진 행렬을 사용해 퀸의 위치를 표현하며, 가장 대표적인 사례인 8-퀸(8 Queens) 문제를 C++로 해결하는 방법을 단계별로 살펴봅니다.

문제 정의

입력

체스판의 크기 N입니다. 일반 체스판이 8×8 크기이므로 여기서는 8을 사용합니다.

출력

N개의 퀸이 배치될 수 있는 행(row)과 열(column)의 위치를 나타내는 행렬입니다. 만약 해가 존재하지 않으면 false를 반환합니다.

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0

위 출력에서 값 1은 퀸이 놓인 올바른 위치를 의미하고, 0은 체스판의 빈 칸을 나타냅니다.

알고리즘: 백트래킹

이 문제는 백트래킹(backtracking) 기법으로 해결합니다. 첫 번째 열부터 한 열씩 진행하면서 각 행에 퀸을 놓아보고, 해당 위치가 유효하지 않거나 이후 진행이 막히면 퀸을 다시 제거한 뒤(백트래킹) 다음 후보 위치를 시도합니다.

1. isValid(board, row, col)

특정 좌표 (row, col)에 퀸을 놓을 수 있는지 검사하는 함수입니다. 현재 위치를 기준으로 왼쪽 방향만 확인하면 되는데, 그 이유는 오른쪽 열에는 아직 어떤 퀸도 배치되지 않았기 때문입니다.

시작
    현재 열의 왼쪽 같은 행에 퀸이 있으면
        false 반환
    왼쪽 위 대각선에 퀸이 있으면
        false 반환
    왼쪽 아래 대각선에 퀸이 있으면
        false 반환
    true 반환   // 그 외의 경우는 유효한 위치
끝

2. solveNQueen(board, col)

재귀적으로 각 열에 퀸을 배치하는 핵심 함수입니다.

시작
    모든 열이 채워졌으면
        true 반환
    보드의 각 행 i에 대해 반복:
        isValid(board, i, col)이 참이면
            (i, col) 위치에 퀸 배치
            solveNQueen(board, col + 1)의 결과가 참이면
                true 반환
            그렇지 않으면 (i, col) 위치에서 퀸 제거
    false 반환
끝

C++ 전체 구현 코드

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다. 예제에서는 설명을 위해 N을 4로 설정했으며, #define N 값을 8로 변경하면 앞서 본 8×8 체스판 결과를 얻을 수 있습니다.

#include<iostream>
using namespace std;
#define N 4

void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << board[i][j] << " ";
        cout << endl;
    }
}

// (row, col)에 퀸을 놓을 수 있는지 검사
bool isValid(int board[N][N], int row, int col) {
    for (int i = 0; i < col; i++) // 왼쪽 같은 행에 퀸이 있는지 확인
        if (board[row][i])
            return false;
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) // 왼쪽 위 대각선에 퀸이 있는지 확인
            return false;
    for (int i = row, j = col; j >= 0 && i < N; i++, j--)
        if (board[i][j]) // 왼쪽 아래 대각선에 퀸이 있는지 확인
            return false;
    return true;
}

// col번째 열부터 재귀적으로 퀸 배치
bool solveNQueen(int board[N][N], int col) {
    if (col >= N) // N개의 퀸을 모두 성공적으로 배치한 경우
        return true;
    for (int i = 0; i < N; i++) { // 각 행에 대해 퀸 배치 가능 여부 확인
        if (isValid(board, i, col)) {
            board[i][col] = 1; // 유효하면 (i, col)에 퀸 배치
            if (solveNQueen(board, col + 1)) // 다음 열을 재귀적으로 처리
                return true;
            board[i][col] = 0; // 진행이 막히면 퀸을 제거하고 되돌아감(백트래킹)
        }
    }
    return false; // 가능한 배치를 찾지 못한 경우
}

bool checkSolution() {
    int board[N][N];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            board[i][j] = 0; // 모든 칸을 0으로 초기화
    if (solveNQueen(board, 0) == false) { // 0번째 열부터 시작
        cout << "Solution does not exist";
        return false;
    }
    printBoard(board);
    return true;
}

int main() {
    checkSolution();
}

실행 결과 (N = 8)

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0

시간 복잡도

N-퀸 문제를 완전 탐색으로 풀 경우 첫 번째 열에 최대 N가지 선택지가 있으므로 시간 복잡도는 O(N!)입니다. 다만 백트래킹은 유효하지 않은 배치를 조기에 잘라내는 가지치기(pruning)를 수행하기 때문에 실제 탐색량은 이보다 훨씬 적습니다. 참고로 8-퀸 문제의 해는 총 92가지이며, 대칭성을 제외하면 근본적으로 서로 다른 해는 12가지입니다.