题解 | #N皇后问题#

如何判断皇后是否冲突？

• 用一个pos数组记录每一行已经存放的皇后的列数，即pos的下标为皇后的行坐标，pos的内容是皇后的列坐标，之后每次递归的根据这个pos数组中已经记录的皇后的位置，来判断当前位置是否能摆放皇后，如果能摆放皇后就继续递归判断后面的行数中能摆放皇后的位置，直到达到最大行则回溯。
• 设要摆放的皇后的位置为row,col，当前已记录的皇后的位置为i,pos[i]，则两者是否在同一对角线上可以用abs(row-i) == abs(col-pos[i])判断，是否为同一行用row==i判断，是否为同一列用col==pos[i]判断。

参考

https://blog.nowcoder.net/n/ab2b9112a3c84b3baca69fa55ce06bac?f=comment

/**
 * 
 * @param n int整型 the n
 * @return int整型
 */
function Nqueen( n ) {
    // write code here
    let count = 0;
    const pos = new Array(n).fill(-1);  // 存放已经摆放好的皇后的位置信息，即每行的第几列放置皇后
    const _isValid = (row, col, pos) => {
        // 遍历已经记录的行
        for (let i = 0; i < row; ++i) {  // 在当前行之前（i<row）是否和当前摆放的皇后的位置冲突
            if (row === i || col === pos[i] || Math.abs(row-i) === Math.abs(col-pos[i])) {
                return false;
            }
        }
        return true;  // 当前位置可以摆放不冲突的皇后
    }
    const _dfs = (row, n, pos) => {
        if (row === n) {  // 遍历到了最后一行
            count++;
            return;
        }

        // 遍历第row行的n个列，即每行逐个列搜索
        for (let i = 0; i < n; ++i) {
            // 检查该位置是否符合条件
            if (_isValid(row, i, pos)) {
                pos[row] = i;  // 符合条件则记录该位置
                _dfs(row+1, n, pos);  // 递归继续查找剩余行的位置
            }
        }
    }

    _dfs(0, n, pos);  // 从第一行开始递归遍历
    return count;
}
module.exports = {
    Nqueen : Nqueen
};