Solution Explanation: N-Queens II

The N-Queens II problem asks to find the number of distinct solutions to place N chess queens on an NxN chessboard such that no two queens threaten each other. Two queens threaten each other if they share the same row, column, or diagonal.

The most efficient approach is using backtracking. We explore all possible placements recursively, pruning branches that lead to conflicts.

Algorithm:

1. State Representation: We use three boolean arrays to track conflicts:

   • cols: Tracks whether a column is occupied.
   • dg: Tracks whether a positive diagonal is occupied. The index represents the sum of row and column indices (row + col).
   • udg: Tracks whether a negative diagonal is occupied. The index represents the difference between the column and row indices (col - row + n -1), where n is the board size, to avoid negative indices.

2. Recursive Function dfs(row): This function explores placements starting from a given row.

   • Base Case: If row reaches n, a solution is found, so increment the ans counter (representing the number of solutions).
   • Recursive Step: For each column col in the current row:
     • Check for conflicts using cols[col], dg[row + col], and udg[col - row + n - 1].
     • If no conflict, mark the column, positive diagonal, and negative diagonal as occupied.
     • Recursively call dfs(row + 1) to explore placements in the next row.
     • After the recursive call (backtracking), unmark the column, positive diagonal, and negative diagonal to explore other possibilities.

Time and Space Complexity:

• Time Complexity: O(N!). In the worst case, we explore all possible permutations of queen placements, which is N!. However, the actual runtime is often much less due to the pruning performed by conflict checks.

• Space Complexity: O(N). The space is dominated by the three boolean arrays (cols, dg, udg), each of size proportional to N. The recursive call stack also uses space, but its maximum depth is N.

Code (Python):

class Solution:
    def totalNQueens(self, n: int) -> int:
        cols = [False] * n
        dg = [False] * (2 * n -1)
        udg = [False] * (2 * n - 1)
        ans = 0
 
        def dfs(row):
            nonlocal ans
            if row == n:
                ans += 1
                return
            for col in range(n):
                if not (cols[col] or dg[row + col] or udg[col - row + n - 1]):
                    cols[col] = dg[row + col] = udg[col - row + n - 1] = True
                    dfs(row + 1)
                    cols[col] = dg[row + col] = udg[col - row + n - 1] = False
 
        dfs(0)
        return ans

The code in other languages (Java, C++, Go, TypeScript, JavaScript, C#) follows the same algorithm with minor syntactic variations. The core logic of backtracking and conflict checking remains the same across all implementations.