We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

N-Queens II

Number: 52

Difficulty: Hard

Paid? No

Companies: Meta, Snowflake, Microsoft, Google, Bloomberg, Zenefits

Problem Description

Place n queens on an n x n chessboard such that no two queens can attack each other (i.e. no two queens share the same row, column, or diagonal). Return the number of distinct solutions.

Key Insights

  • Uses backtracking to generate all possible placements on the board.
  • Maintains sets (or equivalent data structures) to track columns and diagonals that are already threatened.
  • Recursively places one queen per row, ensuring constraints are met before moving to the next row.
  • When the last row is successfully reached, a valid arrangement is found and counted.

Space and Time Complexity

Time Complexity: O(n!) in the worst case due to the nature of recursive backtracking. Space Complexity: O(n) for the recursion stack and helper data structures for columns and diagonals.

Solution

We use a recursive backtracking approach where each recursion level corresponds to placing a queen on a specific row. Three sets (or similar structures) are used to check if a particular column or diagonal is already occupied by another queen:

  • One set for tracking columns.
  • One set for the "hill" diagonals (row - col remains constant).
  • One set for the "dale" diagonals (row + col remains constant).

At each recursive call, we try placing a queen in each column of the current row. If the placement does not conflict with any previously placed queen, we mark the column and appropriate diagonals as occupied and move on to the next row. When a valid configuration for all rows is found, we increment our solution count. Finally, we backtrack by removing the last placed queen before trying the next possibility.

Code Solutions

# Python solution using backtracking
class Solution:
    def totalNQueens(self, n: int) -> int:
        # Count variable to track the number of valid configurations
        self.count = 0

        # Backtracking helper function
        def backtrack(row, columns, diag1, diag2):
            # If we have placed queens in all rows, a valid solution is found
            if row == n:
                self.count += 1
                return

            # Iterate over columns in the current row
            for col in range(n):
                # Compute identifiers for the diagonals
                d1 = row - col  # "hill" diagonal
                d2 = row + col  # "dale" diagonal

                # Check if the column or either diagonal is already attacked
                if col in columns or d1 in diag1 or d2 in diag2:
                    continue

                # Place the queen: add the current col and diagonals to the respective sets
                columns.add(col)
                diag1.add(d1)
                diag2.add(d2)

                # Move on to the next row
                backtrack(row + 1, columns, diag1, diag2)

                # Backtrack: remove the queen and free the column and diagonals
                columns.remove(col)
                diag1.remove(d1)
                diag2.remove(d2)

        # Start the recursion from row 0 with empty sets for columns and diagonals
        backtrack(0, set(), set(), set())
        return self.count

# Example usage:
# solution = Solution()
# print(solution.totalNQueens(4))  # Output: 2
← Back to All Questions