Solution: N-Queens II

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 #52 (Hard): N-Queens II

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 the number of distinct solutions to the n-queens puzzle.

Examples:

Example 1:
Input:	n = 4
Output:	2
Explanation:	There are two distinct solutions to the 4-queens puzzle as shown.
Visual:

Example 2:
Input:	n = 1
Output:	1

Constraints:

• 1 <= n <= 9

Idea:

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

(Note: This problem is an easier duplicate to the previous problem, 51: N-Queens, except that it doesn't require us to return the actual boards, just the count.)

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.

Rather than store the whole board, we can save on space complexity if we only keep track of the different axes of attack in which a queen might be placed. 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.

If we successfully reach the end of the board without failing, we should increment our answer counter (ans).

• Time Complexity: O(N!) which represents the maximum number of queens placed
• Space Complexity: O(N) for the recursion stack

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var totalNQueens = function(N) {
    let ans = 0

    const place = (i, vert, ldiag, rdiag) => {
        if (i === N) ans++
        else 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
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
        }
    }

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

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def totalNQueens(self, N: int) -> int:
        self.ans = 0

        def place(i: int, vert: int, ldiag: int, rdiag:int) -> None:
            if i == N: self.ans += 1
            else:
                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
                    place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)

        place(0,0,0,0)
        return self.ans

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    int ans;

    public int totalNQueens(int N) {
        ans = 0;
        place(0,0,0,0,N);
        return ans;
    }

    private void place(int i, int vert, int ldiag, int rdiag, int N) {
        if (i == N) ans++;
        else 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;
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
        }
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    int totalNQueens(int N) {
        ans = 0;
        place(0,0,0,0,N);
        return ans;
    }

private:
    int ans;

    void place(int i, int vert, int ldiag, int rdiag, int N) {
        if (i == N) ans++;
        else 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;
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
        }
    }
};