# C++ backtrack solution

• ``````class Solution {
public:
void backtrack(int depth, vector<long long int>& path,
vector<bool>& visity, vector<bool>& visit1, vector<bool>& visit2,
vector<vector<string>>& ans, int n){
if(depth == n){
vector<string> tmp(n, string(n, '.'));
for(long long int p : path){
int x = p / n;
int y = p % n;
tmp[x][y] = 'Q';
}
ans.push_back(tmp);
return;
}
for(int j = 0; j < n; ++j){
if(visity[j] || visit1[depth + j] || (visit2[depth - j + n - 1])){
continue;
}
visity[j] = true;
visit1[depth + j] = true;
visit2[depth - j + n - 1] = true;
path.push_back(depth * n + j);
backtrack(depth + 1, path, visity, visit1, visit2, ans, n);
path.pop_back();
visity[j] = false;
visit1[depth + j] = false;
visit2[depth - j + n - 1] = false;
}
}
vector<vector<string>> solveNQueens(int n) {
vector<bool> visity(n, false);
vector<bool> visit1(2 * n, false);
vector<bool> visit2(2 * n, false);
vector<vector<string>> ans;
vector<long long int> path;
backtrack(0, path, visity, visit1, visit2, ans, n);
return ans;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.