# N-Queens
**Difficulty:** HARD
[External](https://leetcode.com/problems/n-queens)
Canonical: https://scaleengineer.com/dsa/problems/n-queens
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Samsung](https://scaleengineer.com/companies/samsung), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.

Given an integer `n`, return _all distinct solutions to the **n-queens puzzle**_. You may return the answer in **any order**.

Each solution contains a distinct board configuration of the n-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space, respectively.

**Example 1:**

![](https://assets.glich.co/dsa/n-queens/image0.jpg) 

**Input:** n = 4
**Output:** [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
**Explanation:** There exist two distinct solutions to the 4-queens puzzle as shown above

**Example 2:**

**Input:** n = 1
**Output:** [["Q"]]

**Constraints:**

* `1 <= n <= 9`

# Approaches
## Backtracking with On-the-fly Validation
This approach uses a standard backtracking algorithm to explore all possible placements of queens, one row at a time. For each potential queen placement, it validates the move by checking all previously placed queens to ensure there are no attacks. This validation step involves scanning the columns and diagonals.
**Time:** O(N! * N) · **Space:** O(N^2)
**Pros:** Conceptually straightforward implementation of backtracking.; Does not require extra space for tracking attacked squares, relying only on the board itself.
**Cons:** Inefficient due to the O(N) safety check performed at every step of the recursion.; For larger N (though outside the problem constraints), this approach would be significantly slower than optimized versions.
### Explanation
The core idea is a recursive function, let's call it `backtrack(row, board)`. The function tries to place a queen in the given `row`. It iterates through all columns `col` from `0` to `n-1` for the current `row`. For each `(row, col)`, it calls a helper function `isSafe(row, col, board)` to check if placing a queen there is valid. The `isSafe` function checks three conditions for all previously placed queens (in rows `0` to `row-1`):
1. No queen in the same column.
2. No queen on the upper-left diagonal.
3. No queen on the upper-right diagonal.

This check takes `O(row)` time, which is `O(n)` in the worst case. If `isSafe` returns true, we place the queen (`board[row][col] = 'Q'`), and recursively call `backtrack(row + 1, board)`. After the recursive call returns, we must backtrack by removing the queen (`board[row][col] = '.'`) to explore other possibilities in the current row. The base case for the recursion is when `row == n`, which means we have successfully placed `n` queens. At this point, we format the current board configuration and add it to our list of solutions.

```java
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backtrack(0, n, board, result);
        return result;
    }

    private boolean isSafe(int row, int col, char[][] board, int n) {
        // Check column upwards
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // Check upper-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // Check upper-right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    private void backtrack(int row, int n, char[][] board, List<List<String>> result) {
        if (row == n) {
            result.add(constructSolution(board));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, board, n)) {
                board[row][col] = 'Q';
                backtrack(row + 1, n, board, result);
                board[row][col] = '.'; // Backtrack
            }
        }
    }

    private List<String> constructSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            solution.add(new String(board[i]));
        }
        return solution;
    }
}
```
### Algorithm
- Create a recursive function `backtrack(row, board)`.
- **Base Case**: If `row` equals `n`, a solution has been found. Convert the `board` to the required list of strings format and add it to the results.
- **Recursive Step**: For the current `row`, iterate through each column `col` from `0` to `n-1`.
- For each cell `(row, col)`, check if it's a safe position to place a queen using a helper function `isSafe()`.
- The `isSafe()` function checks upwards from `(row, col)` for any other queens in the same column or diagonals. This takes O(N) time.
- If the position is safe, place a queen at `board[row][col] = 'Q'`.
- Make a recursive call: `backtrack(row + 1, board)`.
- After the recursive call returns, backtrack by removing the queen from `board[row][col]` to explore other possibilities.

## Optimized Backtracking with Constant-Time Validation
This approach improves upon the basic backtracking solution by optimizing the safety check. Instead of scanning the board each time, it uses auxiliary data structures (like boolean arrays) to keep track of which columns and diagonals are already under attack. This allows for an O(1) time complexity for the safety check at each step.
**Time:** O(N!) · **Space:** O(N^2)
**Pros:** Highly efficient due to the O(1) safety check.; This is the standard and most common solution for the N-Queens problem.
**Cons:** Requires extra O(N) space for the tracking arrays.; The logic for diagonal indexing can be slightly more complex to grasp initially.
### Explanation
This optimized approach maintains the same backtracking structure but drastically speeds up the validation process. We use three boolean arrays to keep track of attacked squares:
- `cols[n]`: `cols[c]` is true if column `c` is occupied.
- `diag1[2n-1]`: For anti-diagonals. All cells `(r, c)` on the same anti-diagonal have a constant `r - c`. We map this value (from `-(n-1)` to `n-1`) to an index `r - c + n - 1`.
- `diag2[2n-1]`: For main-diagonals. All cells `(r, c)` on the same main-diagonal have a constant `r + c`. This value (from `0` to `2n-2`) can be used directly as an index.

With these arrays, checking if a cell `(row, col)` is safe becomes an O(1) lookup. When we place a queen, we set the corresponding indices in the three arrays to `true`. When we backtrack, we reset them to `false`. This eliminates the O(N) scan required in the previous approach.

For even better performance, the boolean arrays can be replaced with integer bitmasks. Each bit in the integer can represent a column or a diagonal, and checks/updates can be done using fast bitwise operations. This doesn't change the asymptotic complexity but can be faster in practice.

```java
class Solution {
    private List<List<String>> result;
    private char[][] board;
    private int n;
    private boolean[] cols;
    private boolean[] diag1; // For diagonals where row - col is constant
    private boolean[] diag2; // For diagonals where row + col is constant

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.result = new ArrayList<>();
        this.board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        
        this.cols = new boolean[n];
        this.diag1 = new boolean[2 * n - 1];
        this.diag2 = new boolean[2 * n - 1];
        
        backtrack(0);
        return result;
    }

    private void backtrack(int row) {
        if (row == n) {
            result.add(constructSolution());
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1Index = row - col + n - 1;
            int d2Index = row + col;

            if (!cols[col] && !diag1[d1Index] && !diag2[d2Index]) {
                // Place queen
                board[row][col] = 'Q';
                cols[col] = true;
                diag1[d1Index] = true;
                diag2[d2Index] = true;

                // Recur for next row
                backtrack(row + 1);

                // Backtrack
                board[row][col] = '.';
                cols[col] = false;
                diag1[d1Index] = false;
                diag2[d2Index] = false;
            }
        }
    }

    private List<String> constructSolution() {
        List<String> solution = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            solution.add(new String(board[i]));
        }
        return solution;
    }
}
```
### Algorithm
- Initialize boolean arrays: `cols[n]`, `diag1[2n-1]`, and `diag2[2n-1]` to track attacked columns and diagonals.
- Create a recursive function `backtrack(row)`.
- **Base Case**: If `row` equals `n`, a solution is found. Add the current board configuration to the results.
- **Recursive Step**: For the current `row`, iterate through each column `col` from `0` to `n-1`.
- Calculate diagonal indices: `d1 = row - col + n - 1` and `d2 = row + col`.
- Check in `O(1)` time if the position is safe: `!cols[col] && !diag1[d1] && !diag2[d2]`.
- If safe, place the queen, mark the corresponding column and diagonals as occupied in the boolean arrays, and make a recursive call: `backtrack(row + 1)`.
- After the call returns, backtrack by removing the queen and un-marking the column and diagonals in the boolean arrays.

# Solutions
### CSharp

```csharp
public class Solution { private int n ; private int [] col ; private int [] dg ; private int [] udg ; private IList < IList < string >> ans = new List < IList < string >>(); private IList < string > t = new List < string >(); public IList < IList < string >> SolveNQueens ( int n ) { this . n = n ; col = new int [ n ]; dg = new int [ n << 1 ]; udg = new int [ n << 1 ]; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i == n ) { ans . Add ( new List < string >( t )); return ; } for ( int j = 0 ; j < n ; ++ j ) { if ( col [ j ] + dg [ i + j ] + udg [ n - i + j ] == 0 ) { char [] row = new char [ n ]; Array . Fill ( row , '.' ); row [ j ] = 'Q' ; t . Add ( new string ( row )); col [ j ] = dg [ i + j ] = udg [ n - i + j ] = 1 ; dfs ( i + 1 ); col [ j ] = dg [ i + j ] = udg [ n - i + j ] = 0 ; t . RemoveAt ( t . Count - 1 ); } } } }
```

### Java

```java
class Solution {
private
  List<List<String>> ans = new ArrayList<>();
private
  int[] col;
private
  int[] dg;
private
  int[] udg;
private
  String[][] g;
private
  int n;
public
  List<List<String>> solveNQueens(int n) {
    this.n = n;
    col = new int[n];
    dg = new int[n << 1];
    udg = new int[n << 1];
    g = new String[n][n];
    for (int i = 0; i < n; ++i) {
      Arrays.fill(g[i], ".");
    }
    dfs(0);
    return ans;
  }
private
  void dfs(int i) {
    if (i == n) {
      List<String> t = new ArrayList<>();
      for (int j = 0; j < n; ++j) {
        t.add(String.join("", g[j]));
      }
      ans.add(t);
      return;
    }
    for (int j = 0; j < n; ++j) {
      if (col[j] + dg[i + j] + udg[n - i + j] == 0) {
        g[i][j] = "Q";
        col[j] = dg[i + j] = udg[n - i + j] = 1;
        dfs(i + 1);
        col[j] = dg[i + j] = udg[n - i + j] = 0;
        g[i][j] = ".";
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<string>> solveNQueens(int n) {
    vector<int> col(n);
    vector<int> dg(n << 1);
    vector<int> udg(n << 1);
    vector<vector<string>> ans;
    vector<string> t(n, string(n, '.'));
    function<void(int)> dfs = [&](int i) -> void {
      if (i == n) {
        ans.push_back(t);
        return;
      }
      for (int j = 0; j < n; ++j) {
        if (col[j] + dg[i + j] + udg[n - i + j] == 0) {
          t[i][j] = 'Q';
          col[j] = dg[i + j] = udg[n - i + j] = 1;
          dfs(i + 1);
          col[j] = dg[i + j] = udg[n - i + j] = 0;
          t[i][j] = '.';
        }
      }
    };
    dfs(0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]: def dfs(i: int): if i == n: ans . append(["" . join(row) for row in g]) return for j in range(n): if col[j] + dg[i + j] + udg[n - i + j] == 0: g[i][j] = "Q" col[j] = dg[i + j] = udg[n - i + j] = 1 dfs(i + 1) col[j] = dg[i + j] = udg[n - i + j] = 0 g[i][j] = "." ans = [] g = [["."] * n for _ in range(n)] col = [0] * n dg = [0] * (n << 1) udg = [0] * (n << 1) dfs(0) return ans

```