Problème de traversée de rivière

Enoncé

Un Berger, un Loup, un Mouton, et un Choux doivent traverser une rivière.
Ils ont une barque à leur disposition mais elle n'a que deux places et seul le Berger sait ramer.
De plus celui-ci ne peut laisser sans surveillance les tandems Loup/Mouton et Mouton/Choux.
Comment doit-il organiser les traversées?

Création des types

Remarque par convention

• les constantes globales seront notées en majuscules. Par exemple: DEPART, ARRIVEE, SOMMETS, ARRETES.
• les classes commencent par une majuscule et on juxtapose plusieurs mots via les majuscules. Par exemple MaClasse.
• les autres variables et fonction sont en minuscule on juxtapose plusieurs mots via _ par exemple: ma_variable.

from enum import Enum, auto

class Cote(Enum):
    """Représente les deux côtés possibles de la rivière."""
    gauche = auto()
    droit = auto()

from dataclasses import dataclass

@dataclass(frozen=True)
class Etat:
    """Représente l'état potentiel du système avant application de la règle sur les tandems."""
    berger: Cote
    loup: Cote
    mouton: Cote
    choux: Cote

Arrete = tuple[Etat, Etat]

DEPART = Etat(
    berger=Cote.gauche, 
    mouton=Cote.gauche, 
    loup=Cote.gauche, 
    choux=Cote.gauche
)
DEPART

Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>)

ARRIVEE= Etat(
    berger=Cote.droit, 
    mouton=Cote.droit, 
    loup=Cote.droit, 
    choux=Cote.droit
)
ARRIVEE

Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)

Génération du graphe associé au système

Génération des sommets

def est_valide(etat: Etat) -> bool:
    """Décide si la règle du jeu est respectée."""
    if etat.berger != etat.loup and etat.loup == etat.mouton:
        return False
    if etat.berger != etat.mouton and etat.mouton == etat.choux:
        return False
    return True

# tests automatiques
assert est_valide(etat=DEPART)
assert est_valide(etat=ARRIVEE)
assert not est_valide(
    etat=Etat(
        berger=Cote.gauche,
        loup=Cote.droit,
        mouton=Cote.droit,
        choux=Cote.gauche
    )
)
assert not est_valide(
    etat=Etat(
        berger=Cote.gauche,
        loup=Cote.gauche,
        mouton=Cote.droit,
        choux=Cote.droit
    )
)

# création de tous les états possibles, 
# on aurait pu créer une fonction récursives pour éviter l'imbrication des boucles
etats: list[Etat] = list()
cotes = (Cote.gauche, Cote.droit)
for berger in cotes:
    for loup in cotes:
        for mouton in cotes:
            for choux in cotes:
                etats.append(
                    Etat(
                        berger=berger,
                        mouton=mouton,
                        loup=loup,
                        choux=choux
                    )
                )
etats

[Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)]

# création des sommets en vérifiant la règle des tandems
SOMMETS: list[Etat] = [etat for etat in etats if est_valide(etat)]
SOMMETS

[Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)]

Génération des arrêtes

def sont_connectes(etat1: Etat, etat2: Etat) -> bool:
    """Peut-on connecter les etats en une traversée."""
    if etat1.berger == etat2.berger:
        return False
    if etat1.loup != etat2.loup and etat1.mouton != etat2.mouton:
        return False
    if etat1.loup != etat2.loup and etat1.choux != etat2.choux:
        return False
    if etat1.choux != etat2.choux and etat1.mouton != etat2.mouton:
        return False
    return True

# test automatique
assert not sont_connectes(DEPART, ARRIVEE)

ARRETES: list[Arrete] = [
    (etat1, etat2) 
    for etat1 in SOMMETS 
    for etat2 in SOMMETS 
    if sont_connectes(etat1, etat2)
]
ARRETES

[(Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>)),
 (Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>))]

# Vérification automatique de la symétrie du graphe
for depart, arrivee in ARRETES:
    assert (arrivee, depart) in ARRETES

Exercice

Coder un fonction (récursive) permettant de résoudre le problème.

def genere_voisins(sommet: Etat, arretes: list[Arrete]) -> list[Etat]:
    """Renvoie la liste des voisins à partir de la liste des arrêtes du graphe."""
    resultat = list()
    for sommet1, sommet2 in arretes:
        if sommet == sommet1:
            resultat.append(sommet2)
        if sommet == sommet2:
            resultat.append(sommet1)
    return list(set(resultat))

