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

Number: 51

Difficulty: Hard

Paid? No

Companies: Google, Microsoft, Amazon, Oracle, TikTok, Bloomberg, Meta, tcs, Uber, Goldman Sachs, Apple, Adobe, Citadel

Problem Description

Place n queens on an n x n chessboard such that no two queens attack each other. Return all distinct board configurations where each configuration is represented as a list of strings. Each string represents a row of the chessboard, using "Q" for queens and "." for empty spaces.

Key Insights

  • Use backtracking to explore potential positions row by row.
  • Use sets to track which columns and diagonals are under attack.
  • Diagonals can be tracked by (row - col) and (row + col), ensuring that queens do not conflict along any diagonal.
  • Recursively build each valid board configuration and backtrack when a conflict arises.

Space and Time Complexity

Time Complexity: O(n!) in the worst-case scenario, as the solution explores permutations for queen placements. Space Complexity: O(n^2) for storing board configurations and O(n) for recursion stack and conflict-tracking sets.

Solution

We use a backtracking algorithm that places queens row by row. For each row, we try placing a queen in each column. Before placing, we check if the column, main diagonal (row - col), and anti-diagonal (row + col) are free using dedicated sets. If a queen can be safely placed, we mark the column and diagonals as occupied and recurse to the next row. Once all rows are processed, the board configuration is a valid solution and is added to the result. After that, we backtrack by unmarking the sets and removing the queen from the board. This systematic approach ensures all possible configurations are considered.

Code Solutions

def solveNQueens(n):
    result = []
    
    # Helper function to backtrack
    def backtrack(row, columns, diag1, diag2, board):
        # Base case: if all rows are filled, add a copy of board to result
        if row == n:
            result.append(list(board))
            return
        
        # Try to place a queen in each column in the current row
        for col in range(n):
            # Check if the column or diagonals are not under attack
            if col in columns or (row - col) in diag1 or (row + col) in diag2:
                continue
            
            # Place the queen
            board[row] = '.' * col + 'Q' + '.' * (n - col - 1)
            # Mark the column and diagonals as occupied
            columns.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            # Move to the next row
            backtrack(row + 1, columns, diag1, diag2, board)
            
            # Backtrack: remove the queen and unmark the sets
            columns.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    # Initialize board with empty rows
    board = ["." * n for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return result

# Example usage:
print(solveNQueens(4))
← Back to All Questions