パズル
N クイーンの問題。 NxN チェスボード上に N 個のクイーンを配置します。このとき、互いに攻撃できないように、同じ行、列、または対角線上に 2 つのクイーンが存在しません。
戦略
バックトラッキング方法。
JavaScript ソリューション
8 クイーンズ問題を例に挙げます:
関数 getNQueens(order) {
if (順序
console.log('3 を超える注文には N クイーンズ問題が適用されます');
戻る;
}
var nQueens = [];
var backTracking = false;
行ループ:
for (var row=0; row
nQueens[行] = [];
}
for (varcol=0;col
続行;
} else if (backTracking && nQueens[row][col] == 1) {
If (col === order-1) {
resetRow(nQueens, order, row);
行 = 行 - 2;
continue rowLoop;
}
nQueens[行][列] = 0;
backTracking = false;
続行;
}
nQueens[行][列] = 1;
If (isQueenValid(nQueens, row,col)) {
rowLoop を継続します;
} else if (col == order-1) {
backTracking = true;
resetRow(nQueens, order, row);
行 = 行 - 2;
rowLoop を継続します;
} else {
nQueens[行][列] = 0;
続行;
};
}
}
nQueens を返します;
}
関数resetRow(nQueens, order, row) {
for (varcol=0;col
}
}
関数 isQueenValid(nQueens, row,col) {
for (var i=0; i
関数 printQueens(queens) {
for (var row=0; row
for (varcol=0;col
クイーン[行][列] = 0;
}
rowText = rowText queens[row][col] ' ';
}
console.log(rowText);
}
}
var queens = getNQueens(8);
printQueens(クイーン);
結果