N-Queens

 

N queens 알고리즘 해결방안 수도코딩

 

 

                                                            colindex

                                                              0 1  2  3

                                  rowindex   0  [[ㅇㅇㅇㅇ]
                                                        1   [ㅇㅇㅇㅇ]
                                                        2   [ㅇㅇㅇㅇ]

                                                        3   [ㅇㅇㅇㅇ]]

 

 ㅇ이 빈자리 , queen 이 놓은 자리를 1 로 표시.

 

 

 

한 줄의 rowIndex 확인함수

 hasRowConflictAt: function (rowIndex) {
      // 가로 배열에 1 에 중복이 있는 지 확인
      //console.log(this)
      let rowcheck = this.attributes[rowIndex]; //rowIndex를 가져오면 가로 한줄..
      // this.get 하면 rowIndew 넘버에 해당하는 가로한줄배열을 가져옴.
      let count = 0;

      //console.log('this Get rowIndex',this.get(rowIndex))
      //console.log('this Get n ',this.get("n"))

      for (let i = 0; i < rowcheck.length; i++) {
        if (rowcheck[i] === 1) {
          count++;
        }
        if (count > 1) {
          return true;
        }
      }
      return false; // fixme true = 충돌 되는 자리, false = 놓을 수 있는 자리
    }

this 의 attributes 속성에서 값을 불러와서 가로 줄 배열에 1 이 한 개 이상 있으면 true , 없으면 false 를 리턴.

 

n줄의 rowIndex 확인함수

hasAnyRowConflicts: function () {
      // 모든 각각의 가로줄에 1 중복이 있는 지 확인.
      let n = this.attributes['n']; // 총 체스판의 크기(각 가로줄의 i를 모두 확인) (n * n);
      let check = Boolean;
      for (let i = 0; i < n; i++) {
        check = this.hasRowConflictAt(i);
        // 여기서 this는 큰배열 a[ [b],[c],[d],[e] ] a[rowindex][i]
        if (check === true) {
          return true;
        }
      }
      return false; // fixme
    }

rowindex 의 queen 이 놓을 수 있는 자리 모두 확인.

 

한 줄의 colIndex 확인함수

hasColConflictAt: function (colIndex) {
      // 모든 row를 돌며 row들에 coIndex(n번쨰 인자) 를 검사
      let n = this.attributes['n']
      //console.log('colIdnex :',colIndex)
      //console.log(this.get(0),this.get(1),this.get(2),this.get(3))
      let count = 0;

      for(let i = 0; i < n; i++){
        if(this.attributes[i][colIndex]===1){
          count++
        }
      }
      if(count > 1){
        return true
      }
      return false;
    }

세로의 경우 rowidex[i] 값으로 확인.

 

n줄의 colIndex 확인함수

hasAnyColConflicts: function () {
      let n = this.get("n"); // 총 체스판의 크기 (n * n);
      let check = Boolean;
      for (let i = 0; i < n; i++) {
        check = this.hasColConflictAt(i);
        if (check === true) {
          return true;
        }
      }
      return false; // fixme
    }

colindex 의 queen 이 놓을 수 있는 자리 모두 확인.

 

