52.N-Queens_II(Hard).md

52. N-Queens II (Hard)

Date and Time: Jul 28, 2024, 23:57 (EST)

Link: https://leetcode.com/problems/n-queens-ii/

Question:

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.

Example 1:

Input: n = 4

Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1

Output: 1

Constraints:

• 1 <= n <= 9

Walk-through:

This is the same as 51. N-Queens, except we don't need to keep track of board and the position of 'Q'.

Python Solution:

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = set()
        posDiag, negDiag = set(), set()
        res = 0
        def backtrack(r):
            nonlocal res
            if r == n:
                res += 1
                return
            for c in range(n):
                if c in cols or (r+c) in posDiag or (r-c) in negDiag:
                    continue
                cols.add(c)
                posDiag.add(r+c)
                negDiag.add(r-c)
                backtrack(r+1)
                cols.remove(c)
                posDiag.remove(r+c)
                negDiag.remove(r-c)
        backtrack(0)
        return res

Time Complexity: $O(n * n!)$
Space Complexity: $O(n)$

Java Solution:

class Solution {
    private int res;
    public int totalNQueens(int n) {
        res = 0;
        Set<Integer> cols = new HashSet<>();
        Set<Integer> posDiag = new HashSet<>();
        Set<Integer> negDiag = new HashSet<>();
        backtrack(0, n, cols, posDiag, negDiag);
        return res;
    }
    private void backtrack(int r, int n, Set<Integer> cols, Set<Integer> posDiag, Set<Integer> negDiag) {
        if (r == n) {
            res++;
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols.contains(c) || posDiag.contains(r+c) || negDiag.contains(r-c)) {
                continue;
            }
            cols.add(c);
            posDiag.add(r+c);
            negDiag.add(r-c);
            backtrack(r+1, n, cols, posDiag, negDiag);
            cols.remove(c);
            posDiag.remove(r+c);
            negDiag.remove(r-c);
        }
    }
}

C++ Solution:

class Solution {
public:
    int totalNQueens(int n) {
        res = 0;
        unordered_set<int> cols, posDiag, negDiag;
        backtrack(n, 0, cols, posDiag, negDiag);
        return res;
    }
private:
    int res;
    void backtrack(int n, int r, unordered_set<int>& cols, unordered_set<int>& posDiag, unordered_set<int>& negDiag) {
        if (r == n) {
            res++;
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols.count(c) || posDiag.count(r+c) || negDiag.count(r-c)) {
                continue;
            }
            cols.insert(c);
            posDiag.insert(r+c);
            negDiag.insert(r-c);
            backtrack(n, r+1, cols, posDiag, negDiag);
            cols.erase(c);
            posDiag.erase(r+c);
            negDiag.erase(r-c);            
        }
    }
};

Runtime and Memory comparison

Language	Runtime	Memory
Python3	47 ms	16.5 MB
Java	4 ms	41.5 MB
C++	14 ms	11.5 MB