<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>all distinct solutions to the <strong>n-queens puzzle</strong></em>. You may return the answer in <strong>any order</strong>.</p>

<p>Each solution contains a distinct board configuration of the n-queens&#39; placement, where <code>&#39;Q&#39;</code> and <code>&#39;.&#39;</code> both indicate a queen and an empty space, respectively.</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> [[&quot;.Q..&quot;,&quot;...Q&quot;,&quot;Q...&quot;,&quot;..Q.&quot;],[&quot;..Q.&quot;,&quot;Q...&quot;,&quot;...Q&quot;,&quot;.Q..&quot;]]
<strong>Explanation:</strong> There exist two distinct solutions to the 4-queens puzzle as shown above
</pre>

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

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> [[&quot;Q&quot;]]
</pre>

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

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

class Solution {
    void SOL ( std::vector < std::vector < char > > & Grid , std::set < std::pair < int , int > > Empty , std::set < std::vector < std::string > > & Ans , int & n ,
          std::vector < std::vector < std::set < std::pair < int , int > > > > & Curr_Node_Visited_From , int Op ) {
        if ( Empty.empty() ) {
            std::vector < std::string > Vec ; int Count = 0 ;
            for ( int i = 1 ; i <= n ; i++ ) {
                std::string Str = "" ;
                for ( int j = 1 ; j <= n ; j++ ) {
                    Str.push_back ( Grid[i][j] ) ;
                    if ( Grid[i][j] == 'Q' ) {
                        Count++ ;
                    }
                } Vec.push_back ( Str ) ;
            }
            if ( Count == n ) {
                Ans.insert ( Vec ) ;
            }
            return ;
        }
        std::set < std::pair < int , int > > :: iterator Ite ;
        for ( Ite = Empty.begin() ; Ite != Empty.end() ; Ite++ ) {
            std::set < std::pair < int , int > > New = Empty ; std::set < std::pair < int , int > > :: iterator NI ;
            int Row = Ite->first , Col = Ite->second ;
            if ( Row > Op ) {
                break ;
            }
            Grid[Row][Col] = 'Q' ;
            New.erase ( {Row,Col} ) ;
            // ei {Row,Col} theke 8 ta Direction e j j Point e jawa jay , segulan sob Delete kre dite hobe !!!
            // Right !!!
            for ( int j = Col + 1 ; j <= n ; j++ ) {
                New.erase ( {Row,j} ) ;
            }
            // Left !!!
            for ( int j = Col - 1 ; j >= 1 ; j-- ) {
                New.erase ( {Row,j} ) ;
            }
            // Up !!!
            for ( int i = Row - 1 ; i >= 1 ; i-- ) {
                New.erase ( {i,Col} ) ;
            }
            // Down !!!
            for ( int i = Row + 1 ; i <= n ; i++ ) {
                New.erase ( {i,Col} ) ;
            }
            // Right_Down !!!
            for ( int i = Row + 1 , j = Col + 1 ; i <= n && j <= n ; i++ , j++ ) {
                New.erase ( {i,j} ) ;
            }
            // Right_Up !!!
            for ( int i = Row - 1 , j = Col + 1 ; i >= 1 && j <= n ; i-- , j++ ) {
                New.erase ( {i,j} ) ;
            }
            // Left_Down !!!
            for ( int i = Row + 1 , j = Col - 1 ; i <= n && j >= 1 ; i++ , j-- ) {
                New.erase ( {i,j} ) ;
            }
            // Left_Up !!!
            for ( int i = Row - 1 , j = Col - 1 ; i >= 1 && j >= 1 ; i-- , j-- ) {
                New.erase ( {i,j} ) ;
            }
            for ( int i = 1 ; i <= Row ; i++ ) {
                for ( int j = 1 ; j <= n ; j++ ) {
                    New.erase ( {i,j} ) ;
                }
            }
            for ( NI = New.begin() ; NI != New.end() ; NI++ ) {
                Curr_Node_Visited_From [ NI->first ] [ NI->second ] . insert ( {Row,Col} ) ;
            }
            SOL ( Grid , New , Ans , n , Curr_Node_Visited_From , Op+1 ) ;
            Grid[Row][Col] = '.' ;
        }
    }
public:
    std::vector < std::vector < std::string > > solveNQueens ( int n ) {
        std::vector < std::vector < char > > Grid ( n+1 , std::vector < char > ( n+1 , '.' ) ) ;
        std::set < std::pair < int , int > > Empty ;
        int i = 0 , j = 0 ;
        for ( i = 1 ; i <= n ; i++ ) {
            for ( j = 1 ; j <= n ; j++ ) {
                Empty.insert ( {i,j} ) ;
            }
        }
        std::vector < std::vector < std::set < std::pair < int , int > > > > Curr_Node_Visited_From ( n+1 , std::vector < std::set < std::pair < int , int > > > ( n+1 ) ) ;
        std::set < std::vector < std::string > > Ans ; std::set < std::vector < std::string > > :: iterator Ite ;
        int Op = 1 ;
        SOL ( Grid , Empty , Ans , n , Curr_Node_Visited_From , Op ) ;
        std::vector < std::vector < std::string > > Res ;
        for ( Ite = Ans.begin() ; Ite != Ans.end() ; Ite++ ) {
            Res.push_back ( *Ite ) ;
        }
        return Res ;
    }
};
33146