51 N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

题解

N皇后是经典的回溯并且剪枝的问题，不过是二维的，但是我们可以降维降为一维。

降维：按照行处理，递归树的每一层是当前一行所有可能选项，递归树的子树是每一行。

按照递归的三部曲：

一，定义函数的参数以及返回值，这里我们参数可以是 n，currentResults（表示现在存的结果），row（现在处理到第几层） 二，递归的终止条件，这里我们可以判断currentResults.length === n 就可以终止 三，递归的单层逻辑，我们对于每一层，都有n中可能得选项

//假设我们的函数是solveNQueensInner，参数是 n, row, currentResults
for(let i=0;i<n;i++) {
    //这里对应的是i是Q的每一种情况
    //比如n是4，当前层是row，可以选项是Q...,.Q..,..Q.,...Q四种
    const currentRowResult = ''
    for (let j = 0; j < n; j++) {
        if (j === i) {
            currentRowResult += 'Q'
        } else {
            currentRowResult += '.'
        }
    }
    //判断加进去之后是否仍是合法的N皇后
    if(isValidResult(currentResults, currentRowResult)) {
        //row+1 递归到下一层
        solveNQueensInner(n, row + 1, [...currentResults, currentRowResult])
    }
}
//下面是判断是否合法的函数
var isValidResult = function (currentResult, newRow) {
    const currentRow = currentResult.length
    for (let i = 0; i < newRow.length; i++) {
        if (newRow[i] === 'Q') {
            //横向不用判断，因为每次加的时候就保证了不重复
            //竖向
            for (let j = 0; j < currentResult.length; j++) {
                if (currentResult[j][i] === 'Q') {
                    return false
                }
            }
            //斜向45度角和135度，行列都减一，向左上角移动，行减一，列加一，向右上角移动
            for (let j = 0; j < currentResult.length; j++) {
                //行数每次减一
                const newI = currentRow - j - 1;
                //列数减一
                const newJ = i - j - 1;
                //列数加1
                const newJ2 = i + j + 1
                if (currentResult[newI][newJ] === 'Q' || currentResult[newI][newJ2] === 'Q') {
                    return false
                }
            }
        }
    }
    return true
}

所以整体上的解答如下：

var solveNQueens = function (n) {
    var results = []
    var solveNQueensInner = function (n, row, currentResults) {
        if (currentResults.length === n) {
            results.push(currentResults)
            return
        }
        for (let i = 0; i < n; i++) {
            let currentResult = ""
            for (let j = 0; j < n; j++) {
                if (j === i) {
                    currentResult += 'Q'
                } else {
                    currentResult += '.'
                }
            }
            if (isValidResult(currentResults, currentResult)) {

                solveNQueensInner(n, row + 1, [...currentResults, currentResult])
            }
        }
    }

    var isValidResult = function (currentResult, newRow) {
        const currentRow = currentResult.length
        for (let i = 0; i < newRow.length; i++) {
            if (newRow[i] === 'Q') {
                //横向竖向，斜向
                for (let j = 0; j < currentResult.length; j++) {
                    if (currentResult[j][i] === 'Q') {
                        return false
                    }
                }
                for (let j = 0; j < currentResult.length; j++) {
                    const newI = currentRow - j - 1;
                    const newJ = i - j - 1;
                    const newJ2 = i + j + 1
                    if (currentResult[newI][newJ] === 'Q' || currentResult[newI][newJ2] === 'Q') {
                        return false
                    }
                }
            }
        }
        return true
    }
    solveNQueensInner(n, 0, [])
    return results
};