n皇后问题

问题:

在n*n的棋盘上放置n个皇后,要求同一行,同一列上只能有一个皇后,并且每个皇后的斜率为正负1的直线上也不能有皇后

思路:

经典的回溯法。参考这里:https://juejin.im/post/5accdb236fb9a028bb195562

代码:

// n queens problem
function nQueens(n) {
    var result = [];
    var k = 0;
    result[k] = 0;
    while (k >= 0) { //when k<0; there is no solution for this 'n'
        result[k]++;
        while (result[k] <= n && !place(result, k))
            result[k]++; //find proper position for the current queen
        if (result[k] <= n) {
            if (k == n - 1) break; //the last queen is put at a proper position, end
            else {
                k++;
                result[k] = 0; //turn to next queen and init her position
            }
        } else {
            result[k] = 0; //before feedback, we should reset the position or it will influence next time we find proper position for her
            k--;
        }
    }
    return result;
}
//judge the current position is proper or not
//k is the serial number of the queen
//res is the array of a partial solution
function place(res, k) {
    var abs = Math.abs;
    for (var i = 0; i < k; i++) {
        if (res[i] == res[k] || abs(res[i] - res[k]) == abs(i - k))
            return false;
    }
    return true;
}
 
var start = Date.now();
var result = nQueens(30);
var end = Date.now();
console.log(result, end - start);

 

知识共享署名4.0国际许可协议,转载请保留出处; 部分内容来自网络,若有侵权请联系我:前端学堂 » n皇后问题

赞 (1) 打赏

评论 0

如果对您有帮助,别忘了打赏一下宝宝哦!

支付宝扫一扫打赏

微信扫一扫打赏