def backtrack(a, k, input_data):
    """
    Algoritmo genérico de backtracking
    
    Args:
        a: solución parcial (vector)
        k: posición actual en el vector
        input_data: datos del problema
    """
    # Caso base: ¿solución completa?
    if is_a_solution(a, k, input_data):
        process_solution(a, k, input_data)
    else:
        # Generar candidatos para la posición k
        candidates = construct_candidates(a, k, input_data)
        
        # Probar cada candidato
        for candidate in candidates:
            a[k] = candidate
            make_move(a, k, input_data)  # Opcional: actualizar estado
            
            # Recursión: extender solución
            backtrack(a, k + 1, input_data)
            
            unmake_move(a, k, input_data)  # Opcional: deshacer cambios
    
    # Backtrack implícito al terminar función

# Componentes a implementar para cada problema:

def is_a_solution(a, k, input_data):
"""¿La solución parcial de k elementos está completa?"""
pass

def construct_candidates(a, k, input_data):
"""Generar candidatos válidos para la posición k"""
pass

def process_solution(a, k, input_data):
"""Manejar la solución completa (imprimir, contar, guardar)"""
pass

def make_move(a, k, input_data):
"""Actualizar estructuras de datos (opcional)"""
pass

def unmake_move(a, k, input_data):
"""Deshacer cambios (opcional)"""
pass

Ejemplo: Generar subconjuntos de {1, 2, 3}

                        Nivel 0: []
                        /        \
                  incluir          excluir
                    /                  \
          Nivel 1: [1]                 []
                  /    \              /    \
        Nivel 2: [1,2]  [1]        [2]     []
                /   \   /  \      /  \    /  \
    Nivel 3: [1,2,3][1,2][1,3][1][2,3][2][3][]

Soluciones encontradas (hojas):
  {1,2,3}, {1,2}, {1,3}, {1}, {2,3}, {2}, {3}, {}

Complejidad: O(2^n) nodos, O(n) altura

class SubsetGenerator:
    def __init__(self, elements):
        self.elements = elements
        self.n = len(elements)
        self.solutions = []

    def generate_all_subsets(self):
        """Generar todos los subconjuntos"""
        a = [False] * self.n
        self.backtrack(a, 0)
        return self.solutions

    def backtrack(self, a, k):
        """Backtracking recursivo"""
        if self.is_a_solution(a, k):
            self.process_solution(a, k)
        else:
            candidates = self.construct_candidates(a, k)

            for candidate in candidates:
                a[k] = candidate
                self.backtrack(a, k + 1)

    def is_a_solution(self, a, k):
        """¿Hemos decidido sobre todos los elementos?"""
        return k == self.n

    def construct_candidates(self, a, k):
        """Candidatos: incluir (True) o excluir (False)"""
        return [True, False]

    def process_solution(self, a, k):
        """Construir y guardar el subconjunto"""
        subset = [self.elements[i] for i in range(self.n) if a[i]]
        self.solutions.append(subset)

# Ejemplo de uso
print("="*60)
print("GENERACIÓN DE SUBCONJUNTOS CON BACKTRACKING")
print("="*60 + "\n")

conjunto = [1, 2, 3]
generator = SubsetGenerator(conjunto)
subconjuntos = generator.generate_all_subsets()

print(f"Conjunto original: {conjunto}")
print(f"Número de subconjuntos: {len(subconjuntos)}")
print(f"\nTodos los subconjuntos:")

for i, subset in enumerate(subconjuntos, 1):
    print(f"  {i:2d}. {{{', '.join(map(str, subset))}}}") if subset else print(f"  {i:2d}. {{}}")

print("\n" + "="*60)
print("ANÁLISIS:")
print("="*60)
print(f"Elementos: n = {len(conjunto)}")
print(f"Subconjuntos: 2^n = 2^{len(conjunto)} = {2**len(conjunto)}")
print(f"Altura del árbol: {len(conjunto)}")
print(f"Factor de ramificación: 2 (incluir/excluir)")