def enleve(a_enlever: Etat, sommets: list[Etat]) -> list[Etat]:
    """Renvoie une liste de sommets sans l'état à enelever."""
    return  [sommet for sommet in sommets if sommet != a_enlever]

def ablation(a_enlever: Etat, arretes: list[Arrete]) -> list[Arrete]:
    """Retourne une liste d'arrêtes n'impliquant pas le sommet à enlever."""
    return [(sommet1, sommet2) for sommet1, sommet2 in arretes if a_enlever != sommet1 and a_enlever != sommet2]

def sont_relies(
        depart: Etat, 
        arrivee: Etat, 
        sommets: list[Etat],
        arretes: list[Arrete]
    ) -> bool:
    """Y a t il un chemin reliant les deux sommets?"""
    if depart == arrivee:
        return True
    for voisin in genere_voisins(sommet=depart, arretes=arretes):
        if sont_relies(
            depart=voisin,
            arrivee=arrivee,
            sommets=enleve(a_enlever=depart, sommets=sommets),
            arretes=ablation(a_enlever=depart, arretes=arretes)
        ):
            return True
    return False

sont_relies(depart=DEPART, arrivee=ARRIVEE, sommets=SOMMETS, arretes=ARRETES)

True

Exercice

Reprendre l'exercice avec une fonction calcule_chemin renvoyant un chemin connectant les deux sommets s'il existe.

Chemin = list[Etat]

def calcule_chemin(
        depart: Etat, 
        arrivee: Etat, 
        sommets: list[Etat],
        arretes: list[Arrete]
    ) -> Chemin:
    """Y a t il un chemin reliant les deux sommets?"""
    if depart == arrivee:
        return [arrivee]
    for voisin in genere_voisins(sommet=depart, arretes=arretes):
        if chemin := calcule_chemin(
            depart=voisin,
            arrivee=arrivee,
            sommets=enleve(a_enlever=depart, sommets=sommets),
            arretes=ablation(a_enlever=depart, arretes=arretes)
        ):
            chemin.insert(0, depart)
            return chemin
    return []

calcule_chemin(depart=DEPART, arrivee=ARRIVEE, sommets=SOMMETS, arretes=ARRETES)

[Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)]

Exercice

Reprendre l'exercice avec un graphe représenté par un dictionnaire d'adjacence. (mathématiquement une fonction qui à un sommet associe l'ensemble de ses voisins)

TableAdjacence = dict[Etat, list[Etat]]

ADJACENCE: TableAdjacence = {
    sommet: [voisin for voisin in SOMMETS if sont_connectes(etat1=sommet, etat2=voisin)]
    for sommet in SOMMETS
}
ADJACENCE

{Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>): [Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)],
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>): [Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)],
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>): [Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)],
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>): [Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)],
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>): [Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)],
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>): [Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)],
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>): [Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>)],
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>): [Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)],
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>): [Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
  Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>)],
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>): [Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>)]}

def ablation_v2(a_enlever: Etat, adjacence: TableAdjacence) -> TableAdjacence:
    return {
        sommet: [voisin for voisin in adjacence[sommet] if voisin != a_enlever]
        for sommet in adjacence
        if sommet != a_enlever
    }

def calcule_chemin_v2(depart: Etat, arrivee: Etat, adjacence: TableAdjacence) -> Chemin:
    if depart == arrivee:
        return [arrivee]
    for voisin in adjacence[depart]:
        if chemin := calcule_chemin_v2(
            depart=voisin, 
            arrivee=arrivee,
            adjacence=ablation_v2(a_enlever=depart, adjacence=adjacence),
        ):
            chemin.insert(0, depart)
            return chemin
        
    return []

calcule_chemin_v2(depart=DEPART, arrivee=ARRIVEE, adjacence=ADJACENCE)

[Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.gauche: 1>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.gauche: 1>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.gauche: 1>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.gauche: 1>, loup=<Cote.droit: 2>, mouton=<Cote.gauche: 1>, choux=<Cote.droit: 2>),
 Etat(berger=<Cote.droit: 2>, loup=<Cote.droit: 2>, mouton=<Cote.droit: 2>, choux=<Cote.droit: 2>)]