[JS] N-Queens

N-Queens알고리즘은 재귀의 응용이며, 구현 기간동안 back tracking과 너비우선탐색과(BFS), 깊이우선탐색(DFS)에 대하여 팀원과 충분히 대화하고 고민하며 공부해볼 수 있었다.

백트래킹(back tracking)_되추적은 어떤 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색하는 것이다.

• 유망성(Promising)
  해답이 나올 가능성이 있는 노드(promising)
  해답이 나올 가능성이 없는 노드(non-promising)

상대 공간 트리에서 깊이우선탐색(DFS)를 실시하면서, 유망하지 않은 노드는 가지쳐서(pruning)검색을 하지 않으며, 유망한 노드에 대해서만 그 노드의 자식노드를 검색함

---

우리 팀에서 (많은 시행착오 끝에) 세운 전략은 아래와 같다.

1. 한 dept는 한 줄의 row 이며 말이 어느 열(column)에 위치하느냐에 따라 모두 다른 경우로 카운팅 되므로 다른 가지(경우의수)로 뿌리내려 내려간다.
2. 해당 위치 열과 행에 말이 도달 한 뒤 유망한 경우 계속진행하며, 유망하지 않은 경우 더이상 진행되지 않으며 counting 되지 않음
3. 최종 개수(열 수)까지 도달하였을 경우 count를 올린다.

 

  if (n === 0 || n === 1) {
    return 1;
  }
  if (n === 2 || n === 3) {
    return 0;
  }

행의 갯수가 0~3일경우 예외의 경우에 해당하므로 예외처리를 해줌.
이후 내부 재귀함수를 돌면서 가지를 뻗어내려간다.

  let storage = [];
  let solutionCount = 0;

  const Tree = function (row, col) {
    this.row = row;
    this.col = col;
    this.children = [];
  }

  Tree.prototype.addChild = function (value) {
    let newTree = Tree(value);
    this.children.push(newTree);
  };

  function diagnoalArr(arr, row, col) {
 	//행, 열 뿐만아니라 좌- 우 대각선을 모두 유망한가 판단
    for (let i = 0; i < arr.length; i++) {
      if (arr[i][0] === row || arr[i][1] === col ||
        Math.abs(arr[i][0] - row) === Math.abs(arr[i][1] - col)) {
        return false;
      }
    }
    return true;
  }


  for (let rt = 0; rt < n; rt++) {
    let colrowArr = [];
    let root = new Tree(0, rt, 1);
    colrowArr.push([0, rt]);
    function treejagui(tree, rowIndex) {
      if (rowIndex >= n) {
        solutionCount++;
        return;
      }
      for (let i = 0; i < n; i++) {
        if (diagnoalArr(colrowArr, rowIndex)) {
          let newTree = new Tree(rowIndex, i);
          colrowArr.push([rowIndex, i]);
          treejagui(newTree, rowIndex + 1);
          colrowArr.pop();
          tree.children.push(newTree);
        }
      }
    }
    treejagui(root, 1);

    storage.push(root);
  }
  return solutionCount;