<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>

// Solution class to solve the N-Queens problem
class Solution{
    private:
        int size;                                   // Size of the baord (n x n)
        vector<vector<string>> solutions;           // Vector to store all possible solutions


        // Making use of a helper function to get  the solutions in the correct output format.
        vector<string> createBoard(vector<vector<char>> state){
            vector<string> board;                       // The current state of the board as strings
            for (int row = 0; row < size; ++row){
                // Create a string from the characters in the row and push to the board
                string current_row(state[row].begin(), state[row].end());
                board.push_back(current_row);
            }
            // Return the board in required format
            return board;
        }

        // Recursive function to backtrack and place queens on the board
        void backtrack(int row, unordered_set<int> diagonals, 
                        unordered_set<int> antiDiagonals, unordered_set<int> cols, 
                        vector<vector<char>> state){
                            
                            // Base case: if all queens have been placed, add the current board configuration to solutions
                            if (row == size){
                                solutions.push_back(createBoard(state));        // Convert the board to the correct format and store
                                return;
                            }

                            // Try placing a queen in every column of the current row
                            for (int col = 0; col < size; ++col){
                                int currDiagonal = row - col;
                                int currAntiDiagonal = row + col;

                                // Check to see if it is a safe place to place a queen by checking
                                // if the column, diagonal, or anti-diagonal, is already occupied
                                if (cols.count(col) || 
                                diagonals.count(currDiagonal) || 
                                antiDiagonals.count(currAntiDiagonal)) 
                                    continue;                               // If not safe, move to the next column
                                
                                // "Add" the queen to the board
                                // Place the queen on the board (mark this column, diagonal, and anti-diagonal as occupied)
                                cols.insert(col);
                                diagonals.insert(currDiagonal);
                                antiDiagonals.insert(currAntiDiagonal);
                                state[row][col] = 'Q';                          // Place the queen ('Q') on the board at (row, col)

                                // Recursively move on to the next row with the updated board state
                                backtrack(row + 1, diagonals, antiDiagonals, cols, state);

                                // "Remove" the Queen from the board since we have already 
                                // explored all valid paths using the above function call
                                cols.erase(col);
                                diagonals.erase(currDiagonal);
                                antiDiagonals.erase(currAntiDiagonal);
                                state[row][col] = '.';                      // Remove the queen from (row, col) (set it back to '.')
                            }
        }
    


    public:
        // Function to solve the N-Queens problem
        vector<vector<string>> solveNQueens (int n){
            size = n;           // Set the board size (n x n)

            // Initialize an empty board of size n x n filled with '.'
            vector<vector<char>> emptyBoard(size, vector<char>(size, '.'));

            // Start the backtracking process from the first row (row 0)
            backtrack(0, 
                        unordered_set<int>(),                           // Create an empty set of columns
                            unordered_set<int>(),                       // Create an empty set of diagonals
                                unordered_set<int>(),                   // Create an empty set of anti-diagonals
                                    emptyBoard);

            // Return all the solutions found
            return solutions;
        }
};
38209