Solution: N-Queens
Tags: algorithms, javascript, java, python
Published: 2021-05-22 12:12:48

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/n-queens/discuss/1223346).*

---

#### [Leetcode Problem #51 (*Hard*): N-Queens](https://leetcode.com/problems/n-queens/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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**_.
>
Each solution contains a distinct board configuration of the n-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space, respectively.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
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
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg)
>
Example 2:||
|---:|---|
Input:|n = 1
Output:|[["Q"]]

---

#### ***Constraints:***
>
 - `1 <= n <= 9`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

A naive approach here would attempt every possible combination of locations, but there are **(N^2)! / (N^2 - N)!** different combinations, which is up to **~1e17** when **N = 9**. Instead, we need to make sure we only attempt to place queens where it's feasible to do so, based on the instructions. This would seem to call for a **depth first search** (**DFS**) approach with a **recursive** helper function (**place**), so that we only pursue workable combinations without wasting time on known dead-ends.

First, we should consider how the queens will be placed. Since each row can only have one queen, our basic process will be to **place** a queen and then recurse to the next row. On each row, we'll have to iterate through the possible options, check the cell for validity, then **place** the queen on the **board**. Once the recursion **return**s, we can **backtrack** and iterate to the next cell in the row.

Since a queen has four axes of attack, we'll need to check the three remaining axes (other than the horizontal row, which our iteration will naturally take care of) for validity. There are **N** possible columns and **2 * N - 1** possible left-downward diagonals and right-downward diagonals. With a constraint of **1 <= N <= 9,** each of the two diagonal states represents up to **17 bits**' worth of data and the vertical state up to **9 bits**, so we can use **bit manipulation** to store these states efficiently.

So for each recursive call to **place** a queen, we should pass along the board state in the form of only three integers (**vert, ldiag, rdiag**). We can then use **bitmasks** to check for cell validity before attempting to recurse to the next row.

Since our **board** is an **N^2** matrix, we can use backtracking here to good effect. If we successfully reach the end of the board without failing, we should push a copy of  board with the rows as strings onto our answer array (**ans**). _(**Note**: It is possible to lower the **extra space** to only the size of the recursion stack, **O(N)**, by procedurally generating the results directly in **ans**, but it doesn't represent a great deal of space savings compared to the extra processing it requires.)_

 - _**Time Complexity: O(N!)** which represents the maximum number of queens placed_
 - _**Space Complexity: O(N^2)** for the board_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var solveNQueens = function(N) {
    let ans = [],
        board = Array.from({length: N}, () => new Array(N).fill('.'))
    
    const place = (i, vert, ldiag, rdiag) => {
        if (i === N) {
            let res = new Array(N)
            for (let row = 0; row < N; row++)
                res[row] = board[row].join("")
            ans.push(res)
            return
        }
        for (let j = 0; j < N; j++) {
            let vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j)
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue
            board[i][j] = 'Q'
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
            board[i][j] = '.'
        }
    }

    place(0,0,0,0)
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def solveNQueens(self, N: int) -> List[List[str]]:
        ans = []
        board = [['.'] * N for _ in range(N)]
        
        def place(i: int, vert: int, ldiag: int, rdiag:int) -> None:
            if i == N:
                ans.append(["".join(row) for row in board])
                return
            for j in range(N):
                vmask, lmask, rmask = 1 << j, 1 << (i+j), 1 << (N-i-1+j)
                if vert & vmask or ldiag & lmask or rdiag & rmask: continue
                board[i][j] = 'Q'
                place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
                board[i][j] = '.'
            
        place(0,0,0,0)
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    List<List<String>> ans;
    char[][] board;
    
    public List<List<String>> solveNQueens(int N) {
        ans = new ArrayList<>();
        board = new char[N][N];
        for (char[] row : board) Arrays.fill(row, '.');
        place(0,0,0,0);
        return ans;
    }
    
    private void place(int i, int vert, int ldiag, int rdiag) {
        int N = board.length;
        if (i == N) {
            List<String> res = new ArrayList<>();
            for (char[] row : board) res.add(new String(row));
            ans.add(res);
            return;
        }
        for (int j = 0; j < N; j++) {
            int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
            if ((vert & vmask) + (ldiag & lmask) + (rdiag & rmask) > 0) continue;
            board[i][j] = 'Q';
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask);
            board[i][j] = '.';
        }
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    vector<vector<string>> solveNQueens(int N) {
        ans.clear();
        board.resize(N, string(N, '.'));
        place(0,0,0,0);
        return ans;
    }
    
private:
    vector<vector<string>> ans;
    vector<string> board;
    
    void place(int i, int vert, int ldiag, int rdiag) {
        int N = board.size();
        if (i == N) {
            vector<string> res;
            for (auto row : board) res.push_back(row);
            ans.push_back(res);
            return;
        }
        for (int j = 0; j < N; j++) {
            int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue;
            board[i][j] = 'Q';
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask);
            board[i][j] = '.';
        }
    }
};
```