# C++ & Recursive Backtracking with simple valid check on row, col, diagonal and anti-diagonal.

• This post is simple, straightforward way to understand the problem. Not the most efficient way. I initialize all the strings in the beginning to make it clear. If you build one row at a time, some of the checks in the isvalid function could be avoided. There are better solution posted if you want to optimize.

https://discuss.leetcode.com/topic/13617/accepted-4ms-c-solution-use-backtracking-and-bitmask-easy-understand This one has clear explanation and optimization.

class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result; // each string will be n
string s(n, '.');
vector<string> board(n, s);
helper(result, board, 0, n);

return result;
}

void helper(vector<vector<string>>& result, vector<string> board, int row, int n)
{
if(row==n)
{
result.push_back(board);
return;
}

for(int c=0; c<n; c++)
{

if(isValid(board, row, c, n))
{
board[row][c]='Q';
helper(result, board, row+1, n);
board[row][c]='.';
}
}
}

bool isValid(vector<string>& board,int row,int col, int n)
{
for(int i=0; i<n; i++) // check all columns
{
if(i!=col && board[row][i]=='Q') return false;
}

for(int i=0; i<n; i++) // check all rows
{
if(i!=row && board[i][col]=='Q') return false;
}

for(int i=row+1, j=col+1; i<n && j<n; i++, j++) //diagonal down
{
if(board[i][j]=='Q') return false;
}

for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--)// diagonal up
{
if(board[i][j]=='Q') return false;
}

for(int i=row+1, j=col-1; i<n && j>=0; i++, j--) // anti diagonal down
{
if(board[i][j]=='Q') return false;
}

for(int i=row-1, j=col+1; i>=0 && j<n; i--, j++)// anti diagonal up
{
if(board[i][j]=='Q') return false;
}

return true;
}

};

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