한 줄의 우상 대각선 확인함수

 hasMajorDiagonalConflictAt: function (majorDiagonalColumnIndexAtFirstRow) {
      //console.log(majorDiagonalColumnIndexAtFirstRow)
      // -가 나온다..colIndex네
      let result = [];
      let n = this.attributes['n'];
      let board = this.attributes;
      let count = 0;
      
      for(let i = 0; i < n; i++){
        result.push(board[i][majorDiagonalColumnIndexAtFirstRow])
        majorDiagonalColumnIndexAtFirstRow++
      }

      result.forEach(function(item){
        if(item ===1){
          count++
      }})

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

반복문을 돌려서 i 값으로 rowImdex 증가하고

majorDiagonalColumnIndexAtFirstRow++ 로 colindex 값 증가 

 

n줄의 우상 대각선 확인함수

hasAnyMajorDiagonalConflicts: function () {
      let n = this.attributes['n'];
      let result = Boolean;

      for(let i = -(n-2); i < n-2; i++){
        result = this.hasMajorDiagonalConflictAt(i);
        if(result){
          return true;
        }
      }
      return false;
}

우상 대각선의 경우 0,0 포인트에서 n-2 만큼 대각열이 생기기 때문에 반복문의 조건을 위와 같이 설정.

한 줄의 좌상 대각선 확인함수

 hasMinorDiagonalConflictAt: function (minorDiagonalColumnIndexAtFirstRow) {
     // console.log(minorDiagonalColumnIndexAtFirstRow)
      // colIndex네 이것도 검사할 줄 스타트포인트

      let n = this.attributes['n'];
      let board = this.attributes;
      let count = 0;

      for(let i = 0; i < n; i++){
        if(board[i][minorDiagonalColumnIndexAtFirstRow]===1){
          count++
        }
        if(count > 1){
          return true;
        }
        minorDiagonalColumnIndexAtFirstRow--
      }
      return false;
}

가로 줄 배열의 i를 반복하면서 인자로 들어오는 세로 줄 포인트를 확인.

n줄의 좌상 대각선 확인함수

hasAnyMinorDiagonalConflicts: function () {
      let n = this.attributes['n'];
      let result = Boolean;

        for(let i = 1; i < n+(n-2); i++){
          result = this.hasMinorDiagonalConflictAt(i);
          if(result === true){
            return true;
          }
        }
        return false;
}

좌상 대각선의 경우 n+(n-2) 세로 줄에서 대각열이 생성되는만큼의 조건으로 반복문의 조건을 위와 같이 설정.

 

---

rook solution

indow.findNRooksSolution = function (n) {
  
var board = new Board({"n":n});
var boardPan = board.rows();

for(let row  = 0; row < boardPan.length; row++){
  for(let col = 0; col < boardPan.length; col++){
    boardPan[row][col] = 1;
    if(board.hasAnyRooksConflicts()){
      boardPan[row][col] = 0;
    }
  }
}
return boardPan;
};

new 생성자로 빈 보드를 생성하고 이중반복문을 통해 한칸 씩 colindex , rowindex를 검사하면서 반복문을 돌아 놓을 수 있는 자리에
rook 을 배치.

 

n rooks solution count 

window.countNRooksSolutions = function (n) {

  var board = new Board({n});
  var boardPan = board.rows();
  var solutionCount = 0;

  function recur(colIndex){

    if(colIndex===boardPan.length){
      solutionCount++
    }
    for(let i = 0; i < boardPan.length; i++){
      boardPan[i][colIndex] = 1
      if(!board.hasAnyRooksConflicts()){
            recur(colIndex + 1);
      }
      boardPan[i][colIndex] = 0;
    }
  }
 recur(0)
  console.log("Number of solutions for " + n + " rooks:", solutionCount);
  return solutionCount;
};

재귀적으로 각 colindex가 모두 가로세로 확인 함수를 통과하면 count++ , colindex 를 증가시키면서 재귀적으로 실행.

 

queen solution

window.findNQueensSolution = function (n) {
  var board = new Board({ 'n': n });
  var boardPan = board.rows();
  var solution = undefined; // fixme

  if (n === 0 || n === 2 || n === 3) {
    return boardPan;
  }
  function recur(col){
    if(col === boardPan.length){
      solution = boardPan;
      return
    }
    for(let i = 0; i < boardPan.length; i++){
      boardPan[i][col] = 1;
      if(!board.hasAnyQueenConflictsOn(i,col)){
        recur(col+1);
      }
      if(solution!==undefined){
        break;
      }
      boardPan[i][col] = 0;
    }
  }
  recur(0)

n의 갯수에 따라 조건을 정하고 그 후 똑같이 모든 자리에 가로세로대각확인 함수를 대입하면 colIndex 를 증가시키며 모든 칸을 확인.

그 때의 배열을 solution 에 대입하고 break. 

 

n queens solution count 

window.countNQueensSolutions = function (n) {
  var solutionCount = 0; // fixme
  var board = new Board({ 'n': n });
  var boardPan = board.rows();


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

  function recur(rowIndex) {
    if (rowIndex === boardPan.length) {
      solutionCount++;
      return;
    }
    for (let i = 0; i < boardPan.length; i++) {
      boardPan[rowIndex][i] = 1;
      if (!board.hasAnyQueensConflicts()) {
        recur(rowIndex + 1);
      }
      boardPan[rowIndex][i] = 0;
    }
  }
  console.log(board)

  recur(0)

  console.log("Number of solutions for " + n + " queens:", solutionCount);
  return solutionCount;

재귀적으로 각 colindex가 모두 가로세로대각 확인 함수를 통과하면 count++ , colindex 를 증가시키면서 재귀적으로 실행.