Résoudre le classique puzzle de la traversée de rivière : renard, poule, grain

Le « Smart Kit River Crossing Game » est une version numérique du classique puzzle loup-chèvre-chou (ou renard-poule-grain) — un problème de satisfaction de contraintes remontant au moins au IXe siècle en Europe. Le défi : transporter trois objets de l'autre côté d'une rivière avec un bateau ne contenant qu'un objet plus l'opérateur, sans laisser de paires conflictuelles seules.

Séquence de solution

État initial : Renard, Poule, Grain | Bateau | (rive opposée vide)

1. Emmener la Poule de l'autre côté. (Renard et Grain en sécurité ensemble — le renard ne mange pas le grain)
2. Revenir seul.
3. Emmener le Renard de l'autre côté.
4. Ramener la Poule EN ARRIÈRE. (Étape critique — ne peut pas laisser Renard et Poule ensemble)
5. Emmener le Grain de l'autre côté. (Renard et Grain en sécurité ensemble)
6. Revenir seul.
7. Emmener la Poule de l'autre côté.

État final : (rive initiale vide) | Bateau | Renard, Poule, Grain

Pourquoi ça marche : analyse des contraintes

Paires interdites (sans surveillance) : Renard+Poule (prédation), Poule+Grain (consommation).
Paires sûres : Renard+Grain (pas d'interaction).
Insight clé : La Poule conflict avec LES DEUX autres — c'est le « nœud central » du graphe de conflits. Donc la Poule doit être l'élément navette : déplacée d'abord, ramenée, déplacée en dernier. Renard et Grain n'interagissent jamais directement.

Approche de résolution généralisable

1. Modéliser les contraintes explicitement — lister tous les états interdits.
2. Identifier l'élément le plus contraint — ici, la Poule.
3. Travailler à rebours depuis l'objectif — le dernier coup doit amener le dernier élément.
4. Utiliser la recherche dans l'espace d'états — BFS/DFS trouve la solution optimale (7 coups minimum).
5. Vérifier qu'aucun état interdit ne survient — y compris pendant le transit en bateau.

Variations et extensions

Missionnaires et cannibales (3 chacun, bateau 2 places). Maris jaloux (3 couples, bateau 2, aucune femme avec autre mari sans le sien). Versions modernes ajoutent limites de temps, bateaux multiples, contraintes dynamiques. La logique centrale reste : satisfaction de contraintes par recherche d'espace d'états.