N-퀸 문제(N-Queens Problem): 백트래킹으로 푸는 체스 퀸 배치 알고리즘

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

체스에서 퀸은 가로, 세로, 대각선 방향 모두로 이동하며 공격할 수 있기 때문에, 같은 행·열·대각선 위에 두 개 이상의 퀸이 존재해서는 안 됩니다.

퀸들의 위치는 이진 행렬(binary matrix)로 표현합니다. 행렬에서 값이 1인 칸은 퀸이 놓인 자리를, 0인 칸은 빈 칸을 의미합니다.

입력과 출력

입력:
체스판의 크기. 일반적으로 8을 사용합니다. (8 × 8은 일반적인 체스판의 크기입니다.)

출력:
N개의 퀸이 배치될 수 있는 행과 열의 위치를 나타내는 행렬.
해가 존재하지 않으면 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은 빈 칸을 나타냅니다.

알고리즘

N-퀸 문제는 한 열씩 퀸을 배치해 보고, 유효하지 않으면 이전 단계로 되돌아가 다른 위치를 시도하는 백트래킹(backtracking) 기법으로 해결할 수 있습니다.

isValid(board, row, col)

입력: 체스판, 검사할 행(row)과 열(col)

출력: 해당 위치에 퀸을 놓는 것이 유효하면 true, 아니면 false

Begin
    현재 열의 왼쪽 같은 행에 퀸이 있다면
        return false
    왼쪽 위 대각선 방향에 퀸이 있다면
        return false
    왼쪽 아래 대각선 방향에 퀸이 있다면
        return false
    return true  // 그 외의 경우는 유효한 위치
End

solveNQueen(board, col)

입력: 체스판, 퀸을 배치하려는 열(col)

출력: 퀸들이 배치된 위치 행렬

Begin
    모든 열이 채워졌다면
        return true
    체스판의 각 행(i)에 대해 반복:
        isValid(board, i, col)이 참이면
            (i, col) 위치에 퀸을 배치
            solveNQueen(board, col+1)이 true이면
                return true
            그렇지 않으면 (i, col) 위치에서 퀸을 제거 (백트래킹)
    return false
End

C++ 구현 예제

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

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;
    }
}

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;
}

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();
}

실행 결과

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

위 결과는 8×8 체스판에서 8개의 퀸이 서로를 공격하지 않도록 배치된 하나의 해를 보여줍니다. 각 행과 열, 그리고 대각선마다 퀸이 정확히 하나씩만 존재함을 확인할 수 있습니다.