Traversée de la rivière

« River Crossing » est une série de casse-têtes logiques classiques dans lesquels le joueur doit faire traverser une rivière à un groupe de personnages ou d’objets à l’aide d’un bateau dont la capacité est limitée, tout en respectant des contraintes spécifiques. Certaines combinaisons de passagers ne peuvent pas être laissées seules ensemble sur l’une ou l’autre des rives — par exemple, un loup mangerait une chèvre, ou une chèvre mangerait un chou. Le joueur doit trouver une séquence de traversées en bateau permettant de faire passer tout le monde en toute sécurité sans enfreindre aucune contrainte.

Règles (Le loup, la chèvre et le chou – version classique)

1. Un fermier doit faire traverser une rivière à un loup, une chèvre et un chou.
2. Le bateau ne peut transporter à la fois que le fermier et un seul autre objet.
3. Le fermier doit être présent dans la barque à chaque traversée (la barque ne peut pas traverser toute seule).
4. Le loup et la chèvre ne peuvent pas être laissés seuls ensemble (le loup mangerait la chèvre).
5. La chèvre et le chou ne peuvent pas être laissés seuls ensemble (la chèvre mangerait le chou).
6. Le loup et le chou peuvent être laissés seuls ensemble sans danger.
7. Le but est de faire passer les quatre éléments (le fermier, le loup, la chèvre et le chou) de l’autre côté.

Solution (énigme classique)

1. Le fermier fait traverser la chèvre.
2. Le fermier revient seul.
3. Le fermier fait traverser le loup.
4. Le fermier ramène la chèvre.
5. Le fermier fait traverser le chou.
6. Le fermier revient seul.
7. Le fermier fait traverser la chèvre.

Total : 7 traversées.

Variantes courantes

• Missionnaires et cannibales : 3 missionnaires et 3 cannibales doivent traverser ; les cannibales ne doivent jamais être plus nombreux que les missionnaires sur l’une ou l’autre des rives.
• Maris jaloux : 3 couples doivent traverser ; aucune femme ne peut se trouver sur une rive avec un autre homme à moins que son mari ne soit présent.
• Pont et lampe de poche : 4 personnes traversent un pont de nuit avec une seule lampe de poche ; seules deux personnes peuvent traverser à la fois ; chaque personne marche à une vitesse différente ; le duo avance au rythme de la personne la plus lente.
• Groupes plus importants : versions étendues avec davantage de personnages et des graphes de contraintes plus complexes.

Stratégies

• Identifier la contrainte critique : Déterminez quel personnage ou quel objet est à l’origine du plus grand nombre de conflits. Dans le casse-tête classique, la chèvre entre en conflit à la fois avec le loup et le chou, ce qui en fait l’élément clé à gérer.
• La technique de la navette : il faut parfois ramener un objet du côté de départ pour résoudre un conflit. Ce mouvement « en arrière », qui va à l’encontre de l’intuition, est souvent la clé de la résolution.
• Penser en états : représentez chaque configuration possible des objets sur les deux rives comme un « état ». Le casse-tête consiste alors à trouver un chemin passant par des états valides, du départ jusqu’à l’arrivée.
• Réduire au minimum les traversées : la solution optimale utilise le moins de traversées possible. Pour le casse-tête classique, 7 traversées constituent la solution optimale.
• Graphique des conflits : tracez un graphique indiquant quels objets sont en conflit. L’élément présentant le plus de conflits nécessite généralement la plus grande prudence : il doit souvent être transporté en premier et peut devoir être ramené en arrière.
• Procédez à rebours : il est parfois utile d’imaginer à quoi doivent ressembler les dernières traversées et de remonter en arrière pour déterminer les mouvements précédents.

Les énigmes de traversée de rivière comptent parmi les plus anciennes énigmes logiques connues, la première version répertoriée apparaissant dans le manuscrit médiéval « Propositiones ad Acuendos Juvenes » (Problèmes pour aiguiser l’esprit des jeunes), attribué à Alcuin d’York vers l’an 800 de notre ère. Alcuin était un érudit anglais et conseiller de l'empereur Charlemagne ; son recueil comprenait le problème du loup, de la chèvre et du chou, ainsi que plusieurs autres énigmes mathématiques. Les énigmes de traversée de rivière ont donc plus de 1 200 ans.

La variante « Les missionnaires et les cannibales » est apparue au XIXe siècle et est devenue un problème classique de la recherche en intelligence artificielle au XXe siècle. Ce fut l’un des premiers problèmes utilisés pour illustrer les algorithmes de recherche dans l’espace d’états. En 1968, Amarel s’en est servi comme étude de cas pour la représentation des problèmes en IA, montrant comment le choix de la représentation influe considérablement sur la difficulté à trouver une solution. Depuis, ce problème figure dans d’innombrables manuels d’IA.

Le problème du « pont et de la torche » a acquis une grande notoriété lorsqu’il est devenu une question d’entretien très courante dans les entreprises technologiques à la fin des années 1990 et dans les années 2000, en particulier chez Microsoft. Il met les candidats au défi d’optimiser le temps total de traversée lorsque les individus ont des vitesses différentes — un défi fondamentalement différent de la nature « satisfaction de contraintes » de la traversée classique de la rivière.

Les casse-têtes de traversée de rivière perdurent depuis plus d’un millénaire car ils enseignent des compétences fondamentales en résolution de problèmes : décomposer une situation complexe en états, identifier les contraintes, envisager des actions contre-intuitives (ramener quelque chose) et explorer systématiquement les possibilités. On les retrouve dans les livres de mathématiques ludiques, les programmes d’enseignement en informatique et les recueils de casse-têtes du monde entier. Leur cadre narratif — un fermier, une rivière, des animaux affamés — rend la logique abstraite concrète et facile à retenir.