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