← 都来码 / Dolaima← 例程索引javascript/school/nqueens.js 原文

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]);
}