JavaScript|LeetCode|搜索|51.N皇后

最新推荐文章于 2025-04-04 21:28:30 发布

J_learner

最新推荐文章于 2025-04-04 21:28:30 发布

阅读量256

点赞数

分类专栏： LeetCode 文章标签：算法 javascript

本文链接：https://blog.csdn.net/J_learner/article/details/104881596

版权

LeetCode 专栏收录该内容

43 篇文章

订阅专栏

该博客介绍了使用JavaScript解决LeetCode中的51.N皇后问题。通过回溯法解决，确保无皇后在同一行、同一列或对角线上。利用visitedC、ltToRd和ldToRt数组记录已放置皇后的状态，并逐步填充棋盘。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

法1：回溯
通过之后看了答案，改进了一下
想法：

依次在每行放皇后，row（已经到了第row行，此时第0行到row - 1行都放了皇后，即现在已经放了row个皇后）== n，则将此时的board（放皇后的棋盘）放入答案
因为按行依次放皇后，所以不会有多个皇后在同行，只需考虑同列，左上到右下，左下到右上

同列：visitedC[]数组标记，其中有n个元素
左上到右下：同一线上元素下标特征：（行下标 - 列下标）相同。且（行下标 - 列下标）的结果有限：-(n - 1)到n-1，所以创建数组ltToRd（left-top to right-down）来做标记，元素个数为2n - 1，JavaScript数组可以使用负数下标（例如：8皇后，数组长度为15，访问下标为-7的元素，就是访问下标为8的元素）
左下到右上：同左上到右下。同一线上元素特征：（行下标 + 列下标）相同。（行下标 + 列下标）的结果范围：0到2n - 2，用来做标记的数组ldToRt的元素个数为2n - 1

遍历当前行的所有元素，若符合2.中的条件，则进入下一行

/** 
* @param {number} n 
* @return {string[][]} 
*/
var solveNQueens = function(n) {    
    var board = [], temp = []; // board为棋盘    
    var visitedC = [], ltToRd = [], ldToRt = []; // 已有皇后的列、左上到右下、左下到右上     
    var output = []; // 符合条件的board加入    
    var i = 0;    
    for(i = 0; i < n; i++) {        
        temp[i] = '.';        
        visitedC[i] = false;    
    }    
    for(i = 0; i < 2 * n - 1; i++) { // 8皇后，行-列、行+列 的可能结果有15种        
        // JavaScript可用负的下标，所以更加方便        
        ltToRd[i] = false; // 行 - 列 = -7~7 左上到右下：（行 - 列）相同则在左上到右下的对角线        
        ldToRt[i] = false; // 行 + 列 = 0~14 左下到右上：（行 + 列）相同则在左下到右上的对角线    
    }    
    for(i = 0; i < n; i++) {        
        board[i] = temp.concat([]);    
    }    
    backtrack(board, n, 0, output, visitedC, ltToRd, ldToRt);
    return output;
};

function backtrack(board, n, row, output, visitedC, ltToRd, ldToRt) {    
    if(row == n) { // row：第[0, row - 1]行已经放置了皇后        
        var i = 0, temp = [];        
        for(i = 0; i < n; i++) {            
            temp.push(board[i].join(''));        
        }        
        output.push(temp.concat([]));        
        return;    
    }
    var j = 0;    
    for(j = 0; j < n; j++) {        
        if(visitedC[j] || ltToRd[row - j] || ldToRt[row + j]) {            
            continue;        
        }        
        board[row][j] = 'Q';        
        ltToRd[row - j] = ldToRt[row + j] = visitedC[j] = true;        
        backtrack(board, n, row + 1, output, visitedC, ltToRd, ldToRt);        
        board[row][j] = '.';        
        ltToRd[row - j] = ldToRt[row + j] = visitedC[j] = false;    
    }
}