题解 | #N皇后问题#

mark

class Solution {
public:
    bool whether_place(int cur, std::vector<int> &column_q) {
      for (int i = 1; i < cur; i++) {
        if (column_q[i] == column_q[cur] || (std::abs(cur-i) == std::abs(column_q[cur]-column_q[i])))
          // 确保不同列，不同斜线
          return false;
      }
      return true;
    }
  
    void dfs(int row, int size, int &sum, std::vector<int> &column_q) {
      if (row > size) {
        // 每一行都放置皇后，终止递归
        sum++;
        return ;
      } 
      
      for (int i = 1; i <= size; i++) {
        // 按行深入
        // 按列发散
        column_q[row] = i;   // 索引代表行号，值代表列号
        if (whether_place(row, column_q)) {
          dfs(row+1, size, sum, column_q);
        }
      }
      // 不满足递归入口则自动跳到下一列
    }
  
    int Nqueen(int n) {
      int sum = 0;
      std::vector<int> column_q(10);
      dfs(1, n, sum, column_q);
      return sum;
    }
};