<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 solve(int i,vector<int> col,vector<vector<int>> map,int n,vector<vector<string>> &ans)
    {
        if(i==n)
        {
          vector<string> v;
          for(int i=0;i<n;i++)
          {
              string s;
              for(int j=0;j<n;j++)
              {
                 if(map[i][j]==0)
                 {
                     s.push_back('.');

                 }
                 else
                 {
                     s.push_back('Q');
                 }
              }
              v.push_back(s);
          }
          ans.push_back(v);
          return;
        }
        
        for(int k=0;k<n;k++)
        {
            if(col[k]==1)
            continue;
            int x=i;
            int y=k;
            int flag=0;
            while(x>=1 && x<n && y>=1 && y<n)
            {
                if(map[x-1][y-1]==1)
                {
                    flag=1;
                    break;

                }
                else
                {
                    x--;
                    y--;
                }
            }
            if(flag==1)
            continue;
           
                x=i;
                y=k;
                 while(x>=1 && x<n && y>=0 && y<n-1)
            {
                if(map[x-1][y+1]==1)
                {
                    flag=1;
                    break;

                }
                else
                {
                    x--;
                    y++;
                }
            }
            if(flag==1)
            continue;
             x=i;
                y=k;
                 while(x>=0 && x<n-1 && y>=1 && y<n)
            {
                if(map[x+1][y-1]==1)
                {
                    flag=1;
                    break;

                }
                else
                {
                    x++;
                    y--;
                }
            }
            if(flag==1)
            continue;
             x=i;
                y=k;
                 while(x>=0 && x<n-1 && y>=0 && y<n-1)
            {
                if(map[x+1][y+1]==1)
                {
                    flag=1;
                    break;

                }
                else
                {
                    x++;
                    y++;
                }
            }
            if(flag==1)
            continue;
            
            col[k]=1;
            map[i][k]=1;
            solve(i+1,col,map,n,ans);
            col[k]=0;
            map[i][k]=0;
            
            
            }
        

    }
    int totalNQueens(int n) {
        vector<vector<string>> ans;
        vector<vector<int>> map(n,vector<int>(n,0));
        vector<int> col(n,0);
        solve(0,col,map,n,ans);
        return ans.size();
    }
};
22807