Les nouvelles technologies pour l’enseignement des mathématiques
Intégration des TICE dans l’enseignement des mathématiques

MathémaTICE, première revue en ligne destinée à promouvoir les TICE à travers l’enseignement des mathématiques.

Problèmes de traversée de rivière

Des problèmes connus des Carolingiens pour la plupart d’entre eux, se prêtent remarquablement bien à une analyse algorithmique, par les graphes ou en Python. Le niveau visé est NSI en Terminale.

Article mis en ligne le 7 juillet 2020
dernière modification le 1er août 2022

par Alain Busser

France Gall le chantait, c’est de l’époque de Charlemagne que date l’école. Mais si l’idée de fonder l’école peut être attribuée à l’empereur, celui qui a animé cette école est Alcuin. Pour lancer l’enseignement des mathématiques, il aurait rédigé le manuscrit propositiones ad acuendos juvenes, un ensemble de propositions (de problèmes) pour aiguiser l’esprit des écoliers. On y trouve beaucoup de problèmes de passage de rivière faisant allusion à la nécessité, fréquente au moyen-âge, d’utiliser un bac (bateau) pour traverser une rivière.

Alcuin %3 0 1 🍏 2 🐐🍏 1--2 3 🐐 3--0 3--2 7 🐺🐐 3--7 4 🐺 4--7 5 🐺🍏 5--1 5--4 6 🐺🐐🍏 5--6

En fait, en appelant « état » une configuration d’un de ces problèmes (par exemple la liste des personnages présents sur la rive droite), on est ramené à l’étude d’un automate fini, et ces problèmes sont très étudiés en informatique, et très utilisés dans l’enseignement de celle-ci.

Aucune licorne, aucune chèvre, aucun chameau, aucun chou ni aucune pomme n’ont été maltraités durant l’élaboration de cet article, aux contributeurs multiples, nombreux et variés.

Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International.

Calculer et autres compétences

Le parcours d’un graphe, si ce graphe représente un automate, est la suite des états (ou des changements d’état) de l’automate, et il est d’usage d’utiliser le mot calcul pour désigner ce parcours. Selon la théorie des automates finis, les problèmes de traversée de rivière reviennent à chercher un calcul. Pour autant, ce n’est pas la compétence calculer qui est évaluée ici.

En fait l’intérêt essentiel de ces problèmes est que la compétence calculer est pratiquement la seule qui ne soit pas mobilisée pour les résoudre ! Il reste

  • La compétence raisonner, mobilisée pour trouver « de tête » une solution (et espérer qu’elle soit optimale).
  • La compétence communiquer, utilisée pour verbaliser la solution qu’on croit avoir trouvée.
  • La compétence représenter, mobilisée par ceux qui veulent utiliser un graphe pour résoudre le problème.
  • Et surtout la compétence modéliser, surtout utilisée par ceux qui réussissent à programmer en Python le parcours du graphe : des questions comme « qu’est-ce que c’est qu’un état dans ce problème ? » viennent très rapidement à l’esprit du programmeur Python !

Le fait de ne pas mobiliser la compétence calculer libère en quelque sorte les autres compétences, de celle-ci, et permet de mieux les repérer. Par ailleurs, ce genre de problème peut intéresser plus les élèves ayant choisi NSI sans maths, certains d’entre eux ayant tendance à être déçus lorsqu’ils voient le niveau de maths requis en informatique...

Sous contraintes

Voici un problème bien plus moderne (XXe siècle) :

Il est intéressant parce que l’algorithme glouton ne s’y applique pas. Cet algorithme inciterait à faire passer d’abord les deux personnages les plus lents, ce qui prendrait du temps pour le retour de l’un d’eux avec la torche. Cependant le problème revêt un caractère nettement plus numérique que ceux décrits ci-dessous alors on ne va pas le traiter ici.

Régiment

Édouard Lucas, proche du milieu militaire, a généralisé ce problème (numéro 19) d’Alcuin :

XIX. PROPOSITIO DE VIRO ET MVLIERE PONDERANTIBVS [PLAVSTRI PONDVS ONVSTI].

De uiro et muliere, quorum uterque pondus habebat plaustri onusti, duos habentes infantes inter utrosque plaustrali pondere pensantes fluuium transire debuerunt. Nauem inuenerunt, quae non poterat ferre plus, nisi unum pondus plaustri. Transfretari faciat, qui se putat posse, ne nauis mergatur.

Dans ce problème, il s’agit de faire traverser la rivière à toute une famille, le bac ne permettant pas à plus d’un adulte (ou deux enfants) de traverser. On considère que chacun des deux enfants (des jumeaux comme on peut le voir ci-dessous) pèse exactement la moitié de l’un des parents (lesquels ont donc tous les deux la même masse corporelle).

~~ rive gauche ~~ ~~ rive droite ~~
👨👩👦👦

régiment

En appelant régiment le couple d’adultes ci-dessus, on retrouve le cas particulier n=2 du régiment de n soldats à faire passer sur l’autre rive avec un bac ne permettant de faire passer qu’un adulte ou deux enfants à la fois. On peut résoudre ce problème récursivement, avec cette solution pour n=1 d’abord :

  • Les deux enfants traversent seuls.
  • L’un des deux enfants revient seul.
  • L’adulte traverse.
  • Le second enfant revient.

Cette solution est emblématique de la programmation dynamique parce que le fait d’avoir résolu le problème dans un cas particulier simple, aide à le résoudre dans le cas général :

(état actuel : n+1 adultes et les deux enfants avec le bac sur la rive gauche)

  • Les deux enfants traversent seuls.
  • L’un des deux enfants revient seul.
  • Un adulte traverse.
  • Le second enfant revient.

(on est alors à l’état : n adultes avec les deux enfants et le bac sur la rive gauche). L’algorithme est donc récursif.

Loup, chèvre et chou

C’est le célébrissime problème 18 d’Alcuin :

XVIII. PROPOSITIO DE HOMINE ET CAPRA ET LVPO.

Homo quidam debebat ultra fluuium transferre lupum, capram, et fasciculum cauli. Et non potuit aliam nauem inuenire, nisi quae duos tantum ex ipsis ferre ualebat. Praeceptum itaque ei fuerat, ut omnia haec ultra illaesa omnino transferret. Dicat, qui potest, quomodo eis illaesis transire potuit ?

Pour homogénéiser les dessins ci-dessous, le chou (cauli) a été remplacé par une pomme, qui présente de plus l’avantage de ne pas avoir la même initiale que la chèvre.

~~ rive gauche ~~~~ rive droite ~~
🐺🐐🍏🚣

L'état actuel du jeu est (0,0,0,0).

Solution géométrique

En représentant la rive gauche par l’équation x=0 et la rive droite par l’équation x=1, chaque état possible est un point de l’espace de dimension 4 (dans l’ordre, les abscisses du loup, de la chèvre, de la pomme et du bateau). Les coordonnées de ces points valant 0 ou 1, ces points sont les sommets d’un tesseract. Mais le graphe n’est pas celui du tesseract. Par exemple, dans un tesseract, il y a une arête entre les sommets (0,0,0,0) et (1,0,0,0). Dans le cas présent cette arête représenterait la traversée de la rivière par le loup sans utiliser le bateau. Pour avoir des arêtes du tesseract, il faut échanger la quatrième coordonnée d’un sommet sur deux, comme le montrent les couleurs ci-dessous (source : wikipedia) :

Sur les sommets blancs, la 4e coordonnée représente l’abscisse t du bateau, sur les sommets colorés, la 4e coordonnée représente 1-t. Il peut maintenant y avoir une arête reliant les points (0,0,0,0) et (1,0,0,1) car ces points ne sont pas de la même couleur (les coordonnées de l’état (1,0,0,1) étant représentées par le point (1,0,0,0) puisque ce point est colorié).

