N Queens 문제 알고리즘 퍼즐의 JavaScript 구현 솔루션_javascript 기술

퍼즐

N퀸 문제. 두 퀸이 같은 행, 열 또는 대각선에 있지 않은 NxN 체스판에 N개의 퀸을 배치하여 서로 공격할 수 없도록 합니다.

전략

역추적 방법.

자바스크립트 솔루션

여왕 8명 문제를 예로 들어보겠습니다.

코드 복사 코드는 다음과 같습니다.

/**
 * cshao가 14년 12월 28일에 작성했습니다.
 */

함수 getNQueens(order) {
if (주문 < 4) {
console.log('3보다 큰 주문에는 N Queens 문제가 적용됩니다.');
반품;
}

var nQueens = [];
var backTracking = false;
행루프:
for (var row=0; 행 If (nQueens[row] === 정의되지 않음) {
nQueens[행] = [];
}

for (var col=0; col If (nQueens[row][col] === 0) {
계속하세요;
} else if (backTracking && nQueens[row][col] == 1) {
If (col === order-1) {
              ResetRow(nQueens, order, row);
             행 = 행 - 2;
                 계속 rowLoop;
}
nQueens[행][열] = 0;
         역추적 = false;
계속하세요;
}
       
nQueens[행][열] = 1;
If (isQueenValid(nQueens, row, col)) {
행 계속Loop;
} else if (col == order-1) {
backTracking = true;
          ResetRow(nQueens, order, row);
           행 = 행 - 2;
행 계속Loop;
} 그 밖의 {
nQueens[행][열] = 0;
계속하세요;
};
}
}

nQueens 반환;
}

함수 재설정Row(nQueens, 순서, 행) {
for (var col=0; col nQueens[행][col] = 정의되지 않음;
}
}

함수 isQueenValid(nQueens, row, col) {
for (var i=0; i If (nQueens[row][i] == 1) {
거짓을 반환합니다.
}
}
for (var j=1; j if (nQueens[row-j][col]==1 || (nQueens[row-j][col-j]!=정의되지 않음 && nQueens[row-j][col-j]==1) || ( nQueens[row-j][col j]!=정의되지 않음 && nQueens[row-j][col j]==1)) {
거짓을 반환합니다.
}
}
true를 반환합니다.
}

함수 printQueens(queens) {
for (var row=0; row var rowText = '';
for (var col=0; col If (queens[row][col]===정의되지 않음) {
퀸즈[행][열] = 0;
}
rowText = rowText 퀸즈[row][col] ' ';
}
console.log(rowText);
}
}

var queens = getNQueens(8);
printQueens(queens);

결과

코드 복사 코드는 다음과 같습니다.

1  0  0  0  0  0  0  0 
0  0  0  0  1  0  0  0 
0  0  0  0  0  0  0  1 
0  0  0  0  0  1  0  0 
0  0  1  0  0  0  0  0 
0  0  0  0  0  0  1  0 
0  1  0  0  0  0  0  0 
0  0  0  1  0  0  0  0