javascript/school/nqueens.js · 1789 字节 · 下载原文
// 八皇后问题 —— 经典回溯递归练习(求 8x8 棋盘上全部 92 个解,这里只报解的个数与第一个解)
// Eight queens puzzle -- the classic backtracking/recursion exercise (all 92 solutions on 8x8;
// here we print only the count and the first solution)
//
// 来源 / Source: Rosetta Code「N-queens problem」JavaScript 条目(GFDL 1.2 / CC-BY-SA 3.0)
// https://rosettacode.org/wiki/N-queens_problem
// 改编 / Adapted: 输出由 console.log 整个解集改为本平台的 println_int(解数 + 第一个解的 8 个列号)。
// Output changed from console.log of the whole solution set to this platform's println_int
// (the number of solutions plus the 8 column numbers of the first solution).
function queenPuzzle(rows, columns) {
if (rows <= 0) {
return [[]];
} else {
return addQueen(rows - 1, columns);
}
}
function addQueen(newRow, columns, prevSolution) {
var newSolutions = [];
var prev = queenPuzzle(newRow, columns);
for (var i = 0; i < prev.length; i++) {
var solution = prev[i];
for (var newColumn = 0; newColumn < columns; newColumn++) {
if (!hasConflict(newRow, newColumn, solution))
newSolutions.push(solution.concat([newColumn]));
}
}
return newSolutions;
}
function hasConflict(newRow, newColumn, solution) {
for (var i = 0; i < newRow; i++) {
if (solution[i] == newColumn ||
solution[i] + i == newColumn + newRow ||
solution[i] - i == newColumn - newRow) {
return true;
}
}
return false;
}
var solutions = queenPuzzle(8, 8);
println_int(solutions.length);
var first = solutions[0];
for (var c = 0; c < first.length; c++) {
println_int(first[c]);
}