n - Queens Algorithm

What is n-Queens?

Given a size n by n chessboard, how many ways could you place n queens on that board in such a way that they cannot attach each other?
n Queens알고리즘은 n*n 체스판에서 Queen이 다른 체스말을 공격하지 못하도록 배치하는 방법의 수를 구하는 알고리즘이다.

The n - Queens Problem

체스에서 각각 체스말은 특정한 룰에 따라 움직일 수 있는데, 퀸은 상하좌우, 대각선, 반대각선으로 자유롭게 거리에 상관없이 움직일 수 있다. (n Rooks 는 대각선 룰이 적용이 안된 문제)

Decision Trees

Both n Queens and n Rooks can be described as "decision tree problems."
In a decision tree problem, each action we take in service of solving a problem has implications for future actions we can take toward solving that same problem.

코드 분석

코드스테이츠에서 제공한 바탕으로 구현한다.

BackBone.js

아직 어떻게 사용하는 지는 배우지 않았지만 사용된 BackBone에 대해 간단히 요약하면 이렇게 정의할 수 있을 것 같다.

"모델은 데이터를 가지고 있고 데이터를 수정할 수 있는 권한이 있다.
뷰는 이 데이터를 모델로부터 가져올 수 있고 데이터를 화면에 보여준다. 또 모델에 수정을 요청할 수 있다.
모델이 요청을 받아서 데이터를 변경하면 뷰에게 통보해서 알려주고 뷰는 그 후에 화면을 업데이트 하게 된다."

BoardViewer.js

BoardViewer.html라는 visualizer를 이용해서 실시간으로 코드를 작성하고 변화를 확인할 수 있다. 문제를 풀기 위해 수정할 필요 없이 눈으로 확인만 하면 된다.

Board.js

solvers.js에서 Board 클래스 안에 있는 답을 찾아내도록 만드는 데 도움을 주는 헬퍼 함수들의 모음이다. 여기서 과제는 다음의 헬퍼 함수들을 만드는 것이다.

• hasRowConflictAt: 주어진 행에 충돌하는 말이 있는지 확인합니다.
• hasAnyRowConflicts: 체스 판 위에 행 충돌이 하나라도 있는지 검사합니다.
• hasColConflictAt: 주어진 열에 충돌하는 말이 있는지 확인합니다.
• hasAnyColConflicts: 체스 판 위에 열 충돌이 하나라도 있는지 검사합니다.
• hasMajorDiagonalConflictAt: 주어진 주대각선에 충돌하는 말이 있는지 확인합니다.
• hasAnyMajorDiagonalConflicts: 체스 판 위에 주대각선 충돌이 하나라도 있는지 검사합니다.
• hasMinorDiagonalConflictAt: 주어진 반대각선에 충돌하는 말이 있는지 확인합니다.
• hasAnyMinorDiagonalConflicts: 체스 판 위에 반대각선 충돌이 하나라도 있는지 검사합니다.

Solver.js

우리가 찾아야 할 문제들이 정의되어 있고 답을 구현해야 한다.

• findNRooksSolution: n이 주어졌을 때 n-rooks 문제의 해답 한 개를 반환합니다.
• countNRooksSolutions: n이 주어졌을 때 n-rooks 문제의 전체 해답 개수를 반환합니다.
• findNQueensSolution: n이 주어졌을 때 n-queens 문제의 해답 한 개를 반환합니다.
• countNQueensSolutions: n이 주어졌을 때 n-queens 문제의 전체 해답 개수를 반환합니다.

전략

Solvers를 풀기위해 사용 되어질 헬퍼함수 method를 구현하기 위해서 For loop을 돌려서 1이 있는지 없는지 확인하면 된다.

