N皇后

[JesseZhao1990]

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    var res = [];
    // 垂直方向的占用情况
    var vertical = {};
    // 水平方向的占用情况
    var horitonal = {};
    // 右倾斜对角线的占用情况
    var diagonalRight ={};
    // 做倾斜对象线的占用情况
    var diagonalLeft = {};
    
    // 尝试在n皇后的问题中，摆放第index行的皇后的位置
    function putQueen(n,index,arr){
        if(n===index){
            res.push(genarateQueen(n,[...arr]));
        }
        for(var i=0;i<n;i++){
            if(!vertical[i] && !horitonal[index] && !diagonalRight[i+index] && !diagonalLeft[index-i+n+1]){
                arr.push(i);
                vertical[i] = true;
                horitonal[index] = true;
                diagonalRight[i+index] = true;
                diagonalLeft[index-i+n+1] = true;
                putQueen(n,index+1,arr);
                arr.pop();
                vertical[i] = false;
                horitonal[index] = false;
                diagonalRight[i+index] = false;
                diagonalLeft[index-i+n+1] = false;
            } 
        }
    }
    
    function genarateQueen(n,arr){
        var result = [];
        for(var i=0;i<n;i++){
            result.push(new Array(n).fill("."));
        }
        
        for(var p=0;p<n;p++){
            result[p][arr[p]] = "Q";
            result[p] = result[p].join("");
        }
        return result;
    }
    
    putQueen(n,0,[]);
    return res;
    
};

解题思路：

每一行只可能存在一个皇后，所以递归地在每一行的每个位置上向后推进，递归下去的条件是水平方向和垂直方向，以及两条对角线上都还未被放置皇后。递归的终止条件就是跑到了最后一行的下一行。此时也是收集到一个满足条件的皇后的时候，再回溯进行下一个收集。

重点内容在于怎么确定两个点在某一个对角线上。我画了示意图。

leetcode原题地址：https://leetcode-cn.com/problems/n-queens/description/