原题地址（困难）

方法1—回溯

思路

基本和51题是一个题，建议先做那一道题。

51. N 皇后

代码

  1. class Solution {
  2. public:
  3.     vector<int> a, b, column;
  4.     int ans;
  5.     int totalNQueens(int n) {
  6.         // 主对角线方向，副对角线方向，列方向
  7.         a.resize(2*n+1, 0);
  8.         b.resize(2*n+1, 0);
  9.         column.resize(n, 0);
  10.         ans = 0;
  11.         dfs(0, n);
  12.         return ans;
  13.     }
  15.     void dfs(int row, int n) {
  16.         if(row == n){
  17.             ans++;
  18.             return;
  19.         }
  20.         // 对第row行的每一列
  21.         for(int j=0; j<n; j++){
  22.             //如果(row, j)这个位置满足行列左斜右斜都没有重复皇后
  23.             if(!a[row+n-1-j] && !b[row+j] && !column[j]){
  24.                 a[row+n-1-j] = b[row+j] = column[j] = 1;
  25.                 dfs(row+1, n);
  26.                 a[row+n-1-j] = b[row+j] = column[j] = 0;
  27.             }
  28.         }
  29.         return;
  30.     }
  31. };

时空复杂度

时间复杂度 O(N!)
空间复杂度 O(2N+1)