N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.













Naive Way:在N-queens 中，要求是返回所有解法，那么就知道解法的个数了，但是作为一道新题，是否说明可以用低于返回所有解法的复杂度求得解的个数。

最后还是用了DFS原来的方法，做了一些简化。

 public class Solution {  
   class Node{  
     int x,y;  
     Node(int xx, int yy){  
       x = xx;  
       y = yy;  
     }  
   }  
   public int totalNQueens(int n) {  
     // DFS  
     int board[][] = new int[n][n];  
     int count = 0;  
     Stack<Node> stack = new Stack<Node>();  
     for(int j = 0;j < n;j++)  
       stack.push(new Node(0,j));  
     while(!stack.isEmpty()){  
       Node node = stack.pop();  
       boolean hasNext = false;  
       setBoard(board,node,false);  
       for(int j = 0;j < n;j++)  
         if(node.x+1 < n && board[node.x+1][j] == 0) stack.push(new Node(node.x+1,j));  
       for(int j = 0;j < n;j++)  
         if(node.x+1 < n &&board[node.x+1][j] == 0) hasNext = true;  
       count += node.x==n-1?1:0;  
       if(!hasNext){  
         // back trace  
         if(stack.isEmpty()) break;  
         Node peek = stack.peek();  
         for(int i = node.x;i >= peek.x;i--)  
           for(int j = n-1;j >= 0;j--)  
             if(((i==node.x && j <= node.y) || (i==peek.x && j > peek.y) || (i< node.x && i > peek.x)) && board[i][j]==-1)  
               setBoard(board, new Node(i,j), true);  
       }  
     }  
     return count;  
   }  
   private void setBoard(int[][] b, Node node, boolean clear){  
     int add = clear?-1:1;  
     for(int i = 0;i < b.length;i++)  
       b[i][node.y] +=b[i][node.y]==-1?0:add;  
     for(int j = 0;j < b[0].length;j++)  
       b[node.x][j] +=b[node.x][j]==-1?0:add;  
     for(int i = 0;i < b.length;i++){  
       if(node.x+i < b.length && node.y+i < b[0].length)  
         b[node.x+i][node.y+i] += b[node.x+i][node.y+i]==-1?0:add;  
       if(node.x+i < b.length && node.y-i >= 0)  
         b[node.x+i][node.y-i] += b[node.x+i][node.y-i]==-1?0:add;  
       if(node.x-i >= 0 && node.y+i < b[0].length)  
         b[node.x-i][node.y+i] += b[node.x-i][node.y+i]==-1?0:add;  
       if(node.x-i >= 0 && node.y-i >= 0)  
         b[node.x-i][node.y-i] += b[node.x-i][node.y-i]==-1?0:add;  
     }  
     b[node.x][node.y] = clear?0:-1;  
   }  
 }  

Improved Way:在Discuss看到很多人都不需要用二维矩阵。方法都特别厉害。

https://oj.leetcode.com/discuss/18411/accepted-java-solution
AlexTheGreat 的做法是将所有格子分为col, row, diag1, diag2。col和row 是指列和行。
diag1是指从左上至右下的对角线， diag2是指从左下至右上的对角线。这样就将一个矩阵拆成4个1D向量。

最厉害的还是代码的回溯方式，遍历一个row之后可立即消去之前遍历的痕迹。

 /**  
  * don't need to actually place the queen,  
  * instead, for each row, try to place without violation on  
  * col/ diagonal1/ diagnol2.  
  * trick: to detect whether 2 positions sit on the same diagnol:  
  * if delta(col, row) equals, same diagnol1;  
  * if sum(col, row) equals, same diagnal2.  
  */  
 private final Set<Integer> occupiedCols = new HashSet<Integer>();  
 private final Set<Integer> occupiedDiag1s = new HashSet<Integer>();  
 private final Set<Integer> occupiedDiag2s = new HashSet<Integer>();  
 public int totalNQueens(int n) {  
   return totalNQueensHelper(0, 0, n);  
 }  
 private int totalNQueensHelper(int row, int count, int n) {  
   for (int col = 0; col < n; col++) {  
     if (occupiedCols.contains(col))  
       continue;  
     int diag1 = row - col;  
     if (occupiedDiag1s.contains(diag1))  
       continue;  
     int diag2 = row + col;  
     if (occupiedDiag2s.contains(diag2))  
       continue;  
     // we can now place a queen here  
     if (row == n-1)  
       count++;  
     else {  
       occupiedCols.add(col);  
       occupiedDiag1s.add(diag1);  
       occupiedDiag2s.add(diag2);  
       count = totalNQueensHelper(row+1, count, n);  
       // recover  
       occupiedCols.remove(col);  
       occupiedDiag1s.remove(diag1);  
       occupiedDiag2s.remove(diag2);  
     }  
   }  
   return count;  
 }  

然后还有一些用bit manipulate的做法，我就看懂了一个，觉得这种做法最厉害之处在于不用back trace。来自leetcode用户weird 。

首先还是定下，col, row, diag1, diag2的4个1D向量, 而row向量会作为recursive的参数成为循环的increment。关键的代码
(col & (cm|dm1|dm2) )==0 
是来判断 当前已知的占据信息 (cm|dm1|dm2) 中，board[col][row]这一点是否被占据了，如果不被占据，即该bit 为0，就可以升一行，并将该点被占据的信息记入cm 中，然后更新 dm1 和dm2。至于dm1 和 dm2 是如何更新的。首先要认清这个回溯算法是不需要back trace的，每次传进 bts ()中的内容都是之前一行的占据情况，同一行不同列使用的信息都是一样的，就是之前一行的占据情况。所以dm1的更新只需要记录对于下一个点会有影响的对角线上的点是否被占据，写一个点必是下一行的某个点，而那时的col会比现在的高一个bit，所以dm1要左移一个bit。简单的说就是cm, dm1,dm2记录的都是相对位置，不是绝对位置。

 public class Solution {  
   int count=0;  
   public int totalNQueens(int n) {  
     bts(0,n,0,0,0);  
     return count;  
   }  
   //passing column mask, left diagonal mask, right diagonal mask  
   void bts(int row, int n, int cm, int dm1, int dm2){  
     if (row==n){  
       count++;  
       return;  
     }  
     for (int col=(1<<(n-1));col>0;col>>=1)  
       if ((col & (cm|dm1|dm2) )==0 )  
         bts(row+1,n, cm|col, (col|dm1)<<1, (col|dm2)>>1);  
   }  
 }