Parmi les 16 sommets du tesseract, certains sont impossibles, ils correspondent aux états suivants :

  • (0,0,0,1) (le batelier a laissé le loup, la chèvre et la pomme sans surveillance)
  • (1,1,1,0) (idem mais en inversant les rives occupées)
  • (0,0,1,1) (le loup et la chèvre sont seuls sur la rive gauche).
  • (1,1,0,0) (idem mais sur la rive droite)
  • (1,0,0,1) (la chèvre et la pomme sont seules sur la rive gauche)
  • (0,1,1,0) (idem, sur la rive droite).

En enlevant ces 6 sommets (et les arêtes adjacentes à ceux-ci) on obtient un graphe simplifié à 10 sommets. Résoudre le problème revient alors à parcourir ce graphe, ce qui est facile une fois le graphe tracé (il a la forme d’une molécule de para-diéthylbenzène).

Le graphe, étiqueté par les personnages qui traversent, est celui des états d’un automate fini. On peut effectuer des parcours de ce graphe en Python.

Une solution Python

Une solution sera modélisée par une liste d’entiers, selon la représentation suivante :

  • L’entier 0 représente la traversée du loup (accompagné automatiquement du batelier).
  • L’entier 1 représente la traversée de la chèvre (accompagnée automatiquement par le batelier).
  • L’entier 2 représente la traversée du chou (et du batelier).
  • L’entier 3 représente la traversée du batelier seul.

Voici une fonction qui transforme ces entiers en leurs hiéroglyphes (ou plutôt, une liste d’entiers, en une chaîne de caractères) :

  1. def mot(t):    
  2.         p = chr(128058)+chr(128016)+chr(127823)+chr(128675)
  3.         return ' '.join([p[k] for k in t])

Télécharger