class NQueens:
    def __init__(self, n):
        self.n = n
        self.solutions = []
        self.solution_count = 0
    
    def solve(self):
        """Resolver N-Reinas con backtracking"""
        a = [-1] * self.n  # a[i] = columna de la reina en fila i
        self.backtrack(a, 0)
        return self.solutions
    
    def backtrack(self, a, k):
        """Colocar reina en fila k"""
        if self.is_a_solution(a, k):
            self.process_solution(a, k)
        else:
            candidates = self.construct_candidates(a, k)
            
            for col in candidates:
                a[k] = col
                self.backtrack(a, k + 1)
    
    def is_a_solution(self, a, k):
        """¿Hemos colocado todas las reinas?"""
        return k == self.n
    
    def construct_candidates(self, a, k):
        """Columnas válidas para la reina en fila k"""
        candidates = []
        
        for col in range(self.n):
            if self.is_safe(a, k, col):
                candidates.append(col)
        
        return candidates
    
    def is_safe(self, a, row, col):
        """¿Es seguro colocar reina en (row, col)?"""
        # Verificar reinas anteriores
        for i in range(row):
            # Misma columna
            if a[i] == col:
                return False
            
            # Diagonal principal (\)
            if abs(row - i) == abs(col - a[i]):
                return False
        
        return True
    
    def process_solution(self, a, k):
        """Guardar solución"""
        self.solution_count += 1
        self.solutions.append(a[:])  # Copia
    
    def print_board(self, solution):
        """Visualizar tablero"""
        for row in range(self.n):
            line = ""
            for col in range(self.n):
                if solution[row] == col:
                    line += "♛ "
                else:
                    line += "· "
            print(line)

# Ejemplo de uso

print("="*60)
print("PROBLEMA DE LAS N-REINAS")
print("="*60 + "\n")

for n in [4, 5, 6, 8]:
queens = NQueens(n)
solutions = queens.solve()

    print(f"\n{n}-Reinas:")
    print(f"  Soluciones encontradas: {len(solutions)}")

    if n <= 6 and solutions:
        print(f"\n  Primera solución para {n}-Reinas:")
        queens.print_board(solutions[0])

print("\n" + "="*60)
print("COMPLEJIDAD:")
print("="*60)
print("""
Teórica (sin poda): O(n^n) - probar todas las posiciones
Con poda inteligente: O(n!) - mucho mejor

- Solo columnas válidas
- Verificación de diagonales

Número de soluciones para N-Reinas:
n=1: 1 n=5: 10 n=9: 352
n=2: 0 n=6: 4 n=10: 724
n=3: 0 n=7: 40 n=11: 2,680
n=4: 2 n=8: 92 n=12: 14,200
""")

