
### Problem Statement

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

**INPUT**

- n = **4**

**OUTPUT**

- **[ [".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."] ]**

![N Queens](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg)

**EXPLANATION**

- There exist two distinct solutions to the 4-queens puzzle as shown above.

**Steps To Solve**

- Think of solution without code

  - So here we have to place n queens in our board so that no queen can kill other queens.
  - We cannot put more than 1 queen in one row.
  - Now we have to try all possible combinations by placing our queens in grid and return the ones in which no queens can kill other queens.
  - Well we will be using backtracking here .Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.
  - Once we generate a solution we store it in our array and then clear the board and look for another solution.We also backtrack if we reach a dead end.
  - For every location where we want to place our queen we check both diagonals above and the column using loop.If a queen is already present ,we don't place our new queen to that block.
  - Lets look at the code.

```js
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let res = [];
  let nQueens = new Array(n).fill(0).map(() => new Array(n).fill("."));
  solveNQueen(res, nQueens, 0, n);
  return res;
};

function solveNQueen(res, nQueens, row, n) {
  if (row === n) {
    res.push(nQueens.map((r) => r.join("")));
    return;
  }

  for (let col = 0; col < n; col++) {
    if (isValid(nQueens, row, col, n)) {
      nQueens[row][col] = "Q";
      solveNQueen(res, nQueens, row + 1, n);
      nQueens[row][col] = ".";
    }
  }
}

function isValid(nQueens, row, col, n) {
  //check if the column had a queen before.
  for (let i = 0; i < row; i++) {
    if (nQueens[i][col] === "Q") return false;
  }

  //check if the 45° diagonal had a queen before.
  for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
    if (nQueens[i][j] === "Q") return false;
  }

  //check if the 135° diagonal had a queen before.
  for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
    if (nQueens[i][j] === "Q") return false;
  }

  return true;
}
```

- To further optimize our solution instead of looping through column and diagonals,we can store the value of blocked column and blocked diagonals in an array.
- Lets first see how we store values for our diagonals.
  ||0|1|2|3|
  |-|-|-|-|-|
  |0 |0 |1 |2 |3 |
  | 1| 1| 2|3 |4 |
  | 2| 2| 3| 4|5 |
  | 3| 3| 4|5 |6 |
- In every block we place row+col.We now see that we have our (2\*n-1) diagonal i.e 7.
- So we create an ndiag array of size 7.
- To block a diagonal we will store true where the index has value row+col.Example if we want to block a diagonal 3 we will do ndiag[3] = true.
- Similarly let check our reverse diagonal.
  ||0|1|2|3|
  |-|-|-|-|-|
  |0 |3|2 |1 |0 |
  | 1| 4| 3|2 |1 |
  | 2| 5| 4| 3|2 |
  | 3| 6| 5|4 |3 |
- In every block, we place row-col+length of board - 1. We now see that we have our (2\*n-1) diagonal i.e 7.
- So we create an rdiag array of size 7.
- To block a diagonal we will store true where the index has value row-col+length of board - 1.Example if we want to block a diagonal 3 we will do rdiag[3] = true.
- So if we place a queen at [0][0] we block entire 0th column ,we mark the r+c block as true in ndiag and r-c+n-1 block i.e 3 block in rdiag to true.We cannot place our queen in blocks with this number.

```js
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let res = [];
  let nQueens = new Array(n).fill(0).map(() => new Array(n).fill("."));
  let cols = new Array(n).fill(false);
  let ndiag = new Array(2 * n - 1).fill(false);
  let rdiag = new Array(2 * n - 1).fill(false);
  solveNQueen(res, nQueens, 0, n, cols, ndiag, rdiag);
  return res;
};

function solveNQueen(res, nQueens, row, n, cols, ndiag, rdiag) {
  if (row === n) {
    res.push(nQueens.map((r) => r.join("")));
    return;
  }

  for (let col = 0; col < n; col++) {
    if (!cols[col] && !ndiag[row + col] && !rdiag[row - col + n - 1]) {
      nQueens[row][col] = "Q";
      cols[col] = true;
      ndiag[row + col] = true;
      rdiag[row - col + n - 1] = true;
      solveNQueen(res, nQueens, row + 1, n, cols, ndiag, rdiag);
      nQueens[row][col] = ".";
      cols[col] = false;
      ndiag[row + col] = false;
      rdiag[row - col + n - 1] = false;
    }
  }
}
```

- Instead of using an array we can use bits to store our values for cols,ndiag and rdiag.
- Suppose we want to block the 2 diagonal then we ON the bit of the 2 location.
- Everything else will remain the same.
- To check if bit is OFF we do (location & (1<< location) === 0)
- To toggle bits we do (location ^= (1<< location)).
- Lets look at code.

```js
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let res = [];
  let nQueens = new Array(n).fill(0).map(() => new Array(n).fill("."));
  let cols = 0;
  let ndiag = 0;
  let rdiag = 0;
  solveNQueen(res, nQueens, 0, n, cols, ndiag, rdiag);
  return res;
};

function solveNQueen(res, nQueens, row, n, cols, ndiag, rdiag) {
  if (row === n) {
    res.push(nQueens.map((r) => r.join("")));
    return;
  }

  for (let col = 0; col < n; col++) {
    if (
      (cols & (1 << col)) === 0 && //check if bit is off already
      (ndiag & (1 << (row + col))) === 0 &&
      (rdiag & (1 << (row - col + n - 1))) === 0
    ) {
      nQueens[row][col] = "Q";
      cols ^= 1 << col; //toggle the bit of col
      ndiag ^= 1 << (row + col);
      rdiag ^= 1 << (row - col + n - 1);
      solveNQueen(res, nQueens, row + 1, n, cols, ndiag, rdiag);
      nQueens[row][col] = ".";
      cols ^= 1 << col;
      ndiag ^= 1 << (row + col);
      rdiag ^= 1 << (row - col + n - 1);
    }
  }
}
```

###### Time and Space Complexity

Time Complexity is **O(N!)**.
Space complexity in this case is **O(N\*N)**.
