[알고리즘] N-퀸(Queen) 문제 - 코딩밥상

N-Queen 문제

이는 백트래킹 알고리즘을 사용할 수 있는 대표적인 문제중 하나로, 체스에서 여덟 방향으로 모두 움직일 수 있는 퀸 8개를 8*8크기의 체스판 안에 서로 공격할 수 없도록 배치하는 모든 경우를 구하는 문제입니다.

체스판의 칸이 모두 64개이고 그 중 8개의 퀸을 배치할 수 있으므로 후보 해의 수는 총 64C8(조합)개 입니다. 약 44억개가 조금 넘는 후보 해 중에서 실제 해는 92개 뿐입니다.

처음 8개의 퀸 문제는 8*8크기의 체스판을 염두에 두고 제안됐지만 다른 크기의 체스판으로 문제를 축소 및 확장할 수 있기때문에 N개의 퀸 문제라고 불리게 된 것입니다.

 

 이 문제는 백트래킹 알고리즘으로 후보해를 대거 줄여 연산 횟수를 줄일 수 있습니다.

첫 번째 행에 차례대로 퀸을 하나씩 놓았을 때, 한 칸씩 행을 내려가며 놓을 수 있는 자리에 퀸을 놓으면서 다음 단계를 수행하고 만약 새로 놓은 퀸이 기존에 놓여있던 퀸을 위협한다면 함수를 반환해서 백트래킹(이전 부분해로 돌아가서 다음후보를 시도)하는 것입니다.

 

 따라서 이 문제에서 가장 중요한 부분은 백트래킹 조건입니다.

• 수직 방향으로 기존 퀸 위협 : 이전 단계에서 놓은 퀸들이 위치한 열 중 새로 놓은 퀸 위치의 열과 같은 것이 있는지 확인
• 수평 방향으로 기존 퀸 위협 : 이전 단계에서 놓은 퀸들이 위치한 행 중 새로 놓은 퀸 위치의 행과 같은 것이 있는지 확인
• 대각선 방향으로 기존 퀸 위협 : 두 퀸 위치가 |행1 - 행2| = |열1 - 열2| 를 만족하면 위협

위 정리를 토대로 구현해 보겠습니다.

bool IsThreatend(int Columns[], int NewRow){
    int CurrentRow = 0;
    bool Threatened = false;
    
    while(CurrentRow < NewRow){
        if(Columns[NewRow]==Columns[CurrentRow] || abs(Columns[NewRow]-Columns[CurrentRow])==abs(NewRow-CurrentRow)){
            Threatened = true;
            break;
        }
        
        CurrentRow++;
    }
    
    return Threatened;
}

int SolutionCount=0;
void FindSolutionForQueen(int Columns[], int Row, int NumberOfQueens, int SolutionCount){
    if(IsThreatend(Columns, Row)) return;
    
    if(Row == NumberOfQueens-1){
        SolutionCount++;
    }
    else{
        for(int i=0; i<NumberOfQueens; i++){
            Columns[Row+1] = i;
            FindSolutionForQueen(Columns, Row+1, NumberOfQueens, SolutionCount);
        }
    }
}