import math
from typing import List, Optional, Tuple

def place_words_in_crossword(words: List[str], size: Optional[int] = None) -> List[List[str]]:
    """
    Places words in a square grid to form a crossword puzzle using backtracking.
    
    Args:
        words: List of uppercase words to place (2-15 chars each)
        size: Optional grid size (n x n). If None, automatically calculated
        
    Returns:
        2D list representing the grid with letters or '.' for empty cells.
        Returns empty list if placement is impossible.
    """
    # Handle edge cases
    if not words:
        return []
    
    # Remove duplicates and filter valid words
    valid_words = list(set([word.upper() for word in words if 2 <= len(word) <= 15]))
    if not valid_words:
        return []
    
    # Sort words by length descending for better placement strategy
    valid_words.sort(key=len, reverse=True)
    
    # Calculate grid size if not provided
    if size is None:
        # Estimate based on total character count and longest word
        total_chars = sum(len(word) for word in valid_words)
        min_size = max(
            math.ceil(math.sqrt(total_chars * 2)),  # Character density estimate
            len(valid_words[0])  # Must fit longest word
        )
        size = min_size
    
    # Try progressively larger grids if placement fails
    max_attempts = 3
    for attempt in range(max_attempts):
        current_size = size + attempt
        grid = _create_empty_grid(current_size)
        
        if _place_words_backtrack(grid, valid_words, 0, []):
            return grid
    
    return []  # Failed to place all words

def _create_empty_grid(size: int) -> List[List[str]]:
    """Creates an empty grid filled with dots."""
    return [['.' for _ in range(size)] for _ in range(size)]

def _place_words_backtrack(grid: List[List[str]], words: List[str], 
                          word_index: int, placed_words: List[Tuple]) -> bool:
    """
    Recursive backtracking function to place words in the grid.
    
    Args:
        grid: Current state of the grid
        words: List of words to place
        word_index: Index of current word being placed
        placed_words: List of (word, row, col, direction) tuples for placed words
        
    Returns:
        True if all words can be placed, False otherwise
    """
    # Base case: all words placed successfully
    if word_index == len(words):
        return True
    
    current_word = words[word_index]
    grid_size = len(grid)
    
    # Try all possible positions and orientations
    for row in range(grid_size):
        for col in range(grid_size):
            for direction in ['horizontal', 'vertical']:
                if _can_place_word(grid, current_word, row, col, direction):
                    # Place the word
                    original_state = _place_word(grid, current_word, row, col, direction)
                    placed_words.append((current_word, row, col, direction))
                    
                    # Recursively try to place remaining words
                    if _place_words_backtrack(grid, words, word_index + 1, placed_words):
                        return True
                    
                    # Backtrack: remove the word and restore grid state
                    _remove_word(grid, current_word, row, col, direction, original_state)
                    placed_words.pop()
    
    return False

def _can_place_word(grid: List[List[str]], word: str, row: int, col: int, direction: str) -> bool:
    """
    Checks if a word can be placed at the given position and direction.
    
    Args:
        grid: Current grid state
        word: Word to place
        row, col: Starting position
        direction: 'horizontal' or 'vertical'
        
    Returns:
        True if word can be placed, False otherwise
    """
    grid_size = len(grid)
    word_len = len(word)
    
    # Check if word fits in grid bounds
    if direction == 'horizontal':
        if col + word_len > grid_size:
            return False
        # Check each position
        for i, char in enumerate(word):
            current_cell = grid[row][col + i]
            if current_cell != '.' and current_cell != char:
                return False
    else:  # vertical
        if row + word_len > grid_size:
            return False
        # Check each position
        for i, char in enumerate(word):
            current_cell = grid[row + i][col]
            if current_cell != '.' and current_cell != char:
                return False
    
    # Additional validation: ensure word doesn't create invalid adjacent letters
    return _validate_word_placement(grid, word, row, col, direction)

def _validate_word_placement(grid: List[List[str]], word: str, row: int, col: int, direction: str) -> bool:
    """
    Validates that placing a word doesn't create invalid letter adjacencies.
    """
    grid_size = len(grid)
    
    if direction == 'horizontal':
        # Check cells before and after the word
        if col > 0 and grid[row][col - 1] != '.':
            return False
        if col + len(word) < grid_size and grid[row][col + len(word)] != '.':
            return False
        
        # Check perpendicular adjacencies
        for i, char in enumerate(word):
            current_col = col + i
            if grid[row][current_col] == '.':  # Only check empty cells
                # Check above and below
                if row > 0 and grid[row - 1][current_col] != '.' and not _has_crossing_word(grid, row - 1, current_col, 'vertical'):
                    return False
                if row < grid_size - 1 and grid[row + 1][current_col] != '.' and not _has_crossing_word(grid, row + 1, current_col, 'vertical'):
                    return False
    
    else:  # vertical
        # Check cells before and after the word
        if row > 0 and grid[row - 1][col] != '.':
            return False
        if row + len(word) < grid_size and grid[row + len(word)][col] != '.':
            return False
        
        # Check perpendicular adjacencies
        for i, char in enumerate(word):
            current_row = row + i
            if grid[current_row][col] == '.':  # Only check empty cells
                # Check left and right
                if col > 0 and grid[current_row][col - 1] != '.' and not _has_crossing_word(grid, current_row, col - 1, 'horizontal'):
                    return False
                if col < grid_size - 1 and grid[current_row][col + 1] != '.' and not _has_crossing_word(grid, current_row, col + 1, 'horizontal'):
                    return False
    
    return True

def _has_crossing_word(grid: List[List[str]], row: int, col: int, direction: str) -> bool:
    """
    Checks if there's a word crossing at the given position in the specified direction.
    """
    # This is a simplified check - in a full implementation, you'd track placed words
    return True  # For now, allow crossings

def _place_word(grid: List[List[str]], word: str, row: int, col: int, direction: str) -> List[Tuple]:
    """
    Places a word in the grid and returns the original state for backtracking.
    
    Returns:
        List of (row, col, original_char) tuples for restoration
    """
    original_state = []
    
    if direction == 'horizontal':
        for i, char in enumerate(word):
            original_state.append((row, col + i, grid[row][col + i]))
            grid[row][col + i] = char
    else:  # vertical
        for i, char in enumerate(word):
            original_state.append((row + i, col, grid[row + i][col]))
            grid[row + i][col] = char
    
    return original_state

def _remove_word(grid: List[List[str]], word: str, row: int, col: int, 
                direction: str, original_state: List[Tuple]) -> None:
    """
    Removes a word from the grid by restoring the original state.
    """
    for r, c, original_char in original_state:
        grid[r][c] = original_char

# Example usage
if __name__ == "__main__":
    # Test with simple words
    words = ["CAT", "DOG", "ACT"]
    grid = place_words_in_crossword(words)
    
    if grid:
        print("Generated crossword grid:")
        print('\n'.join(' '.join(row) for row in grid))
    else:
        print("Could not generate crossword grid")
    
    print("\n" + "="*30 + "\n")
    
    # Test with longer words
    words2 = ["HELLO", "WORLD", "PYTHON"]
    grid2 = place_words_in_crossword(words2)
    
    if grid2:
        print("Generated crossword grid for longer words:")
        print('\n'.join(' '.join(row) for row in grid2))
    else:
        print("Could not generate crossword grid for longer words")