주어진 행에서 충돌하는 말이 있는지 확인하기 위해서는 위에서 먼저 주어진 get함수를 사용하여 각각의 배열을 순차적으로 탐색하면서 1이 있으면 충돌로 간주되어 카운트를 올려준다. 카운트가 1이상이 되면 충돌이 있는 것으로 간주되어 true를 반환한다. 여기서 위에 주어진 함수들을 해석하고 이해하는데 오래걸렸다.ㅠㅠ

    // 주어진 행(rowIndex)에 충돌하는 말이 있는지 확인합니다.
    hasRowConflictAt: function (rowIndex) {
      let arr = this.get(rowIndex);
      let count = 0;
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] !== 0) {
          count++;
        }
        if (count > 1) {
          return true; //반복문을 모두 실행한 뒤 결과값을 반환해주는 것과 반복문이 실행되면서 결과값을 찾으면 바로 반환해주는 것의의 속도차이  
        }
      }
      return false;
    },

주어진 열에서 충돌하는 말이 있는지 확인하기 위해서는 전체 매트릭스인 2차원 배열을 가지고 와서 순차적으로 비교해주는데, 2차원 배열의 첫번째 인덱스를 순차적으로 증가시켜주고 2번째 인덱스는 열의 인덱스로 고정된 값이 1인지 확인해준다. 마찬가지로 1이면 카운트를 올려주고 1이 1이상 있으면 충돌로 간주된다.
그림을 그려놓고 하면 이해가 빠른데 코드로 구현해 설명하려고 하니 힘들었다.

    // 주어진 열(colIndex)에 충돌하는 말이 있는지 확인합니다.
    hasColConflictAt: function (colIndex) {
      let arr = this.rows(); // 전체 메트릭스 
      let count = 0;
      for (let i = 0; i < arr.length; i++) {
        if (arr[i][colIndex] === 1) {
          count++;
        }
        if (count > 1) {
          return true;
        }
      }
      return false;
    },

    // 체스 판 위에 열 충돌이 하나라도 있는지 검사합니다.
    hasAnyColConflicts: function () {
      for (let i = 0; i < this.get('n'); i++) {
        if (this.hasColConflictAt(i)) {
          return true;
        }
      }
      return false;
    },

주대각선과 반대각선에서 충돌하는 말이 있는지 확인하는 것에서 시간이 오래걸렸다. for loop을 돌리기 위한 범위 지정에서 애를 먹었는데, 이것 저것 해보다가 위에서 범위에 관련하여 주어진 함수를 이용할 수 있었다. 코드를 구현할 때 우리에게 주어진 것이 무엇인가 꼼꼼히 읽어야 함을 다시 한번 느꼈다.
_isInBounds: function (rowIndex, colIndex) 를 이용하여 주어진 좌표가 체스 판에 포함되는 좌표인지 확인 할 수 있었다.
주대각선(/) 일때는 행과 열의 index 값이 하나씩 늘어나고, 반대각선(/)일 때는 행은 하나씩 줄고 열은 index의 값이 하나 늘어났다. 여기서 중요한 부분은 카운트를 올려주면서 열 인덱스도 올려주고 빼줘야 하는 것이다. 이 부분에서 이해가 잘 되지 않아서 그림을 그려 규칙성을 찾아내고 코드로 구현해내는 것은 페어의 도움을 많이 받았다.

//주어진 주대각선에 충돌하는 말이 있는지 확인합니다.
    hasMajorDiagonalConflictAt: function (majorDiagonalColumnIndexAtFirstRow) { //주대각선의 시작점이 인풋 
      let arr = this.rows();
      let count = 0;
      for (let i = 0; i < arr.length; i++) {
        if (this._isInBounds(i, majorDiagonalColumnIndexAtFirstRow) &&
          arr[i][majorDiagonalColumnIndexAtFirstRow] === 1) { //0보다 작으면 매트릭스에 존재하지 않기 때문에 다음 행으로 간다. 

          count++;
        }
        majorDiagonalColumnIndexAtFirstRow++;
        if (count > 1) {
          return true;
        }
      }

      return false;
    },
// 주어진 반대각선에 충돌하는 말이 있는지 확인합니다.
    hasMinorDiagonalConflictAt: function (minorDiagonalColumnIndexAtFirstRow) {
      let arr = this.rows();
      let count = 0;

      for (let i = 0; i < arr.length; i++) {
        // if (minorDiagonalColumnIndexAtFirstRow < 0) {
        //   break;
        // }
        if (this._isInBounds(i, minorDiagonalColumnIndexAtFirstRow) &&
          arr[i][minorDiagonalColumnIndexAtFirstRow] === 1) {
          count++;
        }
        minorDiagonalColumnIndexAtFirstRow--;

      }
      if (count > 1) {
        return true;
      }

      return false;
    },     