Comment construire toutes les listes d’entiers égaux à 0, 1, 2 ou 3 ? En fait ces entiers sont des chiffres en base 4. On peut donc construire une liste d’entiers à partir d’un entier, en écrivant celui-ci en base 4 puis en convertissant chaque chiffre (un caractère) en entier. Pour cela on a besoin d’une fonction Python de conversion en base 4. En voici une récursive [1] :

  1. def quater(n):
  2.         if n<4:
  3.                 return str(n)
  4.         else:
  5.                 return quater(n//4)+str(n%4)

Télécharger

Pour implémenter les arêtes du graphe (ou les changements d’état de l’automate), on va créer une fonction qui, à un état state et un personnage quidam, associe

  • soit le même état state si le quidam ne peut pas traverser depuis l’état state,
  • soit le nouvel état s (obtenu à partir de l’état state après que quidam a traversé).

Pour ce faire on crée un futur état en copiant state, puis on effectue le changement d’état sur ce nouvel état (pour garder l’ancien état au cas où le changement d’état ne serait pas possible). Pour effectuer le changement d’état,

  • Si quidam n’est pas le bateau, on le fait traverser en modifiant la coordonnée de numéro quidam de l’état.
  • Dans tous les cas, le batelier traverse aussi.

Ensuite,

  • si quidam n’est pas le bateau et que le bateau et quidam ne sont pas du même côté de la rivière, c’est que le quidam a traversé à la nage. On signale alors une erreur de type (traverser sans le bateau c’est un peu comme essayer d’additionner un nombre avec du texte) ;
  • si le loup et la chèvre sont sur une même rive et que le bateau n’est pas du même côté, on signale là aussi une erreur de type (les types loup et chèvre étant en quelque sorte incompatibles) ;
  • si la chèvre et la pomme sont du même côté qui n’est pas celui du bateau, là encore une erreur de type (incompatibilité entre la chèvre et la pomme) ;
  • Si tout le monde est à droite on signale non pas une erreur mais une exception StopIteration disant que le problème est résolu.
  • Dans tous les autres cas on renvoie le nouvel état puisque la traversée a réussi.

Cette fonction se code ainsi en Python :

  1. def next(state,quidam):
  2.         s = state.copy()
  3.         if quidam<3:
  4.                 s[quidam] = 1-s[quidam]
  5.         s[3] = 1-s[3]
  6.         if quidam<3 and s[quidam]!=s[3]:
  7.                 raise TypeError()
  8.         if (s[0]==s[1]!=s[3]) or (s[1]==s[2]!=s[3]):
  9.                 raise TypeError()
  10.         if s==[1,1,1,1]:
  11.                 raise StopIteration()
  12.         return s

Télécharger

Pour résoudre le problème du loup, de la chèvre et de la pomme, on peut alors faire ainsi :

  • on boucle sur les numéros numtrajet des trajets possibles dans le graphe (par ordre croissant) ;
  • pour chacun de ces numéros, on le convertit en liste d’entiers (transitions possibles) à partir de son écriture en base 4 ;
  • on initialise l’état à [0,0,0,0] ;
  • pour chaque transition, on essaye de changer l’état jusqu’à la survenue d’une exception ;
  • en cas de StopIteration on affiche la suite des transitions (convertie en mot) parce que celle-ci est une solution au problème.

En allant jusqu’à 10000 on obtient ce script :

  1. for numtrajet in range(10000):
  2.         transitions = [int(k) for k in quater(numtrajet)]
  3.         etat = [0,0,0,0]
  4.         for t in transitions:
  5.                 try:
  6.                         etat = next(etat,t)
  7.                 except TypeError:
  8.                         break
  9.                 except StopIteration:
  10.                         print(mot(transitions))
  11.                         break

Télécharger

qui affiche ces deux solutions :

  • 🐐 🚣 🐺 🐐 🍏 🚣 🐐
  • 🐐 🚣 🍏 🐐 🐺 🚣 🐐

Une solution Cubicle

Le logiciel libre Cubicle, développé par Alain Mebsout et Sylvain Conchon, fait de la vérification de modèles : il cherche si un état dangereux (« unsafe ») peut être atteint lors de l’évolution d’un système. Il peut donc servir à résoudre le problème du loup, de la chèvre et de la pomme, en considérant que l’état souhaité (tout le monde sur la rive droite) est dangereux. On utilise des variables booléennes, précisant si le loup est à droite, si la chèvre est à droite, si la pomme est à droite et si le bateau est à droite. Une autre variable booléenne V sert à forcer au moment adéquat la transition no_problemo qui ne fait que vérifier qu’il n’y a pas de problème (et n’est donc pas une vraie transition puisque personne ne traverse).

  1. var Loup_droite : bool
  2. var Chevre_droite : bool
  3. var Pomme_droite : bool
  4. var Bateau_droite : bool
  5. var V : bool (* feu vert pour le bateau *)

Télécharger

L’état initial est décrit par ces variables toutes égales à False (personne n’est sur la rive droite puisque tout le monde est sur la rive gauche) :

init() { Loup_droite=False && Chevre_droite=False && Pomme_droite=False && Bateau_droite=False }

L’état final (« unsafe » donc) est le contraire : tout le monde est sur la rive droite :

unsafe() { Loup_droite=True && Chevre_droite=True && Pomme_droite=True && Bateau_droite=True }

Cubicle va essayer de voir si l’état final unsafe peut être atteint à partir de l’état initial. Pour cela, il faut préciser les transitions permettant de passer d’un état à un autre. Il y a déjà les 4 traversées des protagonistes. Par exemple le loup traverse s’il est du même côté que le bateau (prérequis à la traversée : le loup ne sait pas nager) et si la traversée est autorisée (V), et la traversée a pour effet de modifier les propositions « le loup est sur la rive droite » et « le bateau est sur la rive droite » :

  1. transition le_loup_traverse ()
  2. requires { Loup_droite=Bateau_droite && V=True }
  3. {
  4. Loup_droite := case
  5.                 | Loup_droite=True : False
  6.                 | _ : True;
  7. (* le bateau traverse avec le loup *)
  8. Bateau_droite := case
  9.                 | Bateau_droite=True : False
  10.                 | _ : True;
  11. V := False;
  12. }

Télécharger

Une fois la traversée effectuée, V est positionnée à False pour empêcher tout autre changement d’état avant de vérifier que tout est OK. Les traversées de la chèvre et de la pomme sont similaires, et celle du bateau est plus simple puisqu’il traverse alors seul :

  1. transition le_bateau_traverse ()
  2. requires { V = True }
  3. {
  4. Bateau_droite := case
  5.                 | Bateau_droite=True : False
  6.                 | _ : True;
  7. V := False;
  8. }

Télécharger

Pour vérifier que tout va bien, on ajoute une fausse transition no_problemo qui n’est activée que si V est niée (donc après chaque vraie traversée) et dont le prérequis est constitué de deux implications :

  • Si le loup est du même côté que la chèvre alors le bateau doit aussi être de ce côté.
  • Si la pomme est du même côté que la chèvre alors le bateau doit aussi être de ce côté.

Une fois la vérification faite, la variable V est simplement repositionnée à True afin de permettre de tester d’autres traversées :

  1. transition no_problemo ()
  2. requires { V=False  
  3.         && (Loup_droite=Chevre_droite => Bateau_droite=Chevre_droite)
  4.         && (Pomme_droite=Chevre_droite => Bateau_droite=Chevre_droite) }
  5. { V := True }

Télécharger

Voici l’intégralité du programme Cubicle :

  1. var Loup_droite : bool
  2. var Chevre_droite : bool
  3. var Pomme_droite : bool
  4. var Bateau_droite : bool
  5. var V : bool (* feu vert pour le bateau *)
  6.  
  7. init() { Loup_droite=False && Chevre_droite=False && Pomme_droite=False && Bateau_droite=False }
  8.  
  9. unsafe() { Loup_droite=True && Chevre_droite=True && Pomme_droite=True && Bateau_droite=True }
  10.  
  11.  
  12.  
  13. transition le_loup_traverse ()
  14. requires { Loup_droite=Bateau_droite && V=True }
  15. {
  16. Loup_droite := case
  17.                 | Loup_droite=True : False
  18.                 | _ : True;
  19. (* le bateau traverse avec le loup *)
  20. Bateau_droite := case
  21.                 | Bateau_droite=True : False
  22.                 | _ : True;
  23. V := False;
  24. }
  25.  
  26. transition la_chevre_traverse ()
  27. requires { Chevre_droite=Bateau_droite && V=True }
  28. {
  29. Chevre_droite := case
  30.                 | Chevre_droite=True : False
  31.                 | _ : True;
  32. (* le bateau traverse avec la chevre *)
  33. Bateau_droite := case
  34.                 | Bateau_droite=True : False
  35.                 | _ : True;
  36. V := False;
  37. }
  38.  
  39. transition la_pomme_traverse ()
  40. requires { Pomme_droite=Bateau_droite && V=True }
  41. {
  42. Pomme_droite := case
  43.                 | Pomme_droite=True : False
  44.                 | _ : True;
  45. (* le bateau traverse avec la pomme *)
  46. Bateau_droite := case
  47.                 | Bateau_droite=True : False
  48.                 | _ : True;
  49. V := False;
  50. }
  51.  
  52. transition le_bateau_traverse ()
  53. requires { V = True }
  54. {
  55. Bateau_droite := case
  56.                 | Bateau_droite=True : False
  57.                 | _ : True;
  58. V := False;
  59. }
  60.  
  61.  
  62. transition no_problemo ()
  63. requires { V=False  
  64.         && (Loup_droite=Chevre_droite => Bateau_droite=Chevre_droite)
  65.         && (Pomme_droite=Chevre_droite => Bateau_droite=Chevre_droite) }
  66. { V := True }

Télécharger

En enregistrant ce fichier sous le nom loup.cub, on résout le problème avec la commande

./cubicle -dot 2  loup.cub

ce qui donne, d’une part l’affichage dans la console, de ce corrigé :

Unsafe trace: la_chevre_traverse() -> no_problemo() ->
              le_bateau_traverse() -> no_problemo() ->
              la_pomme_traverse() -> no_problemo() ->
              la_chevre_traverse() -> no_problemo() -> le_loup_traverse() ->
              no_problemo() -> le_bateau_traverse() -> no_problemo() ->
              la_chevre_traverse() -> unsafe[1]

et d’autre part, le dessin de la solution comme parcours de cet arbre :

Voici, au format pdf, une version plus détaillée, avec affichage des valeurs des variables à chacun des états :

Parcours en profondeur

Résoudre ce problème, c’est trouver un chemin dans un graphe. Cela peut se faire notamment par un algorithme de parcours en profondeur, qu’Édouard Lucas a attribué à « Monsieur Trémeaux, ancien élève de l’École Polytechnique, ingénieur des télégraphes », dans ses récréations mathématiques, au chapitre sur les labyrinthes. En effet, sortir d’un labyrinthe, c’est aussi trouver un chemin dans un graphe.

Sébastien Hoarau a lui aussi opté pour un parcours du graphe en profondeur. Comme le parcours en profondeur utilise une structure de type LIFO (ou pile (informatique), au programme de NSI en Terminale), la solution de Sébastien Hoarau peut être exposée tôt dans l’année scolaire, les progressions choisies plaçant en général les piles vers le début de l’année scolaire.

Voici la solution de Sébastien Hoarau :

  1. GAUCHE = 0
  2. DROITE = 1
  3.  
  4. LOUP = 0
  5. CHEVRE = 1
  6. CHOU = 2
  7. PASSEUR = 3
  8. PROTAGONISTES = (LOUP, CHEVRE, CHOU, PASSEUR)
  9.  
  10. DESSINS = (chr(128058), chr(128016), chr(129388), chr(128578))
  11.  
  12. class Passeur():
  13.     """Le passeur mémorise des états des rives gauche et droite
  14.    et simule des traversées : quand l'état courant ie le dernier
  15.    de la mémoire est égal à l'état final on stoppe et on affiche
  16.    
  17.    un état est représenté par une liste de 4 valeurs 0 ou 1...
  18.    chaque valeur correspond à un des protagonistes"""
  19.     def __init__(self):
  20.         self.suivant = None
  21.         self.memoire = [[GAUCHE] * len(PROTAGONISTES)]
  22.         self.etat = self.memoire[-1]
  23.  
  24.  
  25.     def affiche_solution(self):
  26.         for config in self.memoire:
  27.             rives = ['', '']
  28.             for protagoniste in PROTAGONISTES:
  29.                 rives[config[protagoniste]] += DESSINS[protagoniste]
  30.             print(rives[GAUCHE] + ' ~~~~~~~~~ ' + rives[DROITE])
  31.        
  32.     def fini(self):
  33.         return self.etat == [DROITE] * len(PROTAGONISTES)
  34.    
  35.     def memorise(self):
  36.         self.memoire.append(self.suivant.copy())
  37.         self.etat = self.memoire[-1]
  38.  
  39.     def oublie(self):
  40.         self.memoire.pop()
  41.         self.etat = self.memoire[-1]
  42.        
  43.     def deja_vu(self):
  44.         return self.suivant in self.memoire
  45.    
  46.     def danger(self):
  47.         """l'état suivant est dangeureux si le loup et la chèvre sont
  48.        sur la même rive, sans le passeur ou alors la chèvre et le chou"""
  49.         loup_mange_chevre = self.suivant[CHEVRE] == self.suivant[LOUP] and self.suivant[LOUP] != self.suivant[PASSEUR]
  50.         chevre_mange_chou = self.suivant[CHEVRE] == self.suivant[CHOU] and self.suivant[CHEVRE] != self.suivant[PASSEUR]
  51.         return loup_mange_chevre or chevre_mange_chou
  52.    
  53.     def traverse(self, protagoniste):
  54.         """Faire traverser le protagoniste ie faire une copie de
  55.        l'état courant puis changer la valeur pour le protagoniste
  56.        si ce dernier n'est pas le passeur il faut aussi faire
  57.        traverser le passeur"""
  58.         self.suivant = self.etat.copy()
  59.         self.suivant[protagoniste] = 1 - self.suivant[protagoniste]
  60.         if protagoniste != PASSEUR:
  61.             self.suivant[PASSEUR] = 1 - self.suivant[PASSEUR]
  62.        
  63.     def resoud(self):
  64.         if self.fini():
  65.             return True
  66.         else:
  67.             for protagoniste in PROTAGONISTES:
  68.                 self.traverse(protagoniste)
  69.                 if not self.danger() and not self.deja_vu():
  70.                     self.memorise()
  71.                     if self.resoud():
  72.                         return True
  73.                     else:
  74.                         self.oublie()
  75.             return False
  76.                
  77. seb = Passeur()
  78. if seb.resoud():
  79.     seb.affiche_solution()
  80. else:
  81.     print('Pas de solution')

Télécharger

Chaque état est représenté par une liste de nombres égaux à 0 ou à 1 (autrement, un nombre entre 0 et 15, écrit en binaire). La méthode __init__ met ces 4 nombres à 0 puisqu’au début tout le monde est sur la rive gauche. La méthode d’affichage représente cette liste, en séparant les rives par une série de « tildes » représentant les vagues de la rivière. La méthode fini vérifie si l’état final est atteint.

Les méthodes memorise, oublie et deja_vu gèrent la pile (modèle de mémoire de travail du passeur) :

  • memorise place l’état suivant au sommet de la pile, et effectue la transition en faisant en sorte que l’état suivant devienne l’état actuel ;
  • oublie fait un peu l’inverse : l’état du sommet de la pile est éjecté d’icelle (oublié) et l’état précédent devient l’état actuel ;
  • deja_vu vérifie si l’état en cours d’examen est déjà dans la pile (autrement, mémorisé et pas oublié)

La méthode danger vérifie si le loup peut manger la chèvre ou si la chèvre peut manger le chou (absence du passeur pour empêcher le massacre), sous forme d’expressions booléennes, et renvoie la disjonction de ces conditions ; la méthode traverse effectue le changement d’état, en modifiant les abscisses de ceux qui ont effectué la traversée, et la méthode resoud construit une solution récursivement, par l’algorithme de Trémeaux.

On constate que toutes ces fonctions sont définies comme des méthodes d’un objet seb appartenant à la classe Passeur : c’est le passeur qui mémorise les états explorés et qui résout le problème (en plus de ramer, accompagné par un loup, une chèvre ou un chou). L’exécution du script donne cet affichage :

  • 🐺🐐🥬🙂 _________
  • 🐺🥬_________ 🐐🙂
  • 🐺🥬🙂 _________ 🐐
  • 🥬 _________ 🐺🐐🙂
  • 🐐🥬🙂 _________ 🐺
  • 🐐 _________ 🐺🥬🙂
  • 🐐🙂 _________ 🐺🥬
  • _________ 🐺🐐🥬🙂

Unicode étant très pratiqué en Asie, le teint de Sébastien vire un peu au jaune (que l’on se rassure sur son état de santé, il sature bien en oxygène) et le chou est dessiné comme un pe-tsaï, très fréquent d’usage à La Réunion. Du moins lorsque le navigateur accepte de dessiner ce caractère...

Maris jaloux

C’est le problème 17 d’Alcuin :

XVII. PROPOSITIO DE TRIBVS FRATRIBVS SINGVLAS HABENTIBVS SORORES.

Tres fratres erant, qui singulas sorores habebant, et fluuium transire debebant. (Erat enim unicuique illorum concupiscientia in sorore proximi sui) qui uenientes ad fluuium non inuenerunt, nisi paruam nauiculam, in qua non potuerunt amplius nisi duo ex illis transire. Dicat, qui potest, qualiter fluuium transierunt, ne una quidem earum ex ipsis maculata sit ?

En 1612, Claude-Gaspard Bachet de Méziriac a traduit en français ce problème, dans ses problèmes plaisans et délectables :

Trois maris jaloux se trouvent de nuit avec leurs femmes au passage d’une rivière où ils ne rencontrent qu’un petit bateau sans batelier, si étroit qu’il n’est capable que de deux personnes, on demande comment ces six personnes passeront deux à deux, tellement que jamais aucune femme ne demeure en compagnie d’un ou de deux hommes si son mari n’est pas là.

C’est la version de Bachet qui est citée par Édouard Lucas qui devine une analogie entre ce problème, et le jeu du baguenaudier à 3 anneaux :

Dans ce texte, Édouard Lucas évoque une intéressante généralisation [2] : que se passe-t-il s’il y a plus de 3 couples à faire traverser ? Et si le bateau permettait de transporter plus de 2 personnes à la fois ? Lucas propose ce problème d’allure plus numérique que les précédents :

Des maris en nombre quelconque n se trouvent avec leurs femmes au passage d’une rivière ; quel doit être le plus petit nombre x de personnes qu’un bateau peut au plus contenir, pour effectuer la traversée, avec un batelier, avec la condition qu’aucune femme ne demeure dans le bateau ou sur l’une des rives en compagnie d’un ou plusieurs hommes, si son mari n’est présent.

Cette généralisation en a inspiré d’autres durant le XXe siècle. On va en voir une dans l’onglet suivant.

Cannibales et missionnaires

Ce problème, qui n’est pas d’Alcuin, peut être considéré comme une simplification du précédent, ou plutôt une généralisation : si, à un moment, il y a plus de femmes que d’hommes sur une rive, l’une des femmes serait en compagnie d’autres hommes que son mari et la solution proposée par Bachet au problème ci-dessus est donc a fortiori aussi solution du problème suivant (où on met des dragons à la place des femmes et des licornes à la place des hommes, l’allégorie des cannibales et des missionnaires étant inutilement violente de nos jours). Trois 🐉 et trois 🦄 doivent traverser la rivière avec un bac ne permettant au maximum que le passage de deux d’entre eux à la fois, avec la contrainte que sur aucune rive, à aucun moment, les licornes soient moins nombreuses que les dragons ce qui les mettrait en danger :

~~ rive gauche ~~ ~~ rive droite ~~
🐉🐉🐉
🦄🦄🦄

L'état actuel du jeu est (3,3,1).

Système d’addition de vecteurs

Comme on le voit, et bien qu’il y ait plus de protagonistes que dans le problème du loup, de la chèvre et du chou, un état est un point de l’espace de dimension 3. La solution correspond donc à un parcours dans ce graphe en 3D :

Comme les arcs de ce graphe sont des vecteurs, le problème est géométrique et consiste en un système d’addition de vecteurs avec états [3]. Plus précisément, comme pour le loup, la chèvre et le chou, on va tenir compte de la parité du nombre de mouvements, et

  • additionner un vecteur de la forme (l,d,1) à l’état courant si le bateau va de la rive gauche (état (x,y,0) puisque le bateau est à gauche) vers la rive droite (ce qui amène l licornes de plus et d dragons de plus à droite) ;
  • soustraire un vecteur de la forme (l,d,1) à l’état courant si le bateau revient vers la rive gauche (ce qui enlève l licornes et d dragons de la rive droite pour les ramener à gauche, ainsi d’ailleurs que le bateau).

Recherche par force brute

Voici une recherche exhaustive en Python s’inspirant de celle du problème « loup, chèvre, chou » vue auparavant :

L’affichage d’une transition représente la barque (deux flèches indiquant le sens de déplacement de celle-ci) et son équipage. Une transition est la donnée du nombre l de licornes qui traversent, du nombre d de dragons qui traversent, et du sens s de traversée :

  1. def mot(t):    
  2.         l,d,s = t
  3.         fleches = "←→"
  4.         return fleches[s]+l*chr(129412)+d*chr(128009)+fleches[s]

Télécharger

Une variable globale donne, pour chaque chiffre en base 5 du trajet essayé, le nombre de licornes et le nombre de dragons qui traversent :

  1. couples = [(1,1),(1,0),(2,0),(0,2),(0,1)]

On remarque que cette partie du problème a été résolue sans passer par Python : ces 5 couples sont les seuls respectant les contraintes

  • au moins un personnage dans le bateau (il ne traverse pas tout seul)
  • pas plus de 2 personnages à la fois dans le bateau (capacité C du bateau limitée à 2)
  • pas plus de dragons que de licornes dans le bateau

Il aurait été possible, en exercice préliminaire, de créer un script Python retrouvant les 5 couples d’entiers ci-dessus.

Comme il y a 5 transitions possibles, on a besoin d’une fonction de conversion en base 5 :

  1. def quinary(n):
  2.         if n<5:
  3.                 return str(n)
  4.         else:
  5.                 return quinary(n//5)+str(n%5)  

Télécharger

Le prochain état next dépend de l’état actuel state et de la transition radeau faisant passer d’un état à l’autre. En notant l, d et s les valeurs actuelles des variables de même nom (nombre de licornes sur la rive gauche, nombre de dragons sur la rive gauche et sens de déplacement du radeau), les valeurs après la traversée sont notées l2, d2 et s2. Comme la barque ne fait que des allers-retours, s2 est égal à 1-s. L’expression 1-2s vaut 1 ou -1 et a pour effet de déterminer si c’est une addition ou une soustraction qu’il faut effectuer (une traversée vers la droite fait diminuer le nombre de licornes ou de dragons sur la rive gauche, une traversée vers la gauche ramène du monde).

  • La ligne 6 rappelle qu’à tout instant, les nombres de licornes et de dragons sur les deux rives doivent être positifs ou nuls.
  • La ligne 8 rappelle que le seul moyen qu’il y ait plus de dragons que de licornes sur la rive gauche, est qu’il n’y ait pas du tout de licornes sur la rive gauche.
  • La ligne 10 rappelle que le seul moyen qu’il y ait plus dragons que de licornes sur la rive droite, est qu’il n’y ait pas du tout de licornes sur la rive droite.
  • Si ne serait-ce qu’une seule de ces conditions n’est pas respectée, la traversée est considérée comme impossible et l’ancien état est renvoyé par la fonction. La ligne 12 est celle qui n’est exécutée que si la transition est possible : elle renvoie le nouvel état (en réalité un triplet, Python rajoute les parenthèses sans qu’on ait à le lui dire) :
  1. def next(state,radeau):
  2.         l,d,s = state
  3.         l2 = l+radeau[0]*(1-2*s)
  4.         d2 = d+radeau[1]*(1-2*s)
  5.         s2 = 1-s
  6.         if l2<0 or d2<0 or l2>3 or d2>3:
  7.                 return state
  8.         if l2>0 and d2>l2:
  9.                 return state
  10.         if l2<3 and d2<l2:
  11.                 return state
  12.         return l2,d2,s2

Télécharger

Pour chercher une solution à ce problème, il faut donc

  • parcourir en largeur d’abord, l’arbre des possibilités, avec la conversion en base 5 ;
  • pour chaque trajet possible, fabriquer les transitions sous forme d’une liste de triplets (l,d,s)
  • initialiser l’état à 3 licornes, 3 dragons et une barque sur la rive gauche
  • pour chacune des transitions, tenter de calculer le nouvel état (effectuer la transition)
  • si à la fin, il n’y a plus ni licornes ni dragons sur la rive gauche, l’état final est atteint et on affiche la solution qui est la suite des transitions :
  1. for n in range(100000000):
  2.         ld = [couples[int(k)] for k in quinary(n)]
  3.         transitions = [(ld[k][0],ld[k][1],(k+1)%2) for k in range(len(ld))]
  4.         etat = (3,3,1)
  5.         for t in transitions:
  6.                 etat = next(etat,t)
  7.         if etat==(0,0,0) or etat==(0,0,1):
  8.                 print([mot(t) for t in transitions])

Télécharger

C’est très long : il faut des dizaines de millions d’itérations avant d’arriver à ces solutions :

  • [’→🐉🐉→’, ’←🐉←’, ’→🐉🐉→’, ’←🐉←’, ’→🦄🦄→’, ’←🦄🐉←’, ’→🦄🦄→’, ’←🐉←’, ’→🐉🐉→’, ’←🦄←’, ’→🦄🐉→’]
  • [’→🐉🐉→’, ’←🐉←’, ’→🐉🐉→’, ’←🐉←’, ’→🦄🦄→’, ’←🦄🐉←’, ’→🦄🦄→’, ’←🐉←’, ’→🐉🐉→’, ’←🐉←’, ’→🐉🐉→’]

En fait, il y a une autre solution qui aurait dû apparaître avant, mais son premier chiffre est 0 et elle n’a donc pas été calculée.

Solution de Bellman

Dans les années 1950, au sein de RAND Corporation, Richard Bellman a développé une manière efficace pour gérer la récursivité dans des problèmes d’optimisation : la programmation dynamique. En 1962, il a publié des exemples d’utilisation de la programmation dynamique, parmi lesquels figure cette solution du présent problème :

Bellman applique la programmation dynamique à ce problème parce que la programmation dynamique sert à résoudre des problèmes d’optimisation sous contrainte, et que Bellman a réussi à interpréter ce problème comme un problème d’optimisation sous contraintes :

  • la quantité à optimiser est le nombre total de protagonistes sur la rive droite (le maximum étant 6)
  • les contraintes font que seuls ces 10 états sont possibles (en abscisse, le nombre de licornes sur la rive gauche, en ordonnée, le nombre de dragons sur la rive gauche) :

Par exemple le point de coordonnées (2,1) est grisé parce qu’il correspond à 2 licornes et un seul dragon sur la rive gauche, ce qui a priori ne pose pas problème, mais comme le nombre total de dragons et de licornes reste constant, cet état laisserait 1 licorne avec 2 dragons sur la rive droite et nous allons jeter un voile pudique sur ce qui se passerait alors...

Bellman propose alors de généraliser le problème, en ne regardant pas seulement l’état initial (3,3) mais aussi les états intermédiaires, et il calcule (récursivement, par programmation dynamique) le nombre total de licornes et de dragons pour chacun de ces états, au bout de N transitions.

Pour simplifier les calculs, Bellman considère comme transition, un aller-retour du bateau, de la rive gauche à la rive gauche, en amenant du monde à droite puis en en ramenant à gauche. Avec une exception : depuis l’état final on autorise exceptionnellement le bateau à revenir à vide, juste pour que cette transition aussi se termine avec le bateau à gauche.

Par exemple comme dans l’état final (0,0) on a 6 protagonistes (3 licornes et 3 dragons) sur la rive droite, on a f0(0,0)=6 :

De façon similaire on peut calculer les valeurs de f1 en certains points, en se basant sur celle déjà calculée :

Des valeurs de f2 peuvent ensuite être calculées à partir des précédentes, ce qui entame une récursion :

Par exemple le fait que f2(3,3)=2 signifie que depuis l’état initial (3,3) on peut, au mieux, en deux allers-retours, avoir 2 personnages sur la rive droite.

Une des caractéristiques de la programmation dynamique est que l’on résout des problèmes partiels et qu’ensuite on se sert de ces solutions pour résoudre le problème global, récursivement. Ce que fait Bellman pour estimer, pour chacun des états du graphe, l’indice N pour lequel fN(état)=6. Il obtient alors ceci :

Comme chaque sous-problème intervient dans la résolution du problème global, les étapes de cette solution apparaissent en rouge : le fait que pour l’état initial (3,3) la valeur de N est 6 signifie d’une part que pour résoudre le problème à partir de (3,3) il faut 6 allers-retours du bateau (avec un retour à vide après le 6e aller), d’autre part que pour y arriver il faut passer par l’état pour lequel N=5. De part en part, la solution apparaît sur le graphe en regardant les valeurs décroissantes de N :

Une autre caractéristique de la programmation dynamique est qu’une fois qu’on connaît l’optimum, on peut s’en servir pour retrouver la manière de l’obtenir. Par exemple pour le début de la solution on doit, par un aller-retour du bateau, aller de (3,3) à (3,2) comme on le voit sur le graphe ci-dessus : une licorne fait un aller-retour (valeur 3 inchangée) et un dragon fait un aller simple. Cela ne peut se faire que par un aller dragon+licorne suivi par un retour de la licorne seule (en fait il y a une autre façon de faire, la voyez-vous ?).

Pour en savoir plus, voir ce document éduscol. La programmation dynamique est un des chapitres de NSI en terminale.

Python et les graphes

Cette très élégante solution est de Jean-Christophe Filliâtre, qui, entre beaucoup d’autres choses, est un des auteurs du manuel de NSI 24 leçons avec exercices corrigés - Terminale (édité chez Ellipses, ISBN : 9782340038554). L’idée est de dessiner le graphe et d’y chercher un chemin allant de l’état initial vers l’état final. Le graphe ne comporte que 20 sommets et environ le quart d’entre eux sont isolés. La tâche n’est donc pas si énorme qu’on le croirait au début.

Mieux encore, au lieu de dessiner le graphe à la main, on pourrait demander à Python de le construire (et même de le dessiner comme on verra plus bas). Il s’agit alors de traduire en Python les contraintes du problème et une fois le graphe construit (sous la forme d’un dictionnaire Python), de demander à Python de chercher le chemin à l’aide d’un algorithme de parcours en largeur. Jean-Christophe Filliâtre n’est pas l’auteur de cette méthode, qu’Édouard Lucas attribue [4] à un « Monsieur Maurice, ancien élève de l’École Polytechnique ».

Mais Jean-Christophe Filliâtre est l’auteur d’un livre (cité ci-dessus) où figurent justement des explications sur la manière de construire un graphe, et de le parcourir en largeur, en Python. Alors il suffit d’utiliser les ressources de ce livre pour avoir en une fraction de seconde la solution du problème, dessin à l’appui. Voici comment on peut utiliser sa solution ci-dessous :

  • renommer graphe.py le fichier que voici ;
  • renommer largeur.py le fichier que voilà ;
  • compléter ce dernier fichier, en y ajoutant la fonction chemin qui calcule un chemin entre deux sommets du graphe (en cas de difficulté à faire cet exercice, il reste la possibilité d’acheter le livre et de copier le corrigé de cet exercice à la fin du livre) ;
  • exécuter le script Python que voici :
  1. from graphe import Graphe
  2.  
  3. # sommet = (d, l, b) avec
  4. #    0 <= d <= 3 le nombre de dragons sur la rive gauche
  5. #    0 <= l <= 3 le nombre de licornes sur la rive droite
  6. #    b un booléen indiquant si le bateau est sur la rive gauche
  7. g = Graphe()
  8. for d in range(4):
  9.     for l in range(4):
  10.         if l == 0 or l == 3 or (d <= l and 3-d <= 3-l):
  11.             g.ajouter_sommet((d, l, False))
  12.             g.ajouter_sommet((d, l, True))
  13.  
  14. print(g.nb_sommets(), "sommets")
  15.  
  16. def voyage(s, s1):
  17.     if g.sommet(s1):
  18.         g.ajouter_arc(s, s1)
  19.  
  20. for s in g.sommets():
  21.     dg, lg, gauche = s
  22.     dd, ld = 3 - dg, 3 - lg
  23.     if gauche:
  24.         # on transporte uniquement des dragons
  25.         for d in range(1, min(3, dg + 1)):
  26.             voyage(s, (dg - d, lg, False))
  27.         # on transporte uniquement des licornes
  28.         for l in range(1, min(3, lg + 1)):
  29.             voyage(s, (dg, lg - l, False))
  30.         # on transporte un de chaque
  31.         if dg >= 1 and lg >= 1:
  32.             voyage(s, (dg - 1, lg - 1, False))
  33.     else:
  34.         # on transporte uniquement des dragons
  35.         for d in range(1, min(3, dd + 1)):
  36.             voyage(s, (dg + d, lg, True))
  37.         # on transporte uniquement des licornes
  38.         for l in range(1, min(3, ld + 1)):
  39.             voyage(s, (dg, lg + l, True))
  40.         # on transporte un de chaque
  41.         if dd >= 1 and ld >= 1:
  42.             voyage(s, (dg + 1, lg + 1, True))
  43.  
  44. print(g.nb_arcs(), "arcs")
  45.  
  46. # recherche d'un chemin avec un parcours en largeur
  47.  
  48. from largeur import chemin
  49.  
  50. for s in chemin(g, (3, 3, True), (0, 0, False)):
  51.     print(s)

Télécharger

L’exécution du script mène à cette solution :

(3, 3, True)
(1, 3, False)
(2, 3, True)
(0, 3, False)
(1, 3, True)
(1, 1, False)
(2, 2, True)
(2, 0, False)
(3, 0, True)
(1, 0, False)
(1, 1, True)
(0, 0, False)

en 11 déplacements du bateau (ce qui correspond bien aux 6 aller-retours du bateau vus par Bellman, puisque le dernier retour se faisait à vide).

Le module graphviz de Python permet également de dessiner le graphe ainsi construit, et voici le résultat :

dragons_licornes 0/0/D 0/0/D 1/1/G 1/1/G 0/0/D->1/1/G 2/0/G 2/0/G 0/0/D->2/0/G 1/0/G 1/0/G 0/0/D->1/0/G 1/1/G->0/0/D 1/0/D 1/0/D 1/1/G->1/0/D 2/0/G->0/0/D 2/0/G->1/0/D 1/0/G->0/0/D 0/0/G 0/0/G 0/3/D 0/3/D 1/3/G 1/3/G 0/3/D->1/3/G 2/3/G 2/3/G 0/3/D->2/3/G 1/3/G->0/3/D 1/1/D 1/1/D 1/3/G->1/1/D 2/3/G->0/3/D 1/3/D 1/3/D 2/3/G->1/3/D 2/2/D 2/2/D 2/3/G->2/2/D 0/3/G 0/3/G 1/0/D->1/1/G 1/0/D->2/0/G 3/0/G 3/0/G 1/0/D->3/0/G 3/0/G->1/0/D 2/0/D 2/0/D 3/0/G->2/0/D 1/1/D->1/3/G 2/2/G 2/2/G 1/1/D->2/2/G 2/2/G->1/1/D 2/2/G->2/0/D 1/3/D->2/3/G 3/3/G 3/3/G 1/3/D->3/3/G 3/3/G->1/3/D 3/3/G->2/2/D 2/3/D 2/3/D 3/3/G->2/3/D 2/0/D->3/0/G 2/0/D->2/2/G 2/2/D->2/3/G 2/2/D->3/3/G 2/3/D->3/3/G 3/0/D 3/0/D 3/3/D 3/3/D

Solution Cubicle

Jean-Christophe Filliâtre n’est pas le seul auteur du manuel de NSI 24 leçons avec exercices corrigés - Terminale : un autre auteur de ce livre, Sylvain Conchon, est également (entre autres) développeur de Cubicle.

Cubicle, déjà décrit dans la partie sur le loup, la chèvre et la pomme, est un model checker qui permet de coder des systèmes de transitions et de vérifier si des états du système sont atteignables. Sylvain Conchon fait la remarque que

  • les problèmes de traversée de rivière sont des systèmes de transitions (ici une traversée du bateau d’une rive à l’autre est une transition),
  • la question posée par Alcuin est de savoir si un état peut être atteint (unsafe correspond à la situation où tout le monde est de l’autre côté, sain et sauf).

Cubicle est développé entre autres pour Intel, avec pour but de vérifier des protocoles de cohérence de cache dans les processeurs à plusieurs cœurs, et l’état dont on veut savoir q’il peut être atteint, est en fait celui qu’on veut éviter. L’idée est de prouver qu’un système est sûr par une exploration exhaustive d’un arbre pour prouver qu’il n’existe pas de contre-exemple. Par conséquent, le nom unsafe est donné à l’état cherché, alors que justement les licornes sont en sécurité dans cet état ! De même l’état initial (à partir duquel on voudrait savoir si unsafe peut être atteint) est appelé init.

Chaque transition est introduite par un prérequis (une proposition exprimant ce qui permet la transition) et ses effets sont décrits dans un langage de programmation propre à Cubicle et dont les affectations sont notées par le «  := » du langage Algol :

  1. var Lic_G : int (* licornes sur la rive gauche *)
  2. var Lic_D : int (* ... rive droite *)
  3. var Drag_G : int (* dragons sur la rive gauche *)
  4. var Drag_D : int (* ... rive droite *)
  5.  
  6. var V : bool (* True = La contrainte sur le nombre de licornes est vérifiée *)
  7.  
  8. var Dir : bool (* True : le bateau va vers la droite *)
  9.  
  10. (* Initialement :
  11.    ------------
  12.  
  13.   - seulement 3 licornes et 3 dragons sur la rive droite
  14.   - la règle sur les licornes est vérifiée
  15.   - le bateau va vers la droite
  16. *)
  17.  
  18. init () { Lic_G = 3 && Drag_G = 3 &&
  19.           Lic_D = 0 && Drag_D = 0 &&
  20.           Dir = True && V = True }
  21.  
  22.  
  23. (* Cubicle cherche à savoir si un état est atteignable.
  24.  
  25.    Ici, l'état qu'il faut atteindre est constitué de 3 licornes et 3
  26.    dragons sur la rive droite (et rien sur la rive gauche). La règle
  27.    sur les licornes devant être aussi vérifiée (V = True)
  28. *)
  29.  
  30. unsafe () { Lic_G = 0 && Drag_G = 0 && Lic_D = 3 && Drag_D = 3 && V = True }
  31.  
  32. (* Les mouvements possibles du bateau *)
  33.  
  34. (* Pour transporter une licorne vers la droite, il faut qu'il y ait
  35. des licornes sur la rive gauche (Lic_G > 0), que le bateau se dirige à
  36. droite (Dir = True) et que la règle des licornes soit vérifiée (V =
  37. True).
  38.  
  39. Si toutes ces conditions sont vérifiées, le bateau peut transporter
  40. une licorne de la rive gauche vers la rive droite. On met à jour les
  41. compteurs et on passe le booléen V à False afin que la dernière
  42. transition (voir fin du fichier) vérifie bien que la règle des
  43. licornes est respectée.
  44.  
  45. *)
  46.  
  47. transition vers_la_droiteL ()
  48. requires { Lic_G > 0 && Dir = True && V = True }
  49. {
  50.  Lic_G := Lic_G - 1;
  51.  Lic_D := Lic_D + 1;
  52.  Dir := False;
  53.  V := False;
  54. }
  55.  
  56. (* les autres règles se déduisent facilement... *)
  57.  
  58. transition vers_la_gaucheL ()
  59. requires { Lic_D > 0 && Dir = False && V = True }
  60. {
  61.  Lic_D := Lic_D - 1;
  62.  Lic_G := Lic_G + 1;
  63.  Dir := True;
  64.   V := False;
  65. }
  66.  
  67. transition vers_la_droiteD ()
  68. requires { Drag_G > 0 && Dir = True && V = True }
  69. {
  70.  Drag_G := Drag_G - 1;
  71.  Drag_D := Drag_D + 1;
  72.  Dir := False;
  73.  V := False;
  74. }
  75.  
  76. transition vers_la_gaucheD ()
  77. requires { Drag_D > 0 && Dir = False && V = True }
  78. {
  79.  Drag_D := Drag_D - 1;
  80.  Drag_G := Drag_G + 1;
  81.  Dir := True;
  82.  V := False;
  83. }
  84.  
  85. transition vers_la_droiteLL ()
  86. requires { Lic_G > 1 && Dir = True && V = True }
  87. {
  88.  Lic_G := Lic_G - 2;
  89.  Lic_D := Lic_D + 2;
  90.  Dir := False;
  91.  V := False;
  92. }
  93.  
  94. transition vers_la_gaucheLL ()
  95. requires { Lic_D > 1 && Dir = False && V = True }
  96. {
  97.  Lic_G := Lic_G + 2;
  98.  Lic_D := Lic_D - 2;
  99.  Dir := True;
  100.  V := False;
  101. }
  102.  
  103. transition vers_la_droiteDD ()
  104. requires { Drag_G > 1 && Dir = True && V = True }
  105. {
  106.  Drag_G := Drag_G - 2;
  107.  Drag_D := Drag_D + 2;
  108.  Dir := False;
  109.  V := False;
  110. }
  111.  
  112. transition vers_la_gaucheDD ()
  113. requires { Drag_D > 1 && Dir = False && V = True }
  114. {
  115.  Drag_G := Drag_G + 2;
  116.  Drag_D := Drag_D - 2;
  117.  Dir := True;
  118.  V := False;
  119. }
  120.  
  121.  
  122. transition vers_la_droiteLD ()
  123. requires { Lic_G > 0 && Drag_G > 0 && Dir = True && V = True }
  124. {
  125.  Lic_G := Lic_G - 1;
  126.  Lic_D := Lic_D + 1;
  127.  Drag_G := Drag_G - 1;
  128.  Drag_D := Drag_D + 1;
  129.  Dir := False;
  130.  V := False;
  131. }
  132.  
  133. transition vers_la_gaucheLD ()
  134. requires { Lic_D > 0 && Drag_D > 0 && Dir = False && V = True }
  135. {
  136.  Lic_G := Lic_G + 1;
  137.  Lic_D := Lic_D - 1;
  138.  Drag_G := Drag_G + 1;
  139.  Drag_D := Drag_D - 1;
  140.  Dir := True;
  141.  V := False;
  142. }
  143.  
  144. (* La règle des licornes.
  145.  
  146.  Pour repasser le booléen V à vrai, on vérifie la règle des licornes.
  147.  
  148.  Notez que tant que le booléen V est à False, aucune autre transition
  149.  ne peut être exécutée.
  150.  
  151. *)
  152.  
  153. transition regle_des_licornes()
  154. requires { V = False && (Lic_G > 0 => Lic_G >= Drag_G)
  155.                      && (Lic_D > 0 => Lic_D >= Drag_D) }
  156. { V := True }

Télécharger

Noter que la règle des licornes (celle qui autorise la transition sans qu’une licorne ne soit dévorée) est rédigée sous forme d’implications :

  • V doit être nié pour ne lancer cette vérification qu’après une traversée de la rivière,
  • s’il y a au moins une licorne sur la rive gauche, alors il y a au moins autant de licornes que de dragons sur la rive gauche,
  • s’il y a au moins une licorne sur la rive droite, alors il y a au moins autant de licornes que de dragons sur la rive droite.

L’exécution de ce script par Cubicle produit, en quelques secondes, la solution suivante :

========================================
* STATS
----------------------------------------
Number of visited nodes          : 456
Fixpoints                        : 1212
Number of solver calls           : 11924
Max Number of processes          : 0
Number of deleted nodes          : 0
Restarts                         :
0
========================================

Error trace: Init ->
            vers_la_droiteLD() ->
            regle_des_licornes() ->
            vers_la_gaucheL() ->
            regle_des_licornes() ->
            vers_la_droiteDD() ->
            regle_des_licornes() ->
            vers_la_gaucheD() ->
            regle_des_licornes() ->
            vers_la_droiteLL() ->
            regle_des_licornes() ->
            vers_la_gaucheLD() ->
            regle_des_licornes() ->
            vers_la_droiteLL() ->
            regle_des_licornes() ->
            vers_la_gaucheD() ->
            regle_des_licornes() ->
            vers_la_droiteDD() ->
            regle_des_licornes() ->
            vers_la_gaucheD() ->
            regle_des_licornes() ->
            vers_la_droiteDD() ->
            regle_des_licornes() ->
            unsafe[1]

et, avec l’option dot 2, le dessin de cette solution dans l’arbre exploré par Cubicle :

Un clic sur l’arbre ci-dessus permet d’accéder à la version pdf sur laquelle on a intérêt à zoomer pour voir que la solution est un chemin dans cet arbre.

La « trace d’erreur » sans les vérifications intermédiaires donne une solution très lisible, grâce à un nommage judicieux des transitions :

            vers_la_droiteLD() ->
            vers_la_gaucheL() ->
            vers_la_droiteDD() ->
            vers_la_gaucheD() ->
            vers_la_droiteLL() ->
            vers_la_gaucheLD() ->
            vers_la_droiteLL() ->
            vers_la_gaucheD() ->
            vers_la_droiteDD() ->
            vers_la_gaucheD() ->
            vers_la_droiteDD() ->

Et la liste des états (dragons RG, licornes RG, dragons RD, licornes RD, direction du bateau) parcourus est

(3,3,0,0,D)
(2,2,1,1,G)
(2,3,1,0,D)
(0,3,3,0,G)
(1,3,2,0,D)
(1,1,2,2,G)
(2,2,1,1,D)
(2,0,1,3,G)
(3,0,0,3,D)
(1,0,2,3,G)
(2,0,1,3,D)
(0,0,3,3,G)

On remarque que la solution trouvée par Cubicle n’est pas la même que celle trouvée par parcours en largeur du graphe : ce problème a plusieurs solutions.

Jeep

Les jeeps n’existant pas à l’époque d’Alcuin, c’est un chameau qui, ignorant que des siècles après lui, des véhicules allaient le remplacer en consommant le pétrole qui est sous ses pieds, transporte des graines en dévorant au passage une partie de sa cargaison :

LII. PROPOSITIO DE HOMINE PATERFAMILIAS.

Quidam paterfamilias iussit XC modia frumenti de una domo sua ad alteram deportari ; quae distabat leucas XXX : ea uero ratione, ut uno camelo totum illud frumentum deportaretur in tribus subuectionibus, et in unaquaque subuectione XXX modia portarentur : camelus quoque in unaquaque leuca comedat modium unum. Dicat, qui uelit, quot modii residui fuissent ?

Le chameau ne traverse donc pas une rivière, mais un désert. Cela change beaucoup de choses : il est possible de déposer une partie des 90 sacs de couscous au milieu du désert pour revenir les récupérer après.

 📦📦📦🐪______________________________

Une première idée est de faire transporter par le chameau les 90 sacs de couscous d’un coup, avec un aller simple. Il en mange 30 (il consomme un sac de couscous par lieue parcourue) et on arrive 30 lieues plus loin avec 60 sacs de couscous, de quoi nourrir pas mal de monde (sauf le chameau, vu qu’il s’est déjà bien gavé pendant la traversée du désert).

Mais Alcuin signale que la capacité de transport du chameau est limitée à 30 sacs. On ne peut donc appliquer la solution précédente. Si on lui fait porter 30 sacs (sa capacité maximale) à 30 lieues, il ne reste plus de couscous à l’arrivée. En plus pas de carburant pour aller chercher les deux chargements de 30 sacs restés au départ...

 📦📦______________________________🐪

Si on lui fait transporter moins de 30 sacs, il n’arrive pas à destination, faute de carburant pour lui. La constitution de dépots au milieu du désert est donc nécessaire.

On peut alors chercher à constituer un dépot à mi-chemin : on part avec 30 sacs de couscous faire un aller-retour à mi-chemin, soit à 15 lieues,

 📦📦______________📦🐪_______________

mais ce faisant on arrive à cette étape avec seulement 15 sacs restants et on en a besoin pour le trajet retour. L’idée était mauvaise après tout.

 📦📦🐪______________________________

Le problème a-t-il seulement une solution ? Si on constitue un dépot à 10 lieues, on peut y amener d’abord 10 sacs (en en consommant 20 pour l’aller-retour)

 📦📦🐪_________📦____________________

puis encore 10 (avec consommation de 20 sacs supplémentaires)

 📦🐪_________📦____________________

et enfin 20 puisqu’on n’a besoin que d’un aller simple cette fois-ci. On est alors ramené au problème de transporter 40 sacs de couscous à 20 lieues (qui restent à parcourir).

 _________📦📦🐪____________________

En laissant 10 sacs sur place on peut partir avec 30 sacs et arriver avec 10 sacs.

 _________📦____________________📦🐪

Le problème a donc bel et bien une solution. Mais elle n’est pas optimale puisqu’on a laissé 10 sacs abandonnés dans le désert.

Solution au problème

Soit d1 la distance entre le point de départ et le premier dépot. On a vu que d1=15 est trop important (il ne reste plus rien), et que d1=10 est trop important aussi (abandon d’une partie de la cargaison dans le désert). La valeur optimale de d1 est celle qui permet de placer exactement 60 sacs de couscous au dépot, ce qui permet de démarrer une récurrence sans perte de couscous. Comme il y a 3×30 sacs au début, il faut 2 allers-retours et un aller ce qui fait consommer 5×d1 sacs de couscous par le chameau, puisque la distance parcourue par celui-ci est 2×d1+2×d1+d1=5×d1. Comme il faut que cette quantité consommée soit 90-60=30 sacs, cela donne la valeur optimale de d1 : 5×d1=30 soit d1=6 lieues.

 ______📦📦🐪________________________

Il reste alors 30-6=24 lieues à parcourir, avec 60 sacs de couscous à livrer. En partant avec 30 sacs jusqu’au bout, on arrive avec 6 sacs de couscous ce qui n’est pas optimal (on a laissé 30 sacs en plein désert). Soit alors d2 la distance au bout de laquelle on va constituer un second dépot. Pour optimiser il faut que l’aller-retour suivi d’un aller simple fasse consommer par le chameau, une des deux cargaisons de 30 sacs. Alors 2×d2+d2=3×d2=30 d’où d2=10. On porte donc 30 sacs au point d1+d2=16

 ______📦_________📦🐪______________

Il en reste alors 20 (10 ont été consommés par le chameau), on en laisse 10 sur place et on repart avec les 10 restants pour permettre au chameau de revenir vide au premier dépot :

 ______📦🐪_________📦______________

Puis il repart avec les 30 sacs restants jusqu’au second dépot, où il arrive avec 20 sacs :

 ________________📦🐪______________

Il finit les 14 lieues restantes avec ces 30 sacs. Il arrive alors avec 30-14=16 sacs. C’est le maximum qu’il puisse livrer. Cela représente environ 18 pourcent de la cargaison initiale.

L’histoire n’est pas finie : dans ce jeu de Don Knuth, les cartes ne traversent pas une rivière mais une FIFO, le but étant qu’une fois arrivées sur la « rive droite » elles soient rangées dans l’ordre croissant. Ce jeu fait l’objet d’un chapitre entier du livre promenade d’Étienne Ghys et mène à une classification intéressante des permutations sur n éléments.