Solution: N-Queens

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #51 (Hard): N-Queens

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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 2:
Input:	n = 1
Output:	[["Q"]]

---

Constraints:

• 1 <= n <= 9

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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 returns, 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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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] = '.';
        }
    }
};