퇴각검색 알고리즘을 이용한 N-Queen 문제

“누워서 읽는 알고리즘” 책에서 소개된 N-Queen problem을 접하게 되었다. 첫 느낌은 어렵지 않을 것 같았으나 생각보다 쉽지 않았던 문제인 것 같다.

문제는 아래와 같다.

가로 세로 모두 N개의 칸이 있는 체스판 위에 N개의 여왕을 올려놓되 서로 공격해서 잡을 수 없도록 놓을 수 있는 방법은 모두 몇 개인가?

예를 들어 4X4라면 아래와 같이 4개의 Queen을 놓을 수 있다.

“누워서 읽는 알고리즘” 책에서는 퇴각검색(BackTracking) 알고리즘과 함께 소개하고 있다.

퇴각검색이 무엇인지 먼저 소개하고 넘어가기로 한다.

퇴각검색이란 위키피디아에서는 아래와 같이 정의하고 있다.

퇴각검색(영어: backtracking, 한글: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다.

선뜻 이해가 가지 않는다. 아래 설명을 확인해 보자.

주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다.

즉, 위 그림처럼 답을 찾아가면서 막다른 길에 도달 했을 때에는 이전 지점으로 돌아가서 다시 확인 해 보는 것이다. 위키피디아에서는 깊이 우선 탐색으로 이야기 하고 있다.

이런 문제를 경험해 본 사람이 있다면 재귀호출로 구현하면 되겠다는 생각을 했을 것이다.

다시 문제로 돌아가보자. 4X4에서 첫 칸에 Queen을 놓았을 경우부터 확인하게 될 것이다.

경우의 수를 따져 보면 아래 트리처럼 될 것이다.

이를 바탕으로 코드를 구현해 보자.

(Java로 구현한 내용이 아래 github에 있으니 코드가 궁금하다면 참고하면 된다.)

모든 알고리즘 문제가 그러하듯 처음 문제를 해결할 때에는 성능을 생각하지 않고 접근하는 것이 편하다.

여기서는 위 트리처럼 모든 케이스에 대해서 확인해 보는 방법으로 풀어볼 것이다.

알고리즘을 요약해 보면 아래와 같다.

1. 체스판의 첫 칸부터 시작한다.
2. 체스판에 Queen을 놓을 때 해당 칸이 놓을 수 있는지를 체크한다.
3. • 첫 Queen이라면 모든 칸에 놓을 수 있기 때문에 (0, 0) 칸에 놓았다고 가정하고 시작하자.
   • 만약 놓을 수 있다면?
     
   • 해당 칸에 Queen을 놓자.
   • Queen을 놓은 자리가 체스판의 마지막 줄이 아니라면 다음 줄에 Queen을 놓기 위해 2번 작업으로 돌아가 다시 체크한다.
     Queen을 놓고 다음 줄로 넘어가는 이유는 Queen을 놓은 그 줄에는 다른 Queen을 놓을 필요가 없기 때문에 확인할 필요가 없기 때문이다.
   • 만약 마지막 줄이라면 지금까지 놓은 자리는 N-Queen 문제의 답이 된다.
4. 체스판의 모든 케이스에 대해서 확인했다면 정답이 되는 케이스 건수를 확인하면 된다.

코드를 보면 좀 더 쉽게 느껴질 수 있다. 메모리 공간을 절약하기 위해 체스판을 2차원 배열이 아닌 1차원 배열을 사용하였다.

아래 코드는 구현부 중 중요한 역할을 하는 2개의 메서드이다.

private void placeQueens(int board[], int h) { for (int idx = 0; idx < board.length; idx++) { if (canPlaceQueen(board, h, idx)) { board[h] = idx; if (h == board.length - 1) { resultCount++; printBoard(board); } else { placeQueens(board, h + 1); } } } }

private boolean canPlaceQueen(int[] board, int h, int v) { int size = board.length; for (int idx = 0; idx < h; idx++) { if (board[idx] == v) { //같은 라인에 놓인 경우 return false; } else if (Math.abs(idx - h) == Math.abs(board[idx] - v)) { //대각선 라인에 놓인 경우 return false; } } return true; }

• placeQueen(): Queen을 놓는 시도
  
• canPlaceQueen(): Queen을 해당 칸에 놓을 수 있는지 확인
  
• board[h] = idx: (h, idx)에 Queen을 놓는 작업
  

위 3가지가 N-Queen 문제 해결의 핵심이라고 할 수 있다.(상세코드는 github 참고)

TC를 수행해 보면 아래와 같이 결과를 확인할 수 있다.

참고로 15X15를 해결하는데에는 약 55초가 소요되었다.

개선점

위에서 설명한 알고리즘은 성능이 좋은 해결법은 아니라고 생각한다.

성능 개선을 위해서는 placeQueen()과 canPlaceQueen() 메서드의 비효율을 줄이는 작업을 해야 할 것이다. 

• placeQueen()
  Queen을 놓고 이동한 다음 다음 줄 부터 체크하는데, 이를 효율화 하는 방법
  다른 사람이 해결해 놓은 알고리즘을 보면 체스에서 각 Queen 간의 거리를 Knight가 이동할 수 있는 거리의 자리만 체크하는 경우도 있었다.
• canPlaceQueen()
  특정 줄에서 Queen을 놓을 자리가 없을 경우 이전 지점으로 돌아와 다시 확인하는 작업을 하게 되는데, 이 때 중복 체크를 줄이는 방법

다음에 2가지 개선점을 바탕으로 성능 개선을 한 번 해 보아야겠다.

github: https://github.com/tomining/AlgorithmStudy/blob/master/src/main/java/com/algorithm/backtracking/NQueenProblem.java

TC: https://github.com/tomining/AlgorithmStudy/blob/master/src/test/java/com/algorithm/backtracking/NQueenProblemTest.java

---

참고

• http://raisonde.tistory.com/129
  
• https://developers.google.com/optimization/puzzles/queens