#include "leetcode.h" class Solution { public: vector> solveNQueens(int n) { vector> ans; vector nQueens(n, string(n, '.')); solve(ans, nQueens, 0, n); return ans; } private: void solve(vector> &ans, vector &nQueens, int row, int &n) { if (row == n) { ans.push_back(nQueens); return; } for (int col = 0; col != n; ++col) if (isValid(nQueens, row, col, n)) { nQueens[row][col] = 'Q'; solve(ans, nQueens, row + 1, n); nQueens[row][col] = '.'; } } bool isValid(vector &nQueens, int row, int col, int &n) { // check if col had queen for (int i = 0; i != row; ++i) if (nQueens[i][col] == 'Q') return false; // check if 45deg diagonal had queen for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) if (nQueens[i][j] == 'Q') return false; // check if 135deg diagonal had queen for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) if (nQueens[i][j] == 'Q') return false; return true; } }; int main() {}