题解 | N皇后问题

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 the n
 * @return int整型
 */
function Nqueen(n) {
    const columns = new Array(n).fill(false)
    // 左边斜线，x - y相等
    const left = new Array(2 * n - 1).fill(false)
    // 右边斜线，x + y相等
    const right = new Array(2 * n - 1).fill(false)

    function dps(line) {
        if (line === n) return 1
        let res = 0
        for (let i = 0; i < n; i++) {
            const add = line + i
            const substract = line - i + n
            if (columns[i] || right[add] || left[substract]) continue
            // 列
            columns[i] = true
            right[add] = true
            left[substract] = true
            // 斜线
            res += dps(line + 1)
            columns[i] = false
            right[add] = false
            left[substract] = false
            
        }
        return res
    }
    return dps(0)
}
module.exports = {
    Nqueen : Nqueen
};