https://leetcode-cn.com/problems/n-queens/

难度：困难

---

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

  图为 8 皇后问题的一种解法。

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

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

示例：

输入：4

输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解释: 4 皇后问题存在两个不同的解法。

提示：

• 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

解法1：回溯

  对每个位置都进行尝试。

  n 行，每行从头开始遍历，对当前位置，判断这个位置是否满足皇后位置的要求，即横、纵、斜线上都没有其他皇后存在，因为我们是从头开始遍历的，因此，对当前位置只需要判断处于一条竖线的上方、处于左斜线的上方和处于右斜线的上方是否有皇后存在即可。若当前位置满足，则开始寻找下一行的皇后的位置。直到第 n 行找到最后一个皇后。

  如下图，假设遍历到 Q3 位置，它只需要判断三条蓝线的方向是否有皇后即可。

var solveNQueens = function(n) {
    let res = [];
    let board = [];
    
    for (let i = 0; i < n; i++) {
        board[i] = new Array(n).fill('.');
    }

    const deepCopy = () => {
        let arr = [];
        for (let i = 0; i < n; i++) {
            arr[i] = [];
            for (let j = 0; j < n; j++) {
                arr[i][j] = board[i][j];
            }
        }

        return arr;
    };

    const dirs = [[-1, 0], [-1, 1], [-1, -1]];  // 只需要查找 上方的、斜左上方的 和 斜右上方的 方向是否有 Q 即可

    const helper = (row) => {
        if (row === n) {
            res.push(deepCopy());
        }

        for (let i = 0; i < n; i++) {
            let flag = true;
            for (let dir of dirs) {
                let r = row + dir[0], c = i + dir[1];
                while(r >= 0 && r < n && c >= 0 && c < n) {
                    if (board[r][c] === 'Q') {
                        flag = false;
                        break;
                    }
                    r += dir[0], c += dir[1];
                }
                if (!flag) {
                    break;
                }
            }
            
            if (flag) {
                board[row][i] = 'Q';
                helper(row+1);
                board[row][i] = '.';
            }
        }

    };

    helper(0);

    for (let i = 0; i < res.length; i++) {
        for (let j = 0; j < n; j++) {
            res[i][j] = res[i][j].join('');
        }
    }

    return res;
};