Nous sommes face à 3 jauges A,B,C de contenances respectives : 10,7,5.
12 unités sont présentes en tout (au départ 10 à gauche et 2 au centre).
On peut naturellement observer qu'il y a au maximum 6 déplacements théoriques possibles : A->B, A->C, B->A, B->C, C->A, C->B.
Depuis la configuration initiale, voici le schéma des cas possibles (qu'importe les doublons).
La moitié des déplacements sont impossibles, celà se présente dans 2 cas :
Ces limitation sont justement à l'origine du "piment" de ce jeu. Elles vont nécéssairement contribuer à la réduction du grand nombre de cas possibles pour ce jeu. Une approche exhaustive devient donc envisageable.
Afin de rescencer l'intégralité des configurations possibles du jeu, nous allons faire appel à la théorie des graphes (chère à Leonhard Euler) Tous les ingredients sont réunis pour créer un graphe mixte de l'intégralité des configurations possibles du jeu. Une flèche simple (un arc) indique qu'une transition d'une configuration à l'autre est possible, une double flèche (arête) précise que la transition est réversible.
Nous nous retrouvons avec un graphe mixte (doubles flèches et simples flèches - arcs et arêtes) non planaire (on ne peut pas le dessiner sur le plan ou sur une sphère sans que des arcs/arêtes ne se coupent). Comme nous pouvions nous y attendre, il y a 22 configurations différentes, ce qui est bien moins que l'ensemble des configurations qu'une distribution complete pourait donner. Par exemple, la configuration 9-2-1 est absente du graph, c'est donc une configuration impossible.
De plus, nous remarquons que certaines configurations on beaucoup plus de poid (plus de possibilités de les former) que d'autres. par exemple, la configuration 0-7-5 possède 13 parents alors que la configuration 9-0-3 n'en possède que 2.
D'ailleurs, la plupart des 60 arcs qui sont présents dans ce graphe pointes vers une petite minorité de configuration. Je les appellerais des attracteurs (attention, rien à voir avec le terme utilisé par les mathématiques fractales, mais il me semble approprié car au fonctionement assez similaire).
Afin d'améliorer la compréhension de ce graph, je décide de mettre en valeur le poid de chaque nœud (configuration) en fonction de sa centralité d'intermédiarité.
Cet outil de mesure compte le nombre de fois où un nœud agit comme un point de passage le long du plus court chemin entre deux autres nœuds.
La teinte (entre bleu = 0 et rouge = max) indique l'intermédiarité des nœuds.
Ce nouveau graphe est disponible à droite.
Nous voyons se dégager une distribution assez claire dans le graph.
De grands nœuds occupent le haut de celui-ci, puis vien la configuration de départ, et enfin on voit toute une série de configurations (la majorité des nœuds du graph) qui s'éloignent petit à petit de la configuration de départ avec un poid assez faible.
Afin de mettre en évidence la ou les chaines qui se dessinent dans ce graph, j'ai réorganisé celui-ci selon un algorithme three baloon.
Nous voici maintenant avec 2 chaines bien mises en évidence ayant pour origine notre configuration de départ : 10-2-2
Nous remarquons que nos attracteurs sont au nombre de 2 et peuvent être sortis de ces chaines : 0-7-5 et 5-7-0
Enfin, les 2 chaines de longueur 9 se rejoignent en un nœud commun 10-1-1 qui est le nœud le plus excentré du graphe.
Voici les 2 chaines mises en valeur une fois les attracteurs retirés et sans les arcs/arêtes parasites. J'ai marqué le déplacement nécéssaire à chaque arc ou arête concerné pour passer d'un nœud à l'autre de gauche à droite.
On peut remarquer que dans les chaines 1 et 2, il y a des motifs qui se répettent.
Chaine 1 : [AC] [BA] + [CB] [AC] [CB] [BA] X2
Chaine 2 : [BC] [AB] [BC] [CA] X2 + [BC] [CA]
En fait, en observant plus précisément, on se rend compte que ces motifs se repette tout au long de la chaine, mais que les cas exception correspondes à l'évitement des attracteurs. De plus, le parcours des chaines devra se faire à l'aide du motif de chaine 1 [BC] [AB] [BC] [CA] à cause de l'arc présent entre la configuration 5-2-5 et 7-0-5.
Pour bien définir notre algorithme, il va donc nous falloir correctement définir un attracteur. En me basant sur le graphe filtré par l'algorithme tree baloon j'en déduit que les attracteurs sont au nombre de 3 : 10-2-0 , 5-7-0 , 0-7-5
J'emet donc l'hypothèse de définition suivante :
Toutes les configurations dans lesquelles une jauge est pleine ainsi que sa voisine immédiate sont considérées atracteurs.
Nous avons tous les éléments constitutif de notre algorithme, voici les test :
Algorithme de parcour des chaine No.1Configuration initiale : 10-2-0
Liste des attracteurs : 10-2-0 , 5-7-0 , 0-7-5
Motif sélectionné : [CB]-[AC]-[CB]-[BA]
L'algorithme a parcouru l'intégralité des nœuds de nos chaines réunies en 24 lignes et 21 mouvements, donc succès complet !
- 10-2-0 --[CB]--> 10-2-0
- 10-2-0 --[AC]--> 5-2-5
- 5-2-5 --[CB]--> 5-7-0 il s'agit d'un attracteur, on saute l'instruction
- 5-2-5 --[BA]--> 7-0-5
- 7-0-5 --[CB]--> 7-5-0
- 7-5-0 --[AC]--> 2-5-5
- 2-5-5 --[CB]--> 2-7-3
- 2-7-3 --[BA]--> 9-0-3
- 9-0-3 --[CB]--> 9-3-0
- 9-3-0 --[AC]--> 4-3-5
- 4-3-5 --[CB]--> 4-7-1
- 4-7-1 --[BA]--> 10-1-1
- 10-1-1 --[CB]--> 10-2-0 il s'agit d'un attracteur, on saute l'instruction
- 10-1-1 --[AC]--> 6-1-4
- 6-1-4 --[CB]--> 6-6-0
- 6-6-0 --[BA]--> 10-2-0 il s'agit d'un attracteur, on saute l'instruction
- 6-6-0 --[CB]--> 6-6-0
- 6-6-0 --[AC]--> 1-6-5
- 1-6-5 --[CB]--> 1-7-4
- 1-7-4 --[BA]--> 8-0-4
- 8-0-4 --[CB]--> 8-4-0
- 8-4-0 --[AC]--> 3-4-5
- 3-4-5 --[CB]--> 3-7-2
- 3-7-2 --[BA]--> 10-0-2
- 10-0-2 --[CB]--> 10-2-0 il s'agit d'un attracteur, on saute l'instruction
- 10-0-2 --[AC]--> 7-0-5 On a rebouclé sur une configuration déjà observée
- 7-0-5 --[CB]--> 7-5-0 Idem
- 7-5-0 --[BA]--> 10-2-0 il s'agit d'un attracteur, on saute l'instruction
- 7-5-0 --[CB]--> 7-5-0 Bouclage, même config. que ligne 05