[Javascript] - N-Queens 구현하기

• N-Queens란 무엇인가
  - N * N의 크기의 체스판에 퀸을 N개 배치하는 문제이다
  - N개의 퀸은 서로 공격할 수 없다
  - 체스에서 퀸은 자신의 위치에서 상하좌우, 그리고 대각선 방향으로 공격을 할 수 있다

8*8의 체스판에서 8개의 퀸을 서로 공격하지 않도록 배치하는 예

- 위의 문제를 구현하기 위해서는 백트렉킹 알고리즘을 사용해야한다

 

• 백트렉킹이란 무엇인가
  - 특정 노드에서 유망성을 점검하고, 유망하지 않다면 그 노드의 부모 노드로 돌아가서 다른 노드에 대한 검색을 계속하는 절차
  
  - 백트렉킹 알고리즘은 전수조사 방법중 하나인 깊이우선탐색으로 시작한다 그리고 각 노드에서 유망하지 않은 노드들은 탐색 하지 않고 유망한 노드에 대해서만 탐색을 진행한다 (가지치기, Pruning)
  
  - 탐색의 순서
   1. 깊이 우선 탐색을 실행
   2. 각 노드의 유망성 검사
   3. 유망하다면 계속 탐색
   4. 유망하지 않다면 부모 노드로 돌아가서 탬색을 진행(백트렉킹)
  
  - 이 방법을 사용하면 깊이 우선 탐색보다 검색의 수를 줄일 수 있다
• 코드 구현 중 어려웠던 부분
  - 코드를 구현할 때 경우의 수를 찾는 부분에서 Math.random() 메소드를 사용하였더니 CallStack이 넘치는 현상이 발생하였다
  
  - 백트렉킹 방식을 사용하지 않고 진행하려니 테스트가 돌아가지않는 오류가 발생하였다
  
  - 아래의 코드는 Queen을 배치하는 것이 아닌 Rook을 배치하는 경우의 수를 찾아내는 코드이다
  
  

<-------------------------------------------------------------------------------------->
window.findNRooksSolution = function (n) {
  var findRooks = new Board({n: n});
  var solution = [];
 
  function recursion(){
    var arr = Array(n).fill(null).map(()=> Array());
 
    for(let i = 0; i < n; i++){
      for(let j = 0; j < n; j++){
          arr[i][j] = 0;
      }
    }
 
    for(let i = 0; i < arr.length; i++){
      arr[i][Math.floor(Math.random() * n)] = 1;
    }
 
    for(let i = 0; i < n; i++){
      findRooks.attributes[i] = arr[i];
    }
 
    if(!findRooks.hasAnyRooksConflicts()){
      solution = arr;
    } else{
      recursion();
    }
  }
 
  recursion();
  
  return solution;
};

 

 

• 시간이 더 주어진다면 구현해보고 싶은 것
  - 위의 코드처럼 Math.random() 메소드를 사용하지 않고 백트렉킹을 사용하여 구현해보는 것
  - Recursion을 사용했을 때 무한루프에 빠지지 않는 방법으로 구현해보는 것
  - 코드의 실행시간을 단축시키는 법을 생각하고 거기에 맞는 솔루션을 찾는 것

 

이번 도전에서는 나의 한계를 너무나 느꼈다. 검색을 사용하지 않고 나만의 방식으로 해결하려니 한계가 보였다

좋은 솔루션이란 무엇인가에 대한 생각을 더욱 하게되는 도전이었다.

시간이 난다면 다시한번 풀어보고 싶은 문제이다.