class SudokuSolver:
    def __init__(self, board):
        """
        board: matriz 9x9 con 0 para celdas vacías
        """
        self.board = [row[:] for row in board]
        self.n = 9
        self.solutions = []

    def solve(self):
        """Resolver Sudoku con backtracking optimizado"""
        if self.backtrack():
            self.solutions.append([row[:] for row in self.board])
            return True
        return False

    def backtrack(self):
        """Backtracking con selección inteligente"""
        # Encontrar celda vacía con menos candidatos (MRV)
        cell = self.select_most_restricted_cell()

        if cell is None:
            # No hay celdas vacías → solución completa
            return True

        row, col = cell
        candidates = self.get_candidates(row, col)

        # Look ahead: si no hay candidatos, backtrack
        if not candidates:
            return False

        for digit in candidates:
            self.board[row][col] = digit

            # Look ahead: verificar que no bloqueamos otras celdas
            if self.look_ahead(row, col):
                if self.backtrack():
                    return True

            # Unmake move
            self.board[row][col] = 0

        return False

    def select_most_restricted_cell(self):
        """
        MRV (Minimum Remaining Values):
        Seleccionar celda vacía con menos candidatos
        """
        min_candidates = 10
        best_cell = None

        for i in range(self.n):
            for j in range(self.n):
                if self.board[i][j] == 0:
                    candidates = self.get_candidates(i, j)
                    num_candidates = len(candidates)

                    if num_candidates < min_candidates:
                        min_candidates = num_candidates
                        best_cell = (i, j)

                    # Si encontramos celda sin candidatos, retornar
                    if num_candidates == 0:
                        return best_cell

        return best_cell

    def get_candidates(self, row, col):
        """Obtener dígitos válidos para (row, col)"""
        if self.board[row][col] != 0:
            return []

        candidates = set(range(1, 10))

        # Eliminar dígitos en la fila
        candidates -= set(self.board[row])

        # Eliminar dígitos en la columna
        candidates -= set(self.board[i][col] for i in range(self.n))

        # Eliminar dígitos en el bloque 3x3
        block_row, block_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(block_row, block_row + 3):
            for j in range(block_col, block_col + 3):
                candidates.discard(self.board[i][j])

        return sorted(candidates)

    def look_ahead(self, row, col):
        """
        Verificar que la asignación actual no bloquea otras celdas
        Retorna False si alguna celda vacía queda sin candidatos
        """
        for i in range(self.n):
            for j in range(self.n):
                if self.board[i][j] == 0:
                    if len(self.get_candidates(i, j)) == 0:
                        return False
        return True

    def print_board(self):
        """Imprimir tablero formateado"""
        for i in range(self.n):
            if i % 3 == 0 and i != 0:
                print("-" * 21)

            line = ""
            for j in range(self.n):
                if j % 3 == 0 and j != 0:
                    line += "| "

                digit = self.board[i][j]
                line += str(digit) if digit != 0 else "."
                line += " "

            print(line)

# Ejemplo de uso
print("="*60)
print("SUDOKU SOLVER CON PODA INTELIGENTE")
print("="*60 + "\n")

# Sudoku difícil (requiere muchas decisiones)
sudoku_hard = [
    [0, 0, 0, 0, 0, 0, 6, 8, 0],
    [0, 0, 0, 0, 7, 3, 0, 0, 9],
    [3, 0, 9, 0, 0, 0, 0, 4, 5],
    [4, 9, 0, 0, 0, 0, 0, 0, 0],
    [8, 0, 3, 0, 5, 0, 9, 0, 2],
    [0, 0, 0, 0, 0, 0, 0, 3, 6],
    [9, 6, 0, 0, 0, 0, 3, 0, 8],
    [7, 0, 0, 6, 8, 0, 0, 0, 0],
    [0, 2, 8, 0, 0, 0, 0, 0, 0],
]

print("Tablero inicial:")
solver = SudokuSolver(sudoku_hard)
solver.print_board()

print("\n" + "="*60)
print("Resolviendo...")
print("="*60 + "\n")

import time
start = time.time()
solved = solver.solve()
elapsed = time.time() - start

if solved:
    print("✓ Solución encontrada!\n")
    solver.print_board()
    print(f"\nTiempo: {elapsed:.4f} segundos")
else:
    print("✗ No hay solución")

print("\n" + "="*60)
print("TÉCNICAS DE PODA APLICADAS:")
print("="*60)
print("""
1. MRV (Minimum Remaining Values):
  - Seleccionar celda con menos candidatos
  - Reduce factor de ramificación dramáticamente
  - Probabilidad de éxito: 50% con 2 candidatos vs 11% con 9

2. Look Ahead:
  - Verificar que otras celdas tengan candidatos
  - Detectar fallos temprano
  - Evita explorar ramas condenadas

3. Ordenamiento de Candidatos:
  - Probar valores más prometedores primero
  - Falla rápido si no hay solución

IMPACTO:
  Sin poda: ~1 hora
  Con poda: < 1 segundo
  Factor de mejora: > 1200x
""")

import heapq