그리고 체스판 위에서 충돌이 있는지 확인하기 위해서는 n*n체스판에서 벗어나지 않도록 범위를 설정해주고 for loop을 돌려서 위에서 각각 만든 함수들의 참 거짓을 확인해주면 된다.

solvers............
헬퍼함수들을 완성했으니 이제 본격적으로 solvers를 풀 차례. 알고리즘을 구현해내는 것이라 시간도 오래걸렸을 뿐 아니라, 희미하게 알고 있었던 개념들의 충돌이 머릿속에서 마구 일어났다.

먼저 페어의 도움을 받아 수도코드를 작성해보았다. 어떤 것들을 해야하는지는 대충 알 것 같은데 올바르게 순서들을 나열하는 것이 힘들었다.

//1. nxn 의 빈 체스 판을 만든다.
//2. 반복문으로 체스판의 행을 순환한다.
//3. conflict가 났는지 확인한다.
//4. conflict가 나면 recursion을 이용해 다시 확인
//5. conflict가 안난 상태의 로우의 끝까지 가면 성공

도움을 받아 내가 작성한 코드

window.findNRooksSolution = function (n) {

  let solution = new Board({n: n}); // 빈 체스판 만든다. 
  let isFinish = false;
  
  //재귀함수 생성 
  let recurFn = function (rowIndex) {
    if (solution.hasAnyRooksConflicts()) { // 충돌이 넣었는지 확인 
      return;
    }
    if (rowIndex === n) {
      isFinish = true; // conflict가 안난 상태의 로우의 마지막까지 가면 성공 
      return;
    } else { //conflict가 나지 않으면, 다음행으로 이동 -> togglePiece를 이용해 체스말을 올려주고 다시 빼주어야함. 
      for (let i = 0; i < n; i++) {
        solution.togglePiece(rowIndex, i);
        recurFn(rowIndex + 1);
        if (isFinish) {
          return;
        }
        solution.togglePiece(rowIndex, i);
      }
    }
  }
  recurFn(0);

  console.log('Single solution for ' + n + ' rooks:', JSON.stringify(solution));
  return solution.rows(); //board의 rows는 가지고 있는 이차원 배열을 반환함.  
};

페어의 코드 (유망성 검사를 for loop안에서 했기 때문에 시간복잡도가 줄어듬)

window.findNRooksSolution = function (n) { //깊이 우선탐색
  let solution = undefined;
  //let newBoard = new Board({ n: n });
  let newBoard = new Board({
    n: n
  });
  let isFinish = false;
  let recurFn = function (countN) {
    if (countN === n) {
      isFinish = true;
      return;
    }
    for (let i = 0; i < n; i++) {
      newBoard.togglePiece(countN, i)
      if (!newBoard.hasAnyRooksConflicts()) { //유망성
        recurFn(countN + 1);
      }
      if (isFinish) {
        solution = newBoard.rows();
        break;
      }
      newBoard.togglePiece(countN, i)
    }
  }
  recurFn(0);
  solution = newBoard.rows();
  console.log('Single solution for ' + n + ' rooks:', JSON.stringify(solution));
  return solution;
};

느낀점

단연코 이번 스프린트는 여태까지 했던 스프린트중에서 제일 어려웠다. 알고리즘을 짜는 문제는 둘째치고 주어진 함수를 갖다가 쓰는 것도 버거웠다. 솔직히 혼자 하라고 했으면 못 했을 것 같다. 코딩 경험이 있는 페어가 확실히 옆에서 도와줬기 때문에 수도코드도 작성할 수 있었고 코드도 한줄 한줄 써볼 수 있었다. 또 자칫 넘어갈 수 있었던, 몰랐던 개념들도 중간 중간 설명을 너무 잘해줘서 이해가 더 빨리 된 것 같다... 재귀를 써보는 연습을 많이 해봐야 할 것 같다.