题解 | JAVA #N皇后问题# [P0]

递归+回溯
题目理解为: 是否能在满足规则的情况下在每一行都摆一个Queen

请先彻底忘掉对角线的要求。
如果题目只要求每行/列只能有一个queen。以下解法是不是简单易懂：

public class Solution {
  boolean[] colArr;  // remembers whether a column is already claimed
  
  public int Nqueen(int n) {
    colArr = new boolean[n];
    NqueenRec(n, 0);  // starting from row=0
    return totalWays;
  }

  public void NqueenRec(int n, int row) {
    if (row == n) { totalWays++; return; }

    for (int col = 0; col < n; col++) {  // permute all columns
      if (colArr[col]) // if column is already claimed, skip
        continue; 
      else {
        colArr[col] = true;   // claim column 
        NqueenRec(n, row+1);  // go to next row
        colArr[col] = false;  // unclaim column (a.k.a 回溯)
      }
    }
  }
}

理解了以上的代码, 这道题其实也就90%做完了。处理对角线只不过是多增加了两个condition
只需要多理解以下:
 - 棋盘上一共有从左下到右上(a.k.a bltr)对角线共2n-1条，每条上[row+col]都相同
   i.e. 第0条row+col=0， 第1条row+col=1, ... 第2n-2条row+col=2n-2
   所以 bltrIdx = row+col
 - 棋盘上一共有从左上到右下(a.k.a tlbr)对角线也是共2n-1条，每条上[row-col]都相同
   i.e. 第0条row-col=-(n-1), 第1条row-col=-(n-2), ... 第2n-2条row-col=n-1
   转换一下就是 tlbrIdx = row-col+n-1
 
最后完整代码：
时间 O(n!)
空间 O(n): n<=9 ~O(1)

import java.util.*;

public class Solution {
    boolean[] colArr； // remembers whether a column is claimed
    boolean[] bltrDiagArr; // remembers whether a bltr diagnal is claimed
    boolean[] tlbrDiagArr; // remembers whether a tlbr diagnal is claimed
    int totalWays = 0;
  
    public int Nqueen(int n) {
      colArr = new boolean[n];
      bltrDiagArr = new boolean[2*n-1];
      tlbrDiagArr = new boolean[2*n-1];
      
      NqueenRec(n, 0);  // starting from row=0
      return totalWays;
    }
  
    public void NqueenRec(int n, int row) {
      // base case: can only get here if 1 queen is placed on each row ~ [0, n-1]
      if (row == n) { totalWays++; return; }
      
      for (int col = 0; col < n; col++) {  // permute all columns
        int bltrIdx = row + col;
        int tlbrIdx = row - col + n - 1;
        // if there is another queen on the column or diagnals, skip this column
        if (colArr[col] || bltrDiagArr[bltrIdx] || tlbrDiagArr[tlbrIdx]) continue;
        
        // otherwise, place the queen at row/col, i.e. claim column/diagnals
        colArr[col] = true; 
        bltrDiagArr[bltrIdx] = true;
        tlbrDiagArr[tlbrIdx] = true;
        
        NqueenRec(n, row+1);  // go to next row
        
        // unclaim column/diagnals
        colArr[col] = false; 
        bltrDiagArr[bltrIdx] = false;
        tlbrDiagArr[tlbrIdx] = false;
      }
    }
}