设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/eight-queens-lcci

  1.  // 输入：
  2. 4
  3. // 输出：
  4. [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
  5. // 解释: 
  6. 4  // 皇后问题存在如下两个不同的解法。
  7. [
  8.  [".Q..",  // 解法 1
  9.   "...Q",
  10.   "Q...",
  11.   "..Q."],
  13.  ["..Q.",  // 解法 2
  14.   "Q...",
  15.   "...Q",
  16.   ".Q.."]
  17. ]

理解题意

把n个皇后放置在n*n的棋盘上，这些皇后彼此不能相互攻击。任何两个皇后都不能在同一行、同一列以及同一条斜线上。

数据结构及算法思维的选择

数据结构：二维数组
算法思维：递归

基本解法及编码的实现

相当于把每一行都会放置一个皇后，然后过滤掉不满足的结果，把正确的结果保存下来了。
暴力解法：

  1. function solveNQueens(n) {
  2.   // 1. 先实例一个二维数组
  3.   // 声明一个输出结果的数组
  4.   const result = [];
  6.   /**
  7.    * @param {result} 结果数组跟着传，存在满足要求的结果就push
  8.    * @param {chess} 皇后的棋盘
  9.    * @param {row} 当前行数
  10.    */
  11.   solve(result, generator2DArray(n), 0);
  13.   return result;
  14. };
  16. function solve(result, chess, row) {
  17.   // 存在结果的边界条件，就是当现在row + 1的值等于chess的长度及满足
  18.   if (row === chess.length) {
  19.     // 需要把二维数组转为一维数组
  20.     result.push(array2dTo1(chess));
  22.     return;
  23.   };
  25.   // 遍历每一列
  26.   for (let col = 0; col < chess.length; col++) {
  28.     // 判断当前列是否满足放入皇后
  29.     if (valid(row, col, chess)) {
  31.       // 这里需要缓存满足情况的结果
  32.       // 这样就算知道下面的结论不满足的时候，继续往上往下遍历，都是独立的棋盘。
  33.       let tmp = copyArray2d(chess);
  34.       tmp[row][col] = 'Q';
  36.       // 进入下一行查找
  37.       solve(result, tmp, row + 1);
  38.     }
  39.   }
  40. }
  42. function array2dTo1(array2D) {
  43.   const res = [];
  45.   for (const key in array2D) {
  46.     res[key] = array2D[key].join('');
  47.   };
  49.   return res;
  50. }
  52. function generator2DArray(n) {
  53.   const array2D = [];
  55.   for (let i = 0; i < n; i++) {
  56.     array2D[i] = [];
  57.     for (let j = 0; j < n; j++) {
  58.       array2D[i][j] = '.'
  59.     }
  60.   };
  62.   return array2D;
  63. }
  65. function copyArray2d(array2D) {
  66.   const newArr = [];
  68.   for (const item of array2D) {
  69.     newArr.push([...item])
  70.   };
  72.   return newArr;
  73. }
  75. function valid(row, col, chess) {
  76.   // 下方的判断条件只考虑已经填入皇后的坐标
  77.   // 判断这一列是否有存在的
  78.   for (let i = 0; i < row; i++) {
  79.     if (chess[i][col] === 'Q') {
  80.       return false;
  81.     }
  82.   };
  83.   // 判断左上角是否有存在的
  84.   for (let i = row - 1, j = col - 1; i >= 0; i--, j--) {
  85.     if (chess[i][j] === 'Q') {
  86.       return false;
  87.     }
  88.   }
  89.   // 判断右上角是否有存在
  90.   for (let i = row - 1, j = col + 1; i >= 0; i--, j++) {
  91.     if (chess[i][j] === 'Q') {
  92.       return false;
  93.     }
  94.   };
  96.   return true;
  97. }

时间复杂度：O(N!)

  1. N是皇后的数量

空间复杂度：O(N ^ 2)

  1. 栈的最大深度为N

  2. 存储空间为N

    思考最优解

  3. 剔除无效代码或优化空间消耗

  4. 寻找更好的算法思维

    最优解思路及编码实现

    最优解：基于集合的回溯

  5. 数组结构：集合

  6. 算法思维：回溯

边界细节问题和复杂度分析

function solveNQueens(n: number): string[][] {
    const result = [], queues = []

    // 左斜线
    const left = new Set<number>();
    // 右斜线
    const right = new Set<number>();
    // 列
    const column = new Set<number>();

    backTrack(result, queues, n, 0, left, right, column);

    return result;
};

function backTrack(
    result: string[][],
    queues: number[],
    n: number,
    row: number,
    left: Set<number>,
    right: Set<number>,
    column: Set<number>
) {
    if (n === row) {
        result.push(generatorBoard(queues, n));
        return;
    }

    for (let col = 0; col < n; col++) {
        let left1 = col - row;
        // 如果左斜线上存在一个 即不满足
        if (left.has(left1)) {
            continue;
        };

        // 如果右斜线上存在一个 即不满足
        let right1 = col + row;
        if (right.has(right1)) {
            continue;
        };

        // 如果列存在 即不满足
        if (column.has(col)) {
            continue;
        };

        // 当前满足 保存行和列信息
        queues[row] = col;
        // 保存满足行列信息的 左、右斜线和列的唯一值
        left.add(left1), right.add(right1), column.add(col);

        // 进入下一行
        backTrack(result, queues, n, row + 1, left, right, column);

        // 上述的满足不满足 删掉
        queues[row] = -1;
        // 清除掉不满足行列信息的 左、右斜线和列的唯一值
        left.delete(left1), right.delete(right1), column.delete(col);
    }
}

function generatorBoard(queues: number[], n): string[] {
    const arr = [];

    for (const index in queues) {
        if (queues[index] === undefined) continue;

        const row = (new Array(n)).fill('.');
        row[queues[index]] = 'Q';
        arr.push(row.join(''));
    }

    return arr;
}

时间复杂度：O(N!)

空间复杂度: O(N)

总结

  1. 回溯算法的特点
    1. 回溯是一种算法思想，可以用递归实现
    2. 回溯就是一种试探，类似于穷举，但回溯有剪枝功能
    3. 从问题的某一种可能出发，搜索从这种情况出发所能达到的所有可能，当一条路走到尽头的时候，再倒回出发点，从另一种可能出发，继续搜索。这就是回溯
  2. 回溯算法的应用
    1. 求和问题，给定七个数字，1234567求7的组合
    2. 从小到大搜索选择1+2+3+4那后面的 567就没必要重新组合了，这就是剪枝