def encontrar_siguiente_vacio(tablero):
    """
    Busca la siguiente celda vacía (representada por 0) en el tablero.
    Retorna la tupla (fila, columna) si se encuentra, de lo contrario retorna None.
    """
    for r in range(9):
        for c in range(9):
            if tablero[r][c] == 0:
                return r, c  # Fila, columna
    return None

def es_valido(tablero, num, pos):
    """
    Verifica si colocar 'num' en la posición 'pos' (fila, columna) es una
    movida válida. Utiliza la lógica de sets internamente para la caja 3x3.
    """
    fila, col = pos

    # 1. Comprobar la fila (utiliza una comprobación de lista, pero internamente 
    # Python es eficiente)
    for c in range(9):
        if tablero[fila][c] == num:
            return False

    # 2. Comprobar la columna
    for r in range(9):
        if tablero[r][col] == num:
            return False

    # 3. Comprobar la caja 3x3 utilizando un Set para validación rápida
    inicio_fila_caja = fila // 3 * 3
    inicio_col_caja = col // 3 * 3

    # Crear un set con los números actuales en la caja 3x3
    numeros_en_caja = set()
    for r in range(inicio_fila_caja, inicio_fila_caja + 3):
        for c in range(inicio_col_caja, inicio_col_caja + 3):
            val = tablero[r][c]
            # Solo añadir números del 1 al 9, ignorando el 0
            if val != 0:
                numeros_en_caja.add(val)

    # Si el número ya está en el set, significa que es inválido.
    # Esta es una búsqueda O(1) en promedio, muy rápida.
    if num in numeros_en_caja:
        return False

    # Nota: No necesitamos el set si solo estamos verificando la posición 'pos', 
    # pero si quisiéramos verificar todo el tablero, el set es la herramienta ideal.
    # En este caso particular, el chequeo simple de la caja (como el código original)
    # es casi igual de rápido, pero el set es más explícito sobre la técnica.

    return True

def resolver_sudoku(tablero):
    """
    Función principal que resuelve el Sudoku utilizando backtracking.
    Retorna True si encuentra una solución, False si no hay solución.
    """
    siguiente_vacio = encontrar_siguiente_vacio(tablero)

    if not siguiente_vacio:
        return True

    fila, col = siguiente_vacio

    for num in range(1, 10):
        if es_valido(tablero, num, (fila, col)):
            tablero[fila][col] = num  # Colocamos el número

            if resolver_sudoku(tablero):
                return True # Éxito: encontramos la solución

            tablero[fila][col] = 0  # Backtrack: revertimos y probamos el siguiente

    return False # Falla: ningún número del 1 al 9 funciona

def imprimir_tablero(tablero):
    """
    Función para imprimir el tablero de Sudoku de forma legible.
    """
    print("-------------------------")
    for i in range(len(tablero)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - -")

        for j in range(len(tablero[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(tablero[i][j])
            else:
                print(str(tablero[i][j]) + " ", end="")
    print("-------------------------")

# --- Ejemplo de Uso ---

# El tablero es una lista de listas (la estructura de datos más común para matrices).
ejemplo_tablero = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

print("📝 Tablero Inicial:")
imprimir_tablero(ejemplo_tablero)

if resolver_sudoku(ejemplo_tablero):
    print("\n✅ Sudoku Resuelto:")
    imprimir_tablero(ejemplo_tablero)
else:
    print("\n❌ No se encontró solución para este Sudoku.")