class TSP_BranchAndBound:
def **init**(self, distances):
"""
distances: matriz de distancias entre ciudades
"""
self.distances = distances
self.n = len(distances)
self.best_cost = float('inf')
self.best_path = None
self.nodes_explored = 0

    def solve(self, start=0):
        """Resolver TSP con Branch and Bound"""
        # Cola de prioridad: (lower_bound, cost, path, visited)
        initial_state = (0, 0, [start], {start})
        pq = [initial_state]

        while pq:
            lb, cost, path, visited = heapq.heappop(pq)
            self.nodes_explored += 1

            # Poda: si el límite inferior ya es peor, ignorar
            if lb >= self.best_cost:
                continue

            # ¿Solución completa?
            if len(path) == self.n:
                # Agregar retorno al inicio
                total_cost = cost + self.distances[path[-1]][start]

                if total_cost < self.best_cost:
                    self.best_cost = total_cost
                    self.best_path = path + [start]

                continue

            # Expandir: agregar siguientes ciudades
            current = path[-1]

            for next_city in range(self.n):
                if next_city not in visited:
                    new_cost = cost + self.distances[current][next_city]
                    new_path = path + [next_city]
                    new_visited = visited | {next_city}

                    # Calcular límite inferior
                    new_lb = self.lower_bound(new_cost, new_visited)

                    # Solo agregar si es prometedor
                    if new_lb < self.best_cost:
                        heapq.heappush(pq, (new_lb, new_cost, new_path, new_visited))

        return self.best_path, self.best_cost

    def lower_bound(self, current_cost, visited):
        """
        Calcular límite inferior del costo total
        = costo actual + estimación de ciudades restantes
        """
        # Estimación simple: suma de aristas mínimas salientes
        # de ciudades no visitadas
        remaining_cost = 0
        unvisited = [i for i in range(self.n) if i not in visited]

        if not unvisited:
            return current_cost

        # Para cada ciudad no visitada, encontrar arista mínima
        for city in unvisited:
            min_edge = min(self.distances[city][j]
                          for j in range(self.n) if j != city)
            remaining_cost += min_edge

        return current_cost + remaining_cost

# Ejemplo de uso

print("="*60)
print("TSP CON BRANCH AND BOUND")
print("="*60 + "\n")

# Distancias entre 5 ciudades

distances = [
[0, 10, 15, 20, 25],
[10, 0, 35, 25, 30],
[15, 35, 0, 30, 20],
[20, 25, 30, 0, 15],
[25, 30, 20, 15, 0],
]

print("Matriz de distancias:")
print(" ", end="")
for i in range(len(distances)):
print(f" {i}", end="")
print()

for i, row in enumerate(distances):
print(f" {i}:", end="")
for dist in row:
print(f"{dist:3d}", end=" ")
print()

print("\n" + "="*60)
print("Resolviendo con Branch and Bound...")
print("="*60 + "\n")

solver = TSP_BranchAndBound(distances)
best_path, best_cost = solver.solve(start=0)

print(f"Mejor camino: {' → '.join(map(str, best_path))}")
print(f"Costo total: {best_cost}")
print(f"Nodos explorados: {solver.nodes_explored}")

print("\n" + "="*60)
print("COMPARACIÓN:")
print("="*60)
print(f"Backtracking (DFS): exploraría (n-1)! = {5*4*3*2*1} caminos")
print(f"Branch and Bound: exploró {solver.nodes_explored} nodos")
print(f"Reducción: {100\*(1 - solver.nodes_explored/120):.1f}%")

import heapq
import math

