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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

class Solution {
public:
    int count;
    int *x;
    int *y;
    int index;
    bool *rows, *cols, *ltrb, *rtlb;
    vector<vector<string>> ans;
    vector<string> item;
    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) {
                        x[index] = row;
                        y[index++] = col;
                        item.clear();
                        string subitem = "";
                        for(int j = 0; j < n; j++) {
                            subitem.push_back('.');
                        }
                        for(int i = 0; i < n; i++) {
                            item.push_back(subitem);
                        }
                        for(int i = 0; i < index; i++) {
                                item[x[i]][y[i]] = 'Q';
                        }
                        ans.push_back(item);
                        index--;
                    }
                    else {
                        rows[row] = true;
                        cols[col] = true;
                        ltrb[row+col] = true;
                        rtlb[n-1+row-col] = true;
                        x[index] = row;
                        y[index++] = col;
                        Move(row+1, n);
                        index--;
                        rows[row] = false;
                        cols[col] = false;
                        ltrb[row+col] = false;
                        rtlb[n-1+row-col] = false;
                    }
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        x = new int[n];
        y = new 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);
        ans.clear();
        if(n == 1) {
            string subitem = "Q";
            vector<string> item;
            item.clear();
            item.push_back(subitem);
            ans.push_back(item);
            return ans;
        }
        int row = 0;
        index = 0;
        for(int col = 0; col < n; col++) {
            rows[row] = true;
            cols[col] = true;
            ltrb[row+col] = true;
            rtlb[n-1+row-col] = true;
            x[index] = row;
            y[index++] = col;
            Move(row+1, n);
            index--;
            rows[row] = false;
            cols[col] = false;
            ltrb[row+col] = false;
            rtlb[n-1+row-col] = false;
        }
        return ans;
    }
};