Backtracking | N Queen Problem

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
• 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

N Queen Problem

N Queen Problem 이란 N*N 체스판이 주어졌을 때 N개의 queen을 서로 공격할 수 없는 위치에 배치할 수 있는가에 대한 문제이다.

위 그림처럼 4*4 체스판에 queen을 배치하면 어떠한 여왕도 서로의 공격 경로에 위치하지 않음을 알 수 있다, 그리고 이 배치를 배열로 표현하면 여왕이 있는 곳을 '1', 없는 곳을 '0'으로 표현할 수 있다.

              { 0,  1,  0,  0}
              { 0,  0,  0,  1}
              { 1,  0,  0,  0}
              { 0,  0,  1,  0}

Naive Algorithm

보드에 queen을 배치할 수 있는 경우를 모두 도출한 뒤 제약조건을 만족하는 경우에 출력한다.

시도하지 않은 경우의 수가 있다면
{
    새로운 경우의 수를 생성하고
    만약 queen들이 해당 경우의 수에서 공격할 수 없다면
    {
        경우의 수 출력
    }
}

Backtracking Algorithm

먼저 좌측 첫 번째 column부터 queen들을 배치한다 그리고 queen을 배치할 때 이미 배치된 queen들과 충돌이 발생하는 지 검사한다. 현재 column에서 전투가 발생하지 않는 row가 존재한다면 해당 row 지점에 queen을 배치한다. 만약 충돌이 발생하지 않는 row를 찾을 수 없다면 backtrack 후 false를 return한다.

1. 가장 좌측의 column에서 시작한다

2. 만약 모든 queen들의 배치가 완료되면 true를 return한다.

3. 현재 column에서의 모든 row에 대해 다음을 시도한다.

   a) 만약 queen이 [row, column]에 성공적으로 위치할 수 있으면 체크 후 다음 column으로 넘어가서 재귀탐색한다.

   b) 만약 [row, column]의 배치가 마지막 queen의 배치가 되면 true를 return하여 탐색을 종료한다.

   c) 만약 배치했음에도 이후 단계에서 어떠한 해답이 존재하지 않는다면 backtrack 후 a)로 돌아가 다음 row에 대해 시도한다.

4. 만약 모든 row에 대해 시도했음에도 해당사항이 없으면 false를 return하여 이전 단계에서 backtrack하도록 한다.

C코드

#include <stdio.h>
#define N 4

void printSolution(int board[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            printf(" %d", board[i][j]);
        }
        printf("\n");
    }
}

bool isSafe(int board[N][N], int row, int col)
{
    int i, j;

    for (i = 0; i < col; i++) // 해당 row에 대해
    {
        if (board[row][i] == 1) // 다른 col에 queen이 있다면
        {
            return false; // false 반환
        }
    }

    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 1)
        {
            return false; // 좌측 상단 대각선에 queen 존재 검사
        }
    }

    for (i = row, j = col; i < N && j >= 0; i++, j--)
    {
        if (board[i][j] == 1)
        {
            return false; // 좌측 하단 대각선에 queen 존재 검사
        }
    }

    return true;
}

bool sovleNQUtil(int board[N][N], int col)
{
    if (col >= N)
    {
        return true; // 끝까지 배치했으면 탐색 종료
    }

    for (int i = 0; i < N; i++)
    {
        if (isSafe(board, i, col)) // 유효한 좌표라면
        {
            board[i][col] = 1; // 해당 좌표에 queen 배치
            if (sovleNQUtil(board, col + 1)) // 다음 col 탐색
            {
                return true; // 문제 없으면 true 반환
            }
            else
            {
                board[i][col] = 0; // backtracking
            }
        }
    }
    return false; // 이전 단계로 반환하여 backtrack trigger 작동
}

bool solveNQ()
{
    int board[N][N] = { { 0, 0, 0, 0 }, 
                        { 0, 0, 0, 0 }, 
                        { 0, 0, 0, 0 }, 
                        { 0, 0, 0, 0 } };

    if (sovleNQUtil(board, 0) == false)
    {
        printf("There's no Solution!");
        return false;
    }
    else
    {
        printSolution(board);
        return true;
    }
}

int main()
{
    solveNQ();
    return 0;
}

Python 코드

def printSolution(board):
    for i in range(N):
        for j in range(N):
            print(board[i][j], end = " ") # 한칸씩 띄워서 출력
        print() # 개행

def isSafe(board, row, col):
    for i in range(col):
        if board[row][i] == 1:
            return False # 같은 row에 queen이 있는지 검사

    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False # 좌측 상단 대각선에 queen이 있는지 검사

    for i, j in zip(range(row, N), range(col, -1, -1)):
        if board[i][j] == 1:
            return False # 좌측 하단 대각선에 queen이 있는지 검사

    return True

def solveNQUtil(board, col):
    if col >= N:
        return True # col이 끝까지 도달하면 탐색 종료

    for i in range(N):
        if isSafe(board, i, col): # 유효한 위치라면
            board[i][col] = 1 # 해당 좌표에 queen 배치
            if solveNQUtil(board, col + 1) == 1: # 다음 col 탐색 진행
                return True # 이후에 문제가 없으면 이전 단계에 통보
            else:
                board[i][col] = 0 # 문제가 발생한다면 backtrack
    return False # 이전 단계에 통보하여 backtrack trigger 작동

def solveNQ():
    board = [ [0, 0, 0, 0], 
              [0, 0, 0, 0], 
              [0, 0, 0, 0], 
              [0, 0, 0, 0] ]

    if solveNQUtil(board, 0) == False:
        print("There's no Solution")
    else:
        printSolution(board)

global N
N = 4
solveNQ()

C++ 코드

c++ 코드는 C 코드와 문법을 비교했을 때 출력문을 제외하고는 없어서 주석을 생략하였다.

#include <bits/stdc++.h>
using namespace std;
#define N 4

void printSolution(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 isSafe(int board[N][N], int row, int col)
{
    int i, j;
    for (i = col; i >= 0; i--)
    {
        if (board[row][i] == 1)
        {
            return false;

        }
    }
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 1)
        {
            return false;
        }
    }
    for (i = row, j = col; i < N && j >= 0; i++, j--)
    {
        if (board[i][j] == 1)
        {
            return false;
        }
    }
    return true;
}

bool solveNQUtil(int board[N][N], int col)
{
    if (col >= N)
    {
        return true;
    }

    for (int i = 0; i < N; i++)
    {
        if (isSafe(board, i, col) == true)
        {
            board[i][col] = 1;
            if (solveNQUtil(board, col + 1) == true)
            {
                return true;
            }
            else
            {
                board[i][col] = 0;
            }
        }
    }
    return false;
}

bool solveNQ()
{
    int board[N][N] = { { 0, 0, 0, 0 }, 
                        { 0, 0, 0, 0 }, 
                        { 0, 0, 0, 0 }, 
                        { 0, 0, 0, 0 } }; 
    if (solveNQUtil(board, 0) == true)
    {
        printSolution(board);
        return true;
    }
    else
    {
        cout << "There's no Solution!" << endl;
        return false;
    }

}

int main()
{
    solveNQ();
    return 0;
}

참고자료

1. N Queen Problem | Backtracking-3