#include <stdio.h>
#include <vector>
#include <string>
#include <iostream>
#include <math.h>
using namespace std;
class Solution {
public:
vector<vector<string> > ans;
bool safe(vector<string>& board, int i, int j){
if (board[i][j]=='Q')return false;
int n = board.size();
for(int a=0; a<i; ++a)
if ( board[a][j]=='Q')return false;
for(int k1=i-1, k2=j-1; k1>=0 and k2>=0; k1--, k2--)
if (board[k1][k2]=='Q')return false;
for(int k1=i-1, k2=j+1; k1>=0 and k2<n; k1--, k2++)
if (board[k1][k2]=='Q')return false;
return true;
}
bool solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
int breakBound = 0;
if ( (2*n)%3==0)breakBound = (2*n/3 + 1);
else breakBound = ceil(2.0*n/3.0);
return solve(board, breakBound,-1);
}
bool solve(vector<string>& board, int queens_left, int last_i){
if (queens_left==0){
cout << "FALSE CONJECTURE";
ans.push_back(board);
return true;
}
int n = board.size();
for(int j=(last_i+1)%2; j<n; j+=2){
if (safe(board, last_i+1, j)){
board[last_i+1][j] = 'Q';
bool s = solve(board, queens_left-1, last_i+1);
if (s)return true;
board[last_i+1][j] = '.';
}
}
return false;
}
};
int main(int argc, char** argv) {
Solution S;
cout << S.solveNQueens(25) << endl;
for(auto& board : S.ans){
for(int i=0; i<board.size(); ++i){
for(int j=0; j<board[i].size(); ++j){
cout << board[i][j] << " ";
}
cout << endl;
}
}
cout << endl << endl;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hdGguaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIFNvbHV0aW9uIHsKcHVibGljOgogICAgdmVjdG9yPHZlY3RvcjxzdHJpbmc+ID4gYW5zOwogICAgYm9vbCBzYWZlKHZlY3RvcjxzdHJpbmc+JiBib2FyZCwgaW50IGksIGludCBqKXsKICAgICAgICBpZiAoYm9hcmRbaV1bal09PSdRJylyZXR1cm4gZmFsc2U7CiAgICAgICAgaW50IG4gPSBib2FyZC5zaXplKCk7CiAgICAgICAgZm9yKGludCBhPTA7IGE8aTsgICsrYSkKICAgICAgICAgICAgaWYgKCBib2FyZFthXVtqXT09J1EnKXJldHVybiBmYWxzZTsgCiAgICAgICAgCiAgICAgICAgZm9yKGludCBrMT1pLTEsIGsyPWotMTsgazE+PTAgYW5kIGsyPj0wOyBrMS0tLCBrMi0tKQogICAgICAgICAgICBpZiAoYm9hcmRbazFdW2syXT09J1EnKXJldHVybiBmYWxzZTsKICAgICAgICAKICAgICAgICBmb3IoaW50IGsxPWktMSwgazI9aisxOyBrMT49MCBhbmQgazI8bjsgazEtLSwgazIrKykKICAgICAgICAgICAgaWYgKGJvYXJkW2sxXVtrMl09PSdRJylyZXR1cm4gZmFsc2U7CiAgICAgICAgCiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CiAgICBib29sIHNvbHZlTlF1ZWVucyhpbnQgbikgewogICAgICAgIHZlY3RvcjxzdHJpbmc+IGJvYXJkKG4sIHN0cmluZyhuLCAnLicpKTsKCiAgICAgICAgaW50IGJyZWFrQm91bmQgPSAwOwogICAgICAgIGlmICggKDIqbiklMz09MClicmVha0JvdW5kID0gKDIqbi8zICsgMSk7CiAgICAgICAgZWxzZSBicmVha0JvdW5kID0gY2VpbCgyLjAqbi8zLjApOwogICAgICAgIAogICAgICAgIHJldHVybiBzb2x2ZShib2FyZCwgYnJlYWtCb3VuZCwtMSk7ICAgICAgIAogICAgfQogICAgYm9vbCBzb2x2ZSh2ZWN0b3I8c3RyaW5nPiYgYm9hcmQsICBpbnQgcXVlZW5zX2xlZnQsIGludCBsYXN0X2kpewogICAgICAgIGlmIChxdWVlbnNfbGVmdD09MCl7CiAgICAgICAgICAgIGNvdXQgPDwgIkZBTFNFIENPTkpFQ1RVUkUiOwogICAgICAgICAgICBhbnMucHVzaF9iYWNrKGJvYXJkKTsKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQogICAgICAgIGludCBuID0gYm9hcmQuc2l6ZSgpOwogICAgICAgIGZvcihpbnQgaj0obGFzdF9pKzEpJTI7IGo8bjsgais9Mil7CiAgICAgICAgICAgIGlmIChzYWZlKGJvYXJkLCBsYXN0X2krMSwgaikpewogICAgICAgICAgICAgICAgYm9hcmRbbGFzdF9pKzFdW2pdID0gJ1EnOwogICAgICAgICAgICAgICAgYm9vbCBzID0gc29sdmUoYm9hcmQsIHF1ZWVuc19sZWZ0LTEsIGxhc3RfaSsxKTsKICAgICAgICAgICAgICAgIGlmIChzKXJldHVybiB0cnVlOwogICAgICAgICAgICAgICAgYm9hcmRbbGFzdF9pKzFdW2pdID0gJy4nOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KfTsKCmludCBtYWluKGludCBhcmdjLCBjaGFyKiogYXJndikgewogICAgU29sdXRpb24gUzsKICAgIGNvdXQgPDwgUy5zb2x2ZU5RdWVlbnMoMjUpIDw8IGVuZGw7CiAgICBmb3IoYXV0byYgYm9hcmQgOiBTLmFucyl7CiAgICAgICAgZm9yKGludCBpPTA7IGk8Ym9hcmQuc2l6ZSgpOyArK2kpewogICAgICAgICAgICBmb3IoaW50IGo9MDsgajxib2FyZFtpXS5zaXplKCk7ICsrail7CiAgICAgICAgICAgICAgICBjb3V0IDw8IGJvYXJkW2ldW2pdIDw8ICIgIjsKICAgICAgICAgICAgfQogICAgICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICAgICAgfQogICAgfQogICAgY291dCA8PCBlbmRsIDw8IGVuZGw7Cn0K