N-Queen 문제 풀이 (백트래킹)

이 글은 N-Queen 문제를 통해 Backtracking에 대한 핵심을 이해하고 활용하는 것을 다루고 있습니다.

문제 정의

N-Queen 문제는 N x N 크기의 체스판 위에 N개의 퀸(Queen)을 서로 서로 공격하지 않도록 배치하는 경우의 수를 찾는 고전적인 백트래킹(Backtracking) 문제입니다.

핵심 아이디어

1. 각 행(Row)에 하나의 퀸만 배치합니다.
2. 매 행마다 모든 열(Column)을 순회하면서,
   • 세로줄, 좌우 대각선에 다른 퀸이 없는지를 검사합니다.
3. 배치 가능하면 다음 행으로 넘어갑니다.
4. 끝까지 도달하면 정답으로 출력하고,
5. 중간에 배치 실패 시에는 이전 행으로 되돌아가 위치를 바꿉니다. (백트래킹)

시도: 퀸을 배치한다
성공하면:
다음 행으로 이동
실패하면:
배치 취소 (백트래킹)
다음 위치에 퀸을 다시 시도

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void SolveNQueen(int CurrentRow, vector<vector<bool>>& Board, bool& bHasSolution)
{
    int Size = Board.size();

    for (int Col = 0; Col < Size; ++Col)
    {
        bool bCanPlace = true;

        // 위쪽 행들만 검사하면 충분
        for (int Row = 0; Row < CurrentRow; ++Row)
        {
            if (Board[Row][Col] ||  // 같은 열
                (Col - (CurrentRow - Row) >= 0 && Board[Row][Col - (CurrentRow - Row)]) ||  // 좌상 대각선
                (Col + (CurrentRow - Row) < Size && Board[Row][Col + (CurrentRow - Row)]))  // 우상 대각선
            {
                bCanPlace = false;
                break;
            }
        }

        if (!bCanPlace)
            continue;

        // 배치 시도
        Board[CurrentRow][Col] = true;

        if (CurrentRow == Size - 1)
        {
            bHasSolution = true;
            for (const auto& Row : Board)
            {
                for (bool Cell : Row)
                    cout << (Cell ? "* " : "- ");
                cout << '\n';
            }
            cout << '\n';
        }
        else
        {
            SolveNQueen(CurrentRow + 1, Board, bHasSolution);
        }

        // 백트래킹
        Board[CurrentRow][Col] = false;
    }
}

int main()
{
    int N;
    cout << "Enter the number of queens: ";
    cin >> N;

    vector<vector<bool>> Board(N, vector<bool>(N, false));
    bool bHasSolution = false;

    SolveNQueen(0, Board, bHasSolution);

    if (!bHasSolution)
        cout << "There is no solution!" << endl;
}