[Algorithm] N-Queens

N-Queens

N-Queens Problem은 NxN의 체스판에 N개의 퀸을 서로 충돌하지 않게 놓는 방법 혹은 그 수를 구하는 문제다. 예를 들어 4-Queens의 정답은 두 가지가 가능하다.

N-Queens의 정답을 찾기 위해서 필요한 키워드는 DFS(깊이우선탐색, Depth First Search), 재귀(Recursion), 백트래킹(Back tracking)이다.

DFS

DFS는 트리 구조에서 노드들을 순회하는 방법 중 하나로, 노드가 자식 노드를 가지고 있다면 자식 노드들을 계속해서 파고 들어가는 순회 방식이다. 자식노드가 아닌 형제 노드를 먼저 순회하는 방식인 BFS(너비우선탐색, Breadth First Search)에 비해 메모리를 적게 차지한다는 장점이 있다. 원래 DFS는 맨 밑의 자식까지 탐색을 하는 완전탐색 알고리즘이지만, N-Queens에서는 Back-tracking 방법과 함께 필요없는 노드는 방문하지 않음으로써 탐색 시간을 줄일 수 있다.

재귀

재귀는 큰 문제의 답을 작은 문제의 답에서 찾는 것이 핵심이다. 펙토리얼을 구하는 문제를 예로 들자면, factorial(10) = 10 * factorial(9) = 10 * 9 * factorial(8) ... = 10 * 9 * ... * 2 * factorial(1) 처럼 큰 문제의 답을 작은 문제들의 답으로 부터 구할 수 있을 것이다. 기본적으로 DFS에 재귀가 사용된다. 재귀 알고리즘에는 무한 루프에 빠지지 않기 위해서 탈출 조건이 필요하다. N-Queens에서는 답을 찾았다면 함수를 종료, 답을 못찾았다면 for문을 빠져나옴으로써 무한루프를 피할 수 있다.

백트래킹

백트래킹은 DFS를 개선한 알고리즘이다. DFS이 '모든 방법을 탐색'하는 완전탐색방법이라면, 백트래킹은 정답이 될 수 없는 노드는 탐색하지 않음으로써 탐색 효율을 높이는 방법이다. 가지 않아도 될 길을 '배제' 하여 '시간을 단축' 하는 방법이다. 백트래킹에는 뒤로 돌아가기 위한 조건이 필요하다. N-Queens에서는 충돌여부가 그 조건이 된다. 예를 들어 2개의 퀸을 다음과 같이 놓았다면 이미 충돌이 있기 때문에 3번째 줄 부터는 탐색하지 않고 바로 다음으로 세번째 칸에 퀸을 놓는 순서로 넘어간다.

Code

let countNQueensSolutions = function (n) {
  // 1. nxn 빈 배열을 생성(전부 0으로 초기화)
  var myBoard = new Board({n:n});
  var count = 0;

  var solutionFunction = function(row){
    // 재귀 호출을 이용해 들어오는 파라미터(행)의 값이 n이 되면. 즉, 맨 아래 행으로 왔다면
    if(row === n){
      // 정답을 찾은 것으로 보고, count를 증가시킨 뒤 재귀함수를 빠져나간다.
      count++;
      return;
    }
    else {
      // DFS의 구현. i는 column을 의미한다
      for(let i = 0; i < n; i++){
        // row,i에 퀸을 놓는다.
        myBoard.togglePiece(row, i);
        // 재귀의 구현. 충돌이 없다면 다음 행으로 넘어간다.
        if(!myBoard.hasAnyQueensConflicts()){
          solutionFunction(row + 1);
        }
        // Backtracking 구현. 다시 위의 행으로 올라간 뒤, 다음 열에서 정답을 찾는다.
        myBoard.togglePiece(row, i);
      }
    }
  }
   solutionFunction(0);
   return count;
};