#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<string> > results;
    vector<int> result;
    int N;
    void initData() {
        results.clear();
        result.assign(N, 0);
    }
    
    int findBit(int n) {
        unsigned int b4 = 0xFFFF0000;
        unsigned int b3 = 0xFF00FF00;
        unsigned int b2 = 0xF0F0F0F0;
        unsigned int b1 = 0xCCCCCCCC;
        unsigned int b0 = 0xAAAAAAAA;
        
        int pos = ((b4&n) > 0? 1<<4:0)
        | ((b3&n) > 0? 1<<3:0)
        | ((b2&n) > 0? 1<<2:0)
        | ((b1&n) > 0? 1<<1:0)
        | ((b0&n) > 0? 1<<0:0);
        
        return pos;
    }
    
    void addResult(vector<int> &result) {
        vector<string> board = vector<string>(N, string(N, '.'));
        for (int i = 0; i < N; ++i) {
            int bit = findBit(result[i]);
            board[i][bit] = 'Q';
        }
        results.push_back(board);
    }
    
    bool validate(vector<int> &result, int index, int pos) {
        int v = result[index];
        for (int i = index-1; i >= 0; --i) {
            if (v & result[i]) {
                return false;
            }
        }
        
        int l = result[index];
        for (int i = index-1, j = pos-1; i >= 0 && j >= 0; --i, --j) {
            l >>= 1;
            if (l & result[i]) {
                return false;
            }
        }
        
        int r = result[index];
        for (int i = index-1, j = pos+1; i >= 0 && j < N; --i, ++j) {
            r <<= 1;
            if (r & result[i]) {
                return false;
            }
        }
        
        return true;
    }
    
    void solve(vector<int> &result, int l) {
        if (l == N) {
            addResult(result);
            return;
        }
        
        int &num = result[l];
        for (int i = 0; i < N; ++i) {
            num = 1<<i;
            if(validate(result, l, i)) {
                solve(result, l+1);
            }
        }
        
        result[l] = 0;
        
    }
    
public:
    vector<vector<string> > solveNQueens(int n) {
        N = n;
        initData();
        solve(result, 0);
        return results;
    }
};

ostream& operator<<(ostream& out, vector<vector<string> > vv) {
    for (int i = 0; i < vv.size(); ++i) {
        vector<string> &v = vv[i];
        for (int j = 0; j < v.size(); ++j) {
            out << v[j] << endl;
        }
        
        out << string(10, '-') << endl;
    }
    
    return out;
}


int main(int argc, char const *argv[]) {
    Solution s;
    vector<vector<string> > result = s.solveNQueens(2);
    
    cout << result << endl;
    cout << result.size() << endl << endl << endl;
    
    result = s.solveNQueens(4);
    cout << result << endl;
    cout << result.size() << endl << endl << endl;
    
    result = s.solveNQueens(8);
    cout << result << endl;
    cout << result.size() << endl << endl << endl;
    return 0;
}