# Le backtracking explore un espace de solutions en construisant une solution partielle,
# et REVIENT EN ARRIÈRE (backtrack) dès qu'un choix s'avère invalide ou sous-optimal.

# --- Générer toutes les permutations d'un tableau ---
def permutations(tableau: list) -> list[list]:
    resultat = []

    def backtrack(courant: list, restants: list):
        if not restants:
            resultat.append(courant[:])   # copie -- "courant" continuera d'être modifié
            return
        for i in range(len(restants)):
            courant.append(restants[i])
            backtrack(courant, restants[:i] + restants[i + 1:])   # choisir
            courant.pop()                                          # défaire le choix (backtrack)

    backtrack([], tableau)
    return resultat

assert len(permutations([1, 2, 3])) == 6   # 3! = 6

# --- Générer tous les sous-ensembles (powerset) ---
def sous_ensembles(tableau: list) -> list[list]:
    resultat = []

    def backtrack(index: int, courant: list):
        resultat.append(courant[:])   # chaque état partiel EST une solution valide ici
        for i in range(index, len(tableau)):
            courant.append(tableau[i])
            backtrack(i + 1, courant)   # explorer avec cet élément inclus
            courant.pop()                # backtrack : l'exclure pour explorer l'autre branche

    backtrack(0, [])
    return resultat

assert len(sous_ensembles([1, 2, 3])) == 8   # 2^3 = 8

# --- Problème des N reines : placer N reines sur un échiquier N x N sans qu'aucune ne s'attaque ---
def n_reines(n: int) -> list[list[int]]:
    solutions = []
    colonnes_occupees = set()
    diagonales_montantes = set()    # (ligne - colonne) constant sur une diagonale
    diagonales_descendantes = set() # (ligne + colonne) constant sur l'autre diagonale

    def backtrack(ligne: int, positions: list[int]):
        if ligne == n:
            solutions.append(positions[:])
            return
        for colonne in range(n):
            if (colonne in colonnes_occupees
                    or (ligne - colonne) in diagonales_montantes
                    or (ligne + colonne) in diagonales_descendantes):
                continue   # élagage (pruning) : cette branche est invalide, on ne l'explore même pas

            # choisir
            colonnes_occupees.add(colonne)
            diagonales_montantes.add(ligne - colonne)
            diagonales_descendantes.add(ligne + colonne)
            positions.append(colonne)

            backtrack(ligne + 1, positions)

            # défaire (backtrack)
            colonnes_occupees.remove(colonne)
            diagonales_montantes.remove(ligne - colonne)
            diagonales_descendantes.remove(ligne + colonne)
            positions.pop()

    backtrack(0, [])
    return solutions

assert len(n_reines(4)) == 2   # 2 solutions distinctes pour un échiquier 4x4
assert len(n_reines(8)) == 92  # le résultat classique pour 8 reines

# --- Résolution de Sudoku par backtracking avec élagage ---
def resoudre_sudoku(grille: list[list[int]]) -> bool:
    def trouver_case_vide():
        for i in range(9):
            for j in range(9):
                if grille[i][j] == 0:
                    return i, j
        return None

    def valide(ligne: int, colonne: int, valeur: int) -> bool:
        if any(grille[ligne][c] == valeur for c in range(9)):
            return False
        if any(grille[l][colonne] == valeur for l in range(9)):
            return False
        bloc_ligne, bloc_colonne = 3 * (ligne // 3), 3 * (colonne // 3)
        for l in range(bloc_ligne, bloc_ligne + 3):
            for c in range(bloc_colonne, bloc_colonne + 3):
                if grille[l][c] == valeur:
                    return False
        return True

    case = trouver_case_vide()
    if case is None:
        return True   # plus de case vide -> grille résolue
    ligne, colonne = case

    for valeur in range(1, 10):
        if valide(ligne, colonne, valeur):
            grille[ligne][colonne] = valeur     # choisir
            if resoudre_sudoku(grille):
                return True
            grille[ligne][colonne] = 0           # backtrack : ce choix n'a pas mené à une solution

    return False

# --- Génération de combinaisons de parenthèses valides ---
def generer_parentheses(n: int) -> list[str]:
    resultat = []

    def backtrack(courant: str, ouvertes: int, fermees: int):
        if len(courant) == 2 * n:
            resultat.append(courant)
            return
        if ouvertes < n:
            backtrack(courant + "(", ouvertes + 1, fermees)
        if fermees < ouvertes:   # élagage : ne jamais fermer plus qu'on n'a ouvert
            backtrack(courant + ")", ouvertes, fermees + 1)

    backtrack("", 0, 0)
    return resultat

assert set(generer_parentheses(3)) == {"((()))", "(()())", "(())()", "()(())", "()()()"}