Nqueens
간단한 알고리즘 문제는 여러 방법을 통해 접해보았지만, 이번에 N-Queens라는 알고리즘 문제를 Immersive Course를 통해 접하게 되었다. CodeWars나 repl.it에서도 많은 어려운 문제들을 접해보았지만 이렇게 오랜시간이 소요되는 알고리즘 문제는 처음 풀어보았다.
간단한 알고리즘은 머리로 순서를 정리해가며 풀수있지만, 이번에 해결해야 하는 N-Queens는 내 머리속으로만 정리해서 풀기는 불가능했다. 사실 풀기가 불가능 한 것 뿐만 아니라 문제 접근조차 어려웠다.
이런 상황에 나에게 필요한 것은 하나 뿐이다.
잠깐동안 그 한 가지가 ‘포기’라는 생각이 들었다. 하지만 ‘포기’는 안된다.
다른 한 가지는 멍청한 머리로만 문제에 접근하려 하지 않고, 손으로 N-Queens에 대해 정의하고 접근방법을 써내려 가는 것이다.
N-Queens?
그럼 N-Queens가 어떤 것을 해결해야하는 문제인지 알아보자.
N-Queens는 n*n개 칸이 있는 체스판이 주어졌을때, 서로 잡지 못하도록 하는 Queen을 n개 배치하는 것이 목적이다.
어떤 식으로 이루어졌는지 그림으로 보면 더 쉬우니 바로 밑에 그림을 삽입한다!
4-Queens 배치
만약 4-Queens라는 문제를 풀기위해서는 위 처럼 퀸이 배치된다. 위 그림을 보면 Queen 하나가 놓여지면 가로, 세로 및 대각선에는 어떤 퀸도 배치되면 안된다. 배치되는 순간 서로 잡아먹기때문이다!
단순하다면 아주 단순하다. 하지만 코딩으로 위 그림처럼 퀸이 자동으로 배치되도록 하게된다면 어떨까?
N-Queens 풀이
코드로 어떻게 접근할지 살펴보자. 먼저 체스가 생성되면 체스판에는 아래와 같은 형식으로 표현된다.
borad.attributes = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
];//이 보드는 5*5 체스판이다. //현재는 board[0][0] 즉, 좌표가 (0,0)은 0이며, //0은 아무것도 놓여지지 않은 상태를 의미한다. //위 좌표에 퀸이 놓여지면 그때 0이었던 값은 1로 변한다. 먼저 (0,0)칸에 퀸을 하나 놓으면 같은 열과 행에는 퀸을 놓을 수 없다. 그리고 대각선에도 놓을 수 없다.
hasRowConflict(rowIndex){ //인자로 행의 인덱스를 받는다.
let row = this.attributes[rowIndex];
let num = 0;
for(let i=0; i<row.length; i++){
num += row[i];
if(num >1){return true;}
// 같은 행에 퀸이 2개 이상 있으면 '트루'를 리턴한다. '트루'는 충돌이 있다는 의미다.
}
return false;
}다음은 같은 열에 충돌이 있는지 확인하는 함수가 필요하다.
hasColConflictAt: function (colIndex) { //열 인덱스를 인자로 받는다.
let att = this.attributes;
let num = 0;
for(let i=0; i<att.n; i++){
num += att[i][colIndex]; //각 행마다 인자로 받은 열 인덱스 번호를 확인한다.
if(num > 1){return true} // 같은 열에 퀸이 2개 이상있으면 '트루'를 리턴한다.
}
return false;
}다음은 놓은 자리에서 대각선에 충돌이 있는지 확인하는 함수다.
hasMajorDiagonalConflictAt: function (majorDiagonalColumnIndexAtFirstRow) {
//첫번째 행의 열인덱스를 인자로 받는다.
//하지만 나는 [4,0],[3,0],[2,0],[1,0],[0,0],[0,1],[0,2],[0,3],[0,4]
// -4 -3 -2 -1 0 1 2 3 4
//이런식으로 주대각선의 시작점을 정하고 충돌이 있는지 확인하고자 한다.
let att = this.attributes;
let coordinates = [0,0]; //첫 좌표는 0,0
if(majorDiagonalColumnIndexAtFirstRow < 0) { //들어오는 인자가 음수인 경우
coordinates = [Math.abs(majorDiagonalColumnIndexAtFirstRow), 0];
}else if(majorDiagonalColumnIndexAtFirstRow > 0) { //들어오는 인자가 양수인 경우
coordinates = [0, majorDiagonalColumnIndexAtFirstRow];
}
let num = 0;
for(let i=0; i<att.n-Math.abs(majorDiagonalColumnIndexAtFirstRow); i++) {
if(att[coordinates[0]][coordinates[1]] === 1){
num += 1
if(num > 1){return true} //주대각선에 충돌이 있으면 트루 반환
}
coordinates[0] += 1;
coordinates[1] += 1;
}
return false;
};위와 비슷하게 반대각선도 함수를 작성해준다. 이제 n-queens를 구하기 위한 준비가 거의 끝났다.
이제 위에서 작성한 함수들을 이용해서 하나씩 놓아보고 충돌이 있는지 확인을 하고 충돌이 나면 다른 자리에 퀸을 놓아가면 끝!
countNQueensSolutions = function(n) {
if (n === 0) {
return 1;
}
var solutionCount = 0;
let board = new Board({ n: n }); // n개의 칸을 가진 보드판을 만든다.
iterateBoard(board, 0); //재귀할 함수이다.
function iterateBoard(paramBoard, row) {
for (let c = 0; c < n; c++) {
paramBoard.togglePiece(row, c); //한번 실행시 (row,c)좌표에 퀸을 놓고,
if (
paramBoard.hasColConflictAt(c) ||
paramBoard.hasAnyMajorDiagonalConflicts() ||
paramBoard.hasAnyMinorDiagonalConflicts()
) {
paramBoard.togglePiece(row, c); // 다시 한번 실행시 퀸을 되돌린다.
} else {
if (row === n - 1) {
//마지막 줄에 도달하여 퀸을 놓고 충돌이 없으면,
solutionCount++; // 솔루션카운트를 1 증가시킨다.
paramBoard.togglePiece(row, c); //그리고 놓은 퀸을 다시 뺀다.
} else {
iterateBoard(paramBoard, row + 1); //마지막 줄이 아니면 재귀한다.
paramBoard.togglePiece(row, c); //재귀가 끝나면 놓은 퀸을 뺀다.
}
}
}
}
console.log("Number of solutions for " + n + " queens:", solutionCount);
return solutionCount; // 정답 수의 총 합을 저장해 놓은 solutionCount를 반환한다.
};