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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

N-Queens II

Difficulty: Hard

Problem Description

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.

Key Insights

  • The queens must be placed such that they do not share the same row, column, or diagonal.
  • A backtracking approach is effective for exploring possible configurations of queen placements.
  • The solution involves recursively placing queens and backtracking when an invalid state is encountered.
  • The problem has symmetry, which can reduce the search space by only considering unique arrangements.

Space and Time Complexity

Time Complexity: O(n!), as we potentially place a queen in each row and check for valid placements. Space Complexity: O(n), due to the recursion stack and storage for column and diagonal tracking.

Solution

The solution employs a backtracking algorithm to explore all possible configurations of queens on the chessboard. We maintain arrays to track the columns and diagonals that are already occupied by queens to ensure no two queens threaten each other. The algorithm recursively attempts to place queens in each row and counts valid arrangements.

Code Solutions

def totalNQueens(n):
    def backtrack(row, cols, diag1, diag2):
        if row == n:
            return 1
        count = 0
        for col in range(n):
            if col not in cols and (row - col) not in diag1 and (row + col) not in diag2:
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                count += backtrack(row + 1, cols, diag1, diag2)
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
        return count

    return backtrack(0, set(), set(), set())
← Back to All Questions