1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
public:
    int count;
    bool *rows,*cols,*ltrb,*rtlb;
    void SetFalse(bool *arrayin,int n) {
        for(int i = 0;i < n;i++)
            arrayin[i] = false;
    }
    void Move(int row,int n) {
        for(int col = 0;col < n;col++) {
            if( rows[row] != true &&
                cols[col] != true &&
                ltrb[row+col] != true&&
                rtlb[n-1+row-col] != true) {
                    if(row == n-1)count++;
                    else {
                        rows[row] = true;
                        cols[col] = true;
                        ltrb[row+col] = true;
                        rtlb[n-1+row-col] = true;
                        Move(row+1,n);
                        rows[row] = false;
                        cols[col] = false;
                        ltrb[row+col] = false;
                        rtlb[n-1+row-col] = false;
                    }
            }
        }
    }
    int totalNQueens(int n) {
        rows = new bool[n];//行
        SetFalse(rows,n);
        cols = new bool[n];//列
        SetFalse(cols,n);
        ltrb = new bool[n+n-1];
        SetFalse(ltrb,n+n-1);
        rtlb = new bool[n+n-1];
        SetFalse(rtlb,n+n-1);
        count = 0;
        if(n == 1)return 1;
        int row = 0;
        for(int col = 0;col < n;col++) {
            rows[row] = true;
            cols[col] = true;
            ltrb[row+col] = true;
            rtlb[n-1+row-col] = true;
            Move(row+1,n);
            rows[row] = false;
            cols[col] = false;
            ltrb[row+col] = false;
            rtlb[n-1+row-col] = false;
        }
        return count;
    }
};