<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:
    // Check karte hai agar current row aur column par Queen place karna safe hai ya nahi
    bool isSafe(int row,int col, vector<string> board ,int n){

        int diaRow=row;
        int diaCol=col;

        // Upper left diagonal check karte hai
        while(row>=0 && col>=0){
            if(board[row][col]=='Q')return false;
            row--;col--;
        }

        // Left side check karte hai
        col=diaCol;
        row=diaRow;

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

        // Lower left diagonal check karte hai
        row=diaRow;
        col=diaCol;

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

        // Agar sab jagah safe hai to true return karte hai
        return true;
    }

    // Recursive function jo Queens place karte hai
    void solve(int col,int &ans,vector<string> &board,int n ){
        // Agar last column tak Queen safely place ho gayi, to solution mil gaya
        if(col==n){
            ans++;
            return;
        }

        // Har row par check karte hai current column me
        for(int row=0; row<n ;row++){
            if(isSafe(row,col,board,n)){
                board[row][col]='Q'; // Queen place karte hai
                solve(col+1,ans,board,n); // Next column par jate hai
                board[row][col]='.'; // Backtrack karte hai
            }
        }
    }

    // N-Queens problem ke liye total solutions return karte hai
    int totalNQueens(int n) {
        int ans=0;
        vector<string> board(n, string(n, '.'));
        solve(0,ans,board,n);
        return ans;
    }
};

/*
Example Dry Run:
Suppose n = 4:

Configuration 1:
Step 1: Place Q at (0, 0)
Q . . .
. . . .
. . . .
. . . .

Step 2: Place Q at (1, 2)
Q . . .
. . Q .
. . . .
. . . .

Step 3: Place Q at (2, 1)
Q . . .
. . Q .
. Q . .
. . . .

Step 4: Place Q at (3, 3)
Q . . .
. . Q .
. Q . .
. . . Q

Result:
Q . . .
. . Q .
. Q . .
. . . Q

Configuration 2:
Step 1: Place Q at (0, 1)
. Q . .
. . . .
. . . .
. . . .

Step 2: Place Q at (1, 3)
. Q . .
. . . Q
. . . .
. . . .

Step 3: Place Q at (2, 0)
. Q . .
. . . Q
Q . . .
. . . .

Step 4: Place Q at (3, 2)
. Q . .
. . . Q
Q . . .
. . Q .

Result:
. Q . .
. . . Q
Q . . .
. . Q .

Final Solutions:
1) Q . . .        2) . Q . .
   . . Q .           . . . Q
   . Q . .           Q . . .
   . . . Q           . . Q .

Time Complexity: O(N!) - Because we try to place queens in each row and column with backtracking.
Space Complexity: O(N^2) - Because of the board used to keep track of placements.
*/

43407