#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isValid(const vector<int>& col_queen) {
int i, row_id, diff;
row_id = col_queen.size() - 1;
for(i = 0; i < row_id; ++i) {
diff = abs(col_queen[row_id] - col_queen[i]);
if(diff == 0 || diff == row_id - i) {
// col conflict or diagonal conflict.
return false;
}
}
return true;
}
void findPlacement(int k, int n, vector<int> &col_queen, vector<vector<int>> &result) {
if(k == n) {
result.push_back(col_queen);
}
else {
for(int i = 0; i < n; ++i) {
col_queen.push_back(i);
if(isValid(col_queen)){
findPlacement(k+1, n, col_queen, result);
}
col_queen.pop_back();
}
}
}
vector<vector<int>> QueenPlacement(int n) {
vector<vector<int>> result;
vector<int> col_queen;
findPlacement(0, n, col_queen, result);
return result;
}
int main() {
vector<vector<int>> res;
res = QueenPlacement(8);
cout << "Placement of queens are as follow : "<<res.size() << endl;
for(int i = 0; i < res.size(); ++i) {
for(int j = 0; j < res[0].size(); ++j) {
cout << res[i][j] << " ";
}
cout << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y21hdGg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpib29sIGlzVmFsaWQoY29uc3QgdmVjdG9yPGludD4mIGNvbF9xdWVlbikgewoJaW50IGksIHJvd19pZCwgZGlmZjsKCXJvd19pZCA9IGNvbF9xdWVlbi5zaXplKCkgLSAxOwoJZm9yKGkgPSAwOyBpIDwgcm93X2lkOyArK2kpIHsKCSAgICBkaWZmID0gYWJzKGNvbF9xdWVlbltyb3dfaWRdIC0gY29sX3F1ZWVuW2ldKTsKCSAgICBpZihkaWZmID09IDAgfHwgZGlmZiA9PSByb3dfaWQgLSBpKSB7CgkgICAgCS8vIGNvbCBjb25mbGljdCBvciBkaWFnb25hbCBjb25mbGljdC4KCSAgICAJcmV0dXJuIGZhbHNlOwoJICAgIH0KCX0KICAgIHJldHVybiB0cnVlOwp9Cgp2b2lkIGZpbmRQbGFjZW1lbnQoaW50IGssIGludCBuLCB2ZWN0b3I8aW50PiAmY29sX3F1ZWVuLCB2ZWN0b3I8dmVjdG9yPGludD4+ICZyZXN1bHQpIHsKCWlmKGsgPT0gbikgewoJCXJlc3VsdC5wdXNoX2JhY2soY29sX3F1ZWVuKTsKCX0KCWVsc2UgewoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKCQkJY29sX3F1ZWVuLnB1c2hfYmFjayhpKTsKCQkJaWYoaXNWYWxpZChjb2xfcXVlZW4pKXsKCQkJCWZpbmRQbGFjZW1lbnQoaysxLCBuLCBjb2xfcXVlZW4sIHJlc3VsdCk7CgkJCX0KCQkJY29sX3F1ZWVuLnBvcF9iYWNrKCk7CgkJfQoJfQp9Cgp2ZWN0b3I8dmVjdG9yPGludD4+IFF1ZWVuUGxhY2VtZW50KGludCBuKSB7Cgl2ZWN0b3I8dmVjdG9yPGludD4+IHJlc3VsdDsKCXZlY3RvcjxpbnQ+IGNvbF9xdWVlbjsKCWZpbmRQbGFjZW1lbnQoMCwgbiwgY29sX3F1ZWVuLCByZXN1bHQpOwoJcmV0dXJuIHJlc3VsdDsKfQoKaW50IG1haW4oKSB7Cgl2ZWN0b3I8dmVjdG9yPGludD4+IHJlczsKCXJlcyA9IFF1ZWVuUGxhY2VtZW50KDgpOwoJY291dCA8PCAiUGxhY2VtZW50IG9mIHF1ZWVucyBhcmUgYXMgZm9sbG93IDogIjw8cmVzLnNpemUoKSA8PCBlbmRsOwoJZm9yKGludCBpID0gMDsgaSA8IHJlcy5zaXplKCk7ICsraSkgewoJCWZvcihpbnQgaiA9IDA7IGogPCByZXNbMF0uc2l6ZSgpOyArK2opIHsKCQkJY291dCA8PCByZXNbaV1bal0gPDwgIiAiOwoJCX0KCQljb3V0IDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==