<p>The <strong>n-queens</strong> puzzle is the problem of placing <code>n</code> queens on an <code>n x n</code> chessboard such that no two queens attack each other.</p>

<p>Given an integer <code>n</code>, return <em>the number of distinct solutions to the&nbsp;<strong>n-queens puzzle</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/queens.jpg" style="width: 600px; height: 268px;" />
<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are two distinct solutions to the 4-queens puzzle as shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 9</code></li>
</ul>

class Solution {
public:

    void addSolution(vector<vector<char>>& board, vector<vector<string>>& ans, int n){
        vector<string> temp_ans;
        for(int i=0; i<n; i++){
            string temp="";
            for(int j=0; j<n; j++){
                temp+=board[i][j];
            }
            temp_ans.push_back(temp);
        }

        ans.push_back(temp_ans);
    }

    bool isSafe(int row, int col, vector<vector<char>>& board, int n){
        int x=row;
        int y=col;

        while(y>=0){
            if(board[x][y]=='Q') return false;
            y--;
        }

        x=row;
        y=col;

        while(x>=0 && y>=0){
            if(board[x][y]=='Q') return false;
            x--;
            y--;
        }

        x=row;
        y=col;
        
        while(x<n && y>=0){
            if(board[x][y]=='Q') return false;
            x++;
            y--;
        }

        return true;
    }

    void solve(int col, vector<vector<string>>& ans, vector<vector<char>>& board, int n){
        //base case
        if(col==n){
            addSolution(board, ans, n);
            return;
        }

        for(int row=0; row<n; row++){
            if(isSafe(row, col, board, n)){
                board[row][col]='Q';
                solve(col+1, ans, board, n);
                board[row][col]='.';
            }
        }

    }

    int totalNQueens(int n) {
        vector<vector<char>> board(n, vector<char>(n, '.'));
        vector<vector<string>> ans;

        solve(0, ans, board, n);

        return ans.size();
    }
};
9932