class AStar:
    def __init__(self, graph, coordinates):
        """
        graph: grafo ponderado {u: [(v, peso), ...]}
        coordinates: {u: (x, y)} para heurística de distancia
        """
        self.graph = graph
        self.coordinates = coordinates

    def heuristic(self, u, v):
        """
        Heurística: distancia euclidiana (as-the-crow-flies)
        Admisible porque la distancia real nunca es menor
        """
        x1, y1 = self.coordinates[u]
        x2, y2 = self.coordinates[v]
        return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

    def find_path(self, start, goal):
        """Encontrar camino más corto con A*"""
        # Cola de prioridad: (f_score, g_score, node, path)
        pq = [(0, 0, start, [start])]
        visited = set()
        nodes_explored = 0

        while pq:
            f, g, current, path = heapq.heappop(pq)
            nodes_explored += 1

            if current in visited:
                continue

            visited.add(current)

            # ¿Llegamos al objetivo?
            if current == goal:
                return path, g, nodes_explored

            # Expandir vecinos
            for neighbor, weight in self.graph.get(current, []):
                if neighbor not in visited:
                    new_g = g + weight
                    new_h = self.heuristic(neighbor, goal)
                    new_f = new_g + new_h
                    new_path = path + [neighbor]

                    heapq.heappush(pq, (new_f, new_g, neighbor, new_path))

        return None, float('inf'), nodes_explored

# Comparación: Dijkstra vs A*
class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def find_path(self, start, goal):
        """Dijkstra = A* con h(n) = 0"""
        pq = [(0, start, [start])]
        visited = set()
        nodes_explored = 0

        while pq:
            cost, current, path = heapq.heappop(pq)
            nodes_explored += 1

            if current in visited:
                continue

            visited.add(current)

            if current == goal:
                return path, cost, nodes_explored

            for neighbor, weight in self.graph.get(current, []):
                if neighbor not in visited:
                    new_cost = cost + weight
                    new_path = path + [neighbor]
                    heapq.heappush(pq, (new_cost, neighbor, new_path))

        return None, float('inf'), nodes_explored

# Ejemplo: Red de ciudades
print("="*60)
print("COMPARACIÓN: DIJKSTRA VS A*")
print("="*60 + "\n")

# Grafo de ciudades
graph = {
    'A': [('B', 5), ('C', 10)],
    'B': [('D', 3), ('E', 8)],
    'C': [('E', 2)],
    'D': [('F', 7)],
    'E': [('F', 1)],
    'F': [],
}

# Coordenadas para heurística
coordinates = {
    'A': (0, 0),
    'B': (3, 1),
    'C': (2, 4),
    'D': (6, 2),
    'E': (5, 5),
    'F': (9, 4),
}

print("Red de ciudades:")
for u, neighbors in graph.items():
    x, y = coordinates[u]
    print(f"  {u} ({x},{y}) → {neighbors}")

start, goal = 'A', 'F'

print(f"\nBuscar camino: {start} → {goal}")
print("\n" + "="*60)

# Dijkstra
dijkstra = Dijkstra(graph)
path_d, cost_d, nodes_d = dijkstra.find_path(start, goal)

print("DIJKSTRA:")
print(f"  Camino: {' → '.join(path_d)}")
print(f"  Costo: {cost_d}")
print(f"  Nodos explorados: {nodes_d}")

# A*
astar = AStar(graph, coordinates)
path_a, cost_a, nodes_a = astar.find_path(start, goal)

print("\nA* (con heurística euclidiana):")
print(f"  Camino: {' → '.join(path_a)}")
print(f"  Costo: {cost_a}")
print(f"  Nodos explorados: {nodes_a}")

print("\n" + "="*60)
print("ANÁLISIS:")
print("="*60)
print(f"Reducción de nodos: {nodes_d - nodes_a} menos")
print(f"Mejora: {100*(nodes_d - nodes_a)/nodes_d:.1f}%")
print("""
¿Por qué A* es mejor?
- Dijkstra expande como un disco uniforme
- A* dirige la búsqueda hacia el objetivo
- La heurística elimina direcciones inútiles
- Crucial para grafos grandes (mapas, GPS)
""")

import sys

