N皇后问题是在一个N×N的棋盘上放置N个棋皇后,使得没有两个皇后互相攻击。例如,以下是 4 Queen 问题的解决方案。
N皇后问题是在一个N×N的棋盘上放置N个棋皇后,使得没有两个皇后互相攻击。
我写了函数,但它只打印了 1 个解决方案。我如何更新此功能以打印所有解决方案?
皇后为“q”,空值为“-”
function find_all_arrangements(n) {
const allRes = [];
function isValid(row, col, board) {
// Checks the ← direction
for(var i=0; i<col; i++){
if (board[row][i] === "q") {
return false;
}
}
// Checks the ↖ direction
for(var i=row, j=col; i>=0 && j>=0; i--, j--){
if (board[i][j] === "q") {
return false;
}
}
// Checks the ↙ direction
for(var i=row, j=col; j>=0 && i<n; i++, j--){
if (board[i][j] === "q") {
return false;
}
}
return true;
}
function find(col, result) {
if (col === n) {
allRes.push(result);
return true;
}
for (let i = 0; i < n; i++) {
if (isValid(i, col, result)) {
result[i][col] = "q";
if (find(col + 1, result)) {
return true;
}
result[i][col] = "-";
}
}
return false;
}
function generateBoard(n){
var board=[];
for(var i=0; i<n; i++){
board[i]=[];
for(var j=0; j<n; j++){
board[i][j]="-";
}
}
return board;
}
var board = generateBoard(n);
find(0, board);
return allRes;
}
console.log(find_all_arrangements(4))
最佳答案
差不多了,只需修改查找函数以克隆结果数组并对回溯进行一些调整:
function find(col, result) {
if (col === n) {
// this deep clone the 2d array
allRes.push(JSON.parse(JSON.stringify(result)));
return;
}
for (let i = 0; i < n; i++) {
if (isValid(i, col, result)) {
result[i][col] = "q";
find(col + 1, result)
result[i][col] = "-";
}
}
}
关于javascript - 打印 N-Queen 问题中的所有解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52466114/