52. N-Queens II ---H !!!!!!!!!!!!!!!!!!!!!!!!!!

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

 

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 9

A:
仅仅地把问题一，改改，拿过来，（用DFS ）来做，会慢。(但是能过）

class Solution {

public:

int totalNQueens(int n) {

int res = 0;

vector<vector<int>> board(n, vector<int>(n, 0));

helper(board, 0, res);

return res;

}

private:

// set a value on row_th row(all n column), and then contiue to next row

void helper(vector<vector<int>>& board, int row, int& res) {

int n = board.size();

if (row >= n) {

res++;

return;

}

for (int j = 0; j < n; j++) {

board[row][j] = 1;

if (isValid(board, row, j))

helper(board, row + 1, res);

board[row][j] = 0;

}

}

bool isValid(vector<vector<int>>& board, int row, int col) {

int n = board.size();

// position board[row][col] is just set to 1, need check if it is valid

// check going up to see if there's 1

for (int i = 0; i < row; i++)

if (board[i][col])

return false;

// check the whole row are NOT needed

// check diagonal (slash)

for (int i = 0; i < n; i++) {

int j = i + col - row;

if (j >= 0 && j < n) {

if (i != row && board[i][j])

return false;

}

}

// check anti-diagonal (anti-slash)

for (int i = 0; i < n; i++) {

int j = col + row - i;

if (j >= 0 && j < n) {

if (i != row && board[i][j])

return false;

}

}

return true;

}

};

下面的代码，不是自己写的，是网上copy别人的。
第一次， 让爷们儿，放弃了自己的方式。
好好学着下面的代码！！！！！！！！！！！！(time beat 100%;  memory beat 96%)

class Solution {
public:
    int totalNQueens(int n) {
        vector<int> pattern(n); //pattern[i] store the column index of the queen in row i
        return countSolution(1, pattern);
    }
private:
    int countSolution(int k, vector<int>& pattern) { //k: the current row number 
        int n = pattern.size();
        int res = 0;
        for (int i = 0; i < n; i++) {
            bool valid = true;
            for (int j = 0; j < k - 1; j++) {
                if (pattern[j] == i || abs(j - k + 1) == abs(pattern[j] - i)) {
                    valid = false;
                    break;
                }
            }
            if (!valid)
                continue;
            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)