to do
bool okToPlace(vector<string>& board, int row, int col) {
// check cols
for (int i=0; i<board.size(); ++i) {
if (board[i][col]=='Q') return false;
}
// check upper diagnol on the left
for (int i=row-1, j=col-1; i>=0 && j>=0; --i, --j) {
if (board[i][j]=='Q') return false;
}
// check upper dignol on the right
for (int i=row-1, j=col+1; i>=0 && j<board.size(); --i, ++j) {
if (board[i][j]=='Q') return false;
}
return true;
}
void rec(vector<vector<string>>& ret, vector<string>& board, int n, int row) {
if (row == n) {
ret.push_back(board);
return;
}
//traverse throught [i][0->n-1]
for (int j=0; j<n; ++j) {
if (okToPlace(board, row, j)) {
board[row][j] = 'Q';
rec(ret, board, n, row+1);
board[row][j] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ret;
vector<string> board (n, string(n, '.')) ;
rec(ret, board, n, 0);
return ret;
}
};
