3. Exemples de modélisation
3.1 Tic-tac-toe
Un état peut être une matrice 3 × 3 dont chaque case contient X, O ou le symbole vide. Toutes les matrices possibles ne sont pas valides : le nombre de marques doit respecter l’alternance des joueurs et aucun coup ne peut suivre une victoire.
- État initial : grille vide.
- Opération : placer la marque du joueur courant dans une case vide.
- États finaux : victoire de
X, victoire deOou partie nulle.
Le calcul simplifié de 9! = 362 880 arrangements illustre déjà l’explosion combinatoire. Le but de la formalisation n’est donc pas de dessiner le graphe complet, mais de donner des règles générales permettant de l’engendrer.
3.2 Bidons de 4 L et 3 L
L’activité découverte demande d’obtenir exactement 2 L dans le bidon de 4 L à partir de deux bidons vides et non gradués.
Un état est la paire (v4, v3) telle que :
v4 ∈ {0,1,2,3,4};v3 ∈ {0,1,2,3}.
L’état initial est (0,0) et le test de but est v4 = 2, donc tout état (2,n) est final.
Les opérations consistent à remplir un bidon, le vider, transvider tout son contenu dans l’autre lorsque l’espace suffit, ou transvider jusqu’à remplir le bidon de destination. Une opération permettant de retirer une quantité arbitraire serait inadéquate, puisque les bidons ne sont pas gradués.
Un chemin solution est :
(0,0) → (0,3) → (3,0) → (3,3) → (4,2) → (0,2) → (2,0).
Le chemin n’est pas la représentation elle-même : il n’est qu’une solution parmi celles que la représentation rend possibles.
3.3 Fermier, chien, lapin et salade
Deux ensembles A et B représentent les rives. Chaque identifiant — F pour le fermier, C pour le chien, L pour le lapin et S pour la salade — appartient exactement à une rive.
- État initial :
A={F,C,L,S},B=∅. - État final :
A=∅,B={F,C,L,S}. - Opérations : le fermier traverse seul ou avec un passager, dans les deux directions.
- Contraintes : le chien ne peut rester seul avec le lapin, ni le lapin avec la salade, sans le fermier.
Une séquence valide fait traverser le lapin, ramène le fermier seul, fait traverser le chien, ramène le lapin, fait traverser la salade, ramène le fermier seul, puis fait traverser le lapin. Les retours doivent être présents dans l’ensemble des opérations, sinon le problème devient insoluble.
3.4 Cinq billes
Un état est une séquence de cinq symboles contenant exactement deux V, deux R et un B.
- État initial :
VVBRR. - État final :
RRBVV. - Opérations corrigées :
VB → BV,BR → RB,VRB → BRVetBVR → RVB.
Dans chaque règle, le motif de gauche est la précondition locale et celui de droite est l’effet. L’invariant est la conservation exacte des cinq billes.
3.5 Douze maillons
Un état est un ensemble de chaînes (Ni,E) où Ni est la longueur et E vaut O pour ouverte ou F pour fermée. Le nombre de chaînes varie, mais la somme des longueurs demeure 12.
- État initial :
{(3,O),(3,O),(3,O),(3,O)}. - État final :
{(12,F)}. - Attacher : deux chaînes ouvertes
(Ni,O)et(Nj,O)deviennent(Ni+Nj,O). - Ouvrir :
(Ni,F)devient(Ni,O). - Fermer :
(Ni,O)devient(Ni,F).
La version corrigée exige deux chaînes ouvertes pour l’attachement. C’est un exemple typique d’opération qui doit respecter la réalité du domaine, pas seulement produire arithmétiquement la longueur voulue.