力扣日记3.6-【回溯算法篇】51. N 皇后_算法

力扣日记：【回溯算法篇】51. n 皇后

51. n 皇后

题目描述

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

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

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

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

示例 1：
在这里插入图片描述

示例 2：

提示：

1 <= n <= 9

题解

cpp ver

class solution {
public:
    vector<vector<string>> result;
    vector<vector<string>> solvenqueens(int n) {
        // 初始化 棋盘
        // 注意对于一个二维矩阵，board[row][col] 即索引是先row再col
        vector<string> chessboard(n, string(n, '.'));   
        backtracking(chessboard, n, 0);
        return result;
    }
    bool isvalid(vector<string> chessboard, int n, int x, int y) {  // y -> row, x -> col，索引先y再x
        // 同一行是否有q（由于是递归进入下一行，所以不可能在同一行有q，不需判断）
        // 同一列是否有q（由于是从上往下遍历，所以下方未遍历过的行不可能有q，只需判断当前位置以上的部分）
        for (int i = 0; i < y; i++) {
            if (chessboard[i][x] == 'q') return false;
        }
        // \ 是否有q（同理，只需判断左上，注意m,k从当前位置的左上一个位置开始）
        for (int m = x - 1, k = y - 1; m >= 0 && k >= 0; m--, k--) { // m 为 横坐标，k 为纵坐标 查询：[0,x-1) [0,y-1)
            if (chessboard[k][m] == 'q') return false;
        }
        // / 是否有q（同理，只需判断右上，注意m,k从当前位置的右上一个位置开始）
        for (int m = x + 1, k = y - 1; m < n && k >= 0; m++, k--) { // [x+1, n) [0,y-1)
            if (chessboard[k][m] == 'q') return false;
        }
        return true;
    }
    // 关键：将n皇后问题转换为树形结构：横向搜索为for循环，纵向遍历（进入下一行）为递归
    // 参数：棋盘矩阵，皇后数，当前遍历到的行数
    void backtracking(vector<string>& chessboard, int n, int row) {
        // 终止条件：row从0开始，当为n时，说明已经遍历完所有行
        if (row == n) {
            result.push_back(chessboard);
            return;
        }
        // for 循环
        for (int i = 0; i < n; i++) {   // 每一行都从0开始遍历
            if (isvalid(chessboard, n, i, row)) {
                // 如果当前位置为有效位置
                // 设置此位置为皇后位置
                chessboard[row][i] = 'q';
                // 递归（进入下一行）
                backtracking(chessboard, n, row + 1);   // row 作为参数，自动回溯
                // 回溯
                chessboard[row][i] = '.';
            }
        }
    }   
};

复杂度

时间复杂度: o(n!)
空间复杂度: o(n)

思路总结

第一次接触到n皇后，即使知道用回溯法，还是不知道如何下手。再次感谢代码随想录提供思路。
关键思路：
- 将n皇后问题转换为树形结构：依次遍历棋盘的各个位置，横向搜索通过for循环，纵向遍历（进入下一行）通过递归
- 只有当前位置有效，才能放入棋盘（处理节点）并进行递归回溯
难点（易错）：判断当前位置是否有效
- 首先要明确，对于二维数组，row为第一个索引，col为第二个索引
- 判断当前位置是否有效，即当前位置的同一行、同一列、左45°、右45°（同斜线）均不能出现皇后’q’
- 剪枝：由于遍历是从左到右、从上往下（一行接一行）遍历，所以在判断时：
  - 对于同一行是否有q：由于是递归进入下一行，所以不可能在同一行有q，不需判断
  - 对于同一列是否有q：由于是从上往下遍历，所以下方未遍历过的行不可能有q，只需判断当前位置以上的部分
  - 对于 \ 方向是否有q：同理，只需判断左上，注意m（横坐标）,k（纵坐标）从当前位置的左上一个位置开始，即m：x-1 → 0，k：y-1 → 0；
  - 对于 / 方向是否有q：同理，只需判断右上，注意m,k从当前位置的右上一个位置开始，即 m：x+1 → n - 1，k：y -1 → 0。
三部曲：
- 参数：棋盘矩阵，皇后数，当前遍历到的行数
  - 棋盘的初始化：
```
vector<string> chessboard(n, string(n, '.'));
```
- 终止条件：row从0开始，当为n时，说明已经遍历完所有行，则终止
- for 循环
  - 对棋盘的第row行，从棋盘左遍历到右
  - 如果当前位置有效，则进行：
    - 处理节点即放下皇后（chessboard[row][i] = 'q';）
    - 递归（进入下一行）
    - 回溯（chessboard[row][i] = '.';）
树状结构示意图（n = 3）