def memory_analysis():
"""Analizar uso de memoria en búsqueda combinatoria"""

    print("="*60)
    print("ANÁLISIS DE MEMORIA: BACKTRACKING VS BRANCH AND BOUND")
    print("="*60 + "\n")

    # Tamaño típico de un nodo de búsqueda
    node_size_bytes = sys.getsizeof([]) + sys.getsizeof(0) * 15  # ~200 bytes

    print(f"Tamaño aproximado por nodo: {node_size_bytes} bytes\n")

    problems = [
        ("TSP n=10", 10, 10, 10),
        ("TSP n=15", 15, 15, 15),
        ("Subconjuntos n=20", 20, 20, 20),
        ("N-Reinas n=12", 12, 12, 12),
    ]

    print(f"{'Problema':<20} {'DFS (KB)':<15} {'BFS (MB)':<15} {'Diferencia':<15}")
    print("-" * 70)

    for name, height, branching, n in problems:
        # DFS: pila de altura h
        dfs_nodes = height
        dfs_memory = dfs_nodes * node_size_bytes / 1024  # KB

        # BFS/Branch and Bound: todos los nodos de nivel máximo
        # Aproximación: b^(h/2) en promedio
        bfs_nodes = branching ** (height // 2)
        bfs_memory = bfs_nodes * node_size_bytes / (1024 * 1024)  # MB

        if bfs_memory < 1:
            bfs_str = f"{bfs_memory * 1024:.1f} KB"
        else:
            bfs_str = f"{bfs_memory:.1f} MB"

        ratio = bfs_memory * 1024 / dfs_memory if dfs_memory > 0 else float('inf')

        print(f"{name:<20} {dfs_memory:.1f} KB{'':<8} {bfs_str:<15} {ratio:.0f}x")

    print("\n" + "="*60)
    print("CONCLUSIONES:")
    print("="*60)
    print("""

1. Backtracking (DFS):
  ✓ Memoria = O(altura) = muy manejable
  ✓ Puede explorar árboles enormes
  ✗ Puede explorar ramas malas completamente

2. Branch and Bound / A\*:
  ✓ Encuentra óptimo potencialmente más rápido
  ✓ Poda más agresiva con buenos límites
  ✗ Memoria = O(nodos generados) = exponencial
  ✗ Puede agotar RAM antes de terminar

3. Regla práctica:
  - Problemas pequeños (n < 15): Branch and Bound/A\*
  - Problemas grandes: Backtracking con poda inteligente
  - Muy grandes: Heurísticas aproximadas (no exactas)
    """)

memory_analysis()

"""
CHECKLIST PARA BÚSQUEDA COMBINATORIA EFICIENTE

1. MODELADO:
  ☐ Definir vector de solución a = (a₁, a₂, ..., aₙ)
  ☐ Definir conjuntos de candidatos Sᵢ para cada posición
  ☐ Definir criterio de solución completa

2. PODA (¡LO MÁS IMPORTANTE!):
  ☐ Verificar validez tempranamente
  ☐ Calcular límites inferiores/superiores
  ☐ Ordenar candidatos inteligentemente (MRV, etc.)
  ☐ Look-ahead: anticipar consecuencias
  ☐ Explotar simetrías

3. SELECCIÓN DE MÉTODO:
  ☐ ¿Cuántos nodos? (n < 15 → B&B, n > 15 → DFS)
  ☐ ¿Hay límite inferior? (sí → B&B, no → DFS)
  ☐ ¿Hay heurística? (sí → A*, no → B&B)
  ☐ ¿Restricción de memoria? (sí → DFS)

4. OPTIMIZACIÓN:
  ☐ Usar estructuras de datos eficientes
  ☐ Evitar copias innecesarias (make/unmake move)
  ☐ Implementar detección temprana de fallos
  ☐ Mantener estadísticas (nodos visitados)

5. TESTING:
  ☐ Probar con casos pequeños conocidos
  ☐ Verificar que encuentra todas las soluciones
  ☐ Medir nodos explorados con/sin poda
  ☐ Monitorear uso de memoria
"""