题解 | #N皇后问题#

/**
 * 
 * @param n int整型 the n
 * @return int整型
 */
// 回溯+剪枝
function Nqueen( n ) {
    // write code here
    let ans = [];
    const backTrack = (arr) => {
        if(arr.length === n){// 设置递归条件，同时arr.length==n说明所有**行**都找到了放置皇后的位置
            //初始化所有行列的位置并初始化棋盘
            let temp = new Array(n).fill(0).map(_=>new Array(n).fill('.'));
            let ele = arr.map((e,i) => {
                temp[i][e] = 'Q';// 放置皇后的位置
                return temp[i].join('')// 将数组["Q",".",".","."]转换为[Q...]
            })
            ans.push(ele);// 添加答案
            return;
        }
        for(let i=0;i < n;i++){
            if(arr.indexOf(i) < 0){
                let flag = true;
                let cur = arr.length;
                // 判断当前**列**位置是否被使用和
                // 此位置是否与之前的保存的皇后位置构成对角线
                for(let j= 1;cur -j >=0;j++){
                    if(arr[cur -j] === i - j) flag = false;
                }
                for(let j=1;cur-j>=0&&i+j<=n;j++){
                    if(arr[cur -j]===i+j) flag = false;
                }
                flag && backTrack(arr.concat(i));// 递归，寻找下一**行**的皇后位置
            }
        }
    }
    backTrack([])
    return ans.length
}
module.exports = {
    Nqueen : Nqueen
};

/**
 * 
 * @param n int整型 the n
 * @return int整型
 */
// 常用-集合
function Nqueen( n ) {
    // write code here
    let column = new Set();// 标记列不可用
    let pos = new Set();// 标记正斜线不可用
    let neg = new Set();// 标记反斜线不可用
    let result = 0;
    const compute = (i,n) =>{
        if(i === n){
            result ++;
            return;
        }
        for(let j =0;j < n;j++){
            if(column.has(j) || pos.has(i - j) || neg.has(i+j)){
                continue;
            }
            column.add(j);// 列号j
            pos.add(i-j);// 行号i - 列号j 正斜线
            neg.add(i+j);// 行号i + 列号j 反斜线
            compute(i+1,n);// 计算下一行
            // 完成上一步递归计算后，清除
            column.delete(j);
            pos.delete(i-j);
            neg.delete(i+j)
        }
    }
    compute(0,n);
    return result;
    
}
module.exports = {
    Nqueen : Nqueen
};