N-Queens II !!!!!!!!!!!!!!!!!!!!!!!!!!

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

A:
仅仅地把问题一，改改，拿过来，（用DFS ）来做，会太慢。
下面的代码，不是自己写的，是网上copy别人的。
第一次， 让爷们儿，放弃了自己的方式。
好好学着下面的代码！！！！！！！！！！！！！！！！！！

public class Solution {
    public int totalNQueens(int n) {
        assert(n>0);
        return countSolution(1,new int[n]);
    }
    
    public int countSolution(int k, int[] pattern){
        int n= pattern.length;
        assert(k<=n);
        int res = 0;
        main:
        for(int i=0;i<n;i++){
            for(int j=0;j<k-1;j++){
                if(pattern[j]==i||Math.abs(j-k+1)==Math.abs(pattern[j]-i))
                continue main;
            }
            pattern[k-1]=i;
            if(k==n) return 1;
            else res+=countSolution(k+1,pattern);
        }
        return res;
    }
}

上面这个例子， 包括下面的例子，都默认要求  n < 32

-------------------------方法2------------

public class Solution {

static int result = 0;
static int upperLimit = 0;

public int totalNQueens(int n) {
    upperLimit = (1 << n)-1;
    result = 0;
    int row = 0;
    int ld = 0;
    int rd = 0;
    dfs(row,ld,rd);
    return result;
}
private static void dfs(int row, int ld, int rd) {
    if(row >= upperLimit){
        result++;
        return;
    }
    int pos = upperLimit &(~(row|ld|rd));
    int p = 0;
    while(pos > 0){
        p = pos & (~pos+1);
        pos = pos-p;
        dfs(row+p,(ld+p)<<1,(rd+p)>>1);
    }
}
}

Mistakes:
背诵上面的代码吧。    人家还用了个main:

Learned:
首先是label的运用。可以直接跳出2层循环。 
        当然，不建议这样用，可以设置个标识，如果内层跳出了， 再跳第二层。

----------------------------3 rd Pass --------------------------
由于2D array 的值只有2个， 因此，我们可以用1D array 来表示它。
比如： int[ ] {3,1,4,2} 代表放置的地点分别为[1,3], [2,1], [3,4], [2,4]  （ 第一个是index)
这么一来，我们用很简单的用数组表示了整个Board，而且在isValid函数里判断的时候会非常简洁，而且把输出Board单独隔离了出来

注意，我们刚开始的时候，在isValid中，依然去判断行，列， 对角线。 其实是不必要的。  只需要判断当前行之前的行，列即可。
因此，刚开始的时候，我们写成：

    private boolean isValid(int cur) {
        // no need to check col, check row
        for (int i = 0; i < cur; i++)
            if ( loc[i] == loc[cur])
                return false;
        // check diagonal \
        for (int i = 0; i < cur; i++) {
            int j = i + loc[cur] - cur; // new colum that is on diagonal
            if ( j >= 0 && j < N && loc[j] != loc[cur])
                return false;
        }
        // check diagonal /
        for (int i = 0; i < cur; i++) {
            int j = loc[cur] + cur - i;// new colum that is on diagonal /
            if ( j >= 0 && j < N && loc[j] != loc[cur])
                return false;
        }
        return true;
    }

这样其实是不必要的，  只需要判断 x上的距离差和y轴上的距离差，绝对值相等即可。

public class Solution {
    int total = 0;

    public int totalNQueens(int n) {
        int[] loc = new int[n];
        dfs(loc,0);
        return total;
    }

    private void dfs(int[] loc,int row) {
        if (row >= loc.length) {
            total++;
            return;
        }
        for (int i = 0; i < loc.length; i++) {
            loc[row] = i+1;// loc[i]==j, means that on board[i][j] =='Q'
            if (isValid( loc,row))
                dfs(loc,row + 1);
        }
    }

    private boolean isValid(int[] loc,int cur) {
        for (int i = 0; i < cur; i++) 
            if (loc[i] == loc[cur] || Math.abs(loc[i] - loc[cur]) == (cur - i))
                return false;
        return true;
    }
}

Learned:
1：
   用1D 来代替2D array--------   其实，退化来讲， 如果是一维的棋盘，上面只能有一个位置放Q的话。
我们也可以直接 用一个 变量 来记录其位置即可。
2：
  对2D 的数组来讲， 要判断是其diagonal的值相等。只需要判断其 x 轴的差距， 是否和 y轴的差距相等即可。    （由于是2条对角线， 因此，要去 Abs)