Places N queens on an NxN chessboard so that no two queens threaten each other.

# N-Queens Problem - Backtracking # Description: Places N queens on an NxN chessboard so that no two queens threaten each other. # N-Queens Problem: Backtracking Solution def solve_n_queens(n): """ Solve the N-Queens problem by finding all possible ways to place N queens on an NxN chessboard without any queens threatening each other. Args: n (int): Size of the chessboard and number of queens. Returns: list: All valid queen configurations, where each configuration is represented by a list of column positions for each row. Time Complexity: O(N!) Space Complexity: O(N) """ def is_queen_safe(board, current_row, current_col): """ Check if placing a queen at the given position conflicts with existing queens. Args: board (list): Current board configuration current_row (int): Row of the new queen current_col (int): Column of the new queen Returns: bool: True if queen placement is safe, False otherwise """ # Check for queens in the same column and diagonals for row in range(current_row): # Same column check if board[row] == current_col: return False # Diagonal conflict check (using absolute value) column_diff = abs(board[row] - current_col) row_diff = current_row - row if column_diff == row_diff: return False return True def place_queens(board, current_row): """ Recursively place queens on the board using backtracking. Args: board (list): Current board configuration current_row (int): Current row being processed Modifies: solutions (list): Stores all valid board configurations """ # Base case: all queens are placed successfully if current_row == n: solutions.append(board.copy()) return # Try placing queen in each column of the current row for col in range(n): if is_queen_safe(board, current_row, col): # Place queen board[current_row] = col # Recursively place queens in next row place_queens(board, current_row + 1) # Backtrack (optional step in Python, but good for clarity) board[current_row] = -1 # Initialize solution storage and board solutions = [] initial_board = [-1] * n # Start the queen placement process place_queens(initial_board, 0) return solutions

Mar 28, 2025 - 04:49

# N-Queens Problem - Backtracking
# Description: Places N queens on an NxN chessboard so that no two queens threaten each other.

# N-Queens Problem: Backtracking Solution
def solve_n_queens(n):
    """
    Solve the N-Queens problem by finding all possible ways to place N queens 
    on an NxN chessboard without any queens threatening each other.

    Args:
        n (int): Size of the chessboard and number of queens.

    Returns:
        list: All valid queen configurations, where each configuration is 
              represented by a list of column positions for each row.

    Time Complexity: O(N!)
    Space Complexity: O(N)
    """
    def is_queen_safe(board, current_row, current_col):
        """
        Check if placing a queen at the given position conflicts with existing queens.

        Args:
            board (list): Current board configuration
            current_row (int): Row of the new queen
            current_col (int): Column of the new queen

        Returns:
            bool: True if queen placement is safe, False otherwise
        """
        # Check for queens in the same column and diagonals
        for row in range(current_row):
            # Same column check
            if board[row] == current_col:
                return False

            # Diagonal conflict check (using absolute value)
            column_diff = abs(board[row] - current_col)
            row_diff = current_row - row
            if column_diff == row_diff:
                return False

        return True

    def place_queens(board, current_row):
        """
        Recursively place queens on the board using backtracking.

        Args:
            board (list): Current board configuration
            current_row (int): Current row being processed

        Modifies:
            solutions (list): Stores all valid board configurations
        """
        # Base case: all queens are placed successfully
        if current_row == n:
            solutions.append(board.copy())
            return

        # Try placing queen in each column of the current row
        for col in range(n):
            if is_queen_safe(board, current_row, col):
                # Place queen
                board[current_row] = col

                # Recursively place queens in next row
                place_queens(board, current_row + 1)

                # Backtrack (optional step in Python, but good for clarity)
                board[current_row] = -1

    # Initialize solution storage and board
    solutions = []
    initial_board = [-1] * n

    # Start the queen placement process
    place_queens(initial_board, 0)

    return solutions