Jeu du baguenaudier

Le jeu est peut-être d'origine chinoise, où il est connu sous le nom de liulianhuan 九連環 (Les neuf anneaux). Il est expliqué dans le problème 107 du livre De viribus quantitatis (1496-1508) de Luca Pacioli^[3] et il a été étudié dans leurs ouvrages par John Wallis^[4] et par Jérôme Cardan^[5].

Édouard Lucas, l'inventeur des tours de Hanoï, a proposé une solution basée sur le système binaire et le code de Gray qui se formule comme son casse-tête^[6]. Le nombre minimum de déplacements pour résoudre un problème à ${\displaystyle n}$ anneaux est donné par la suite (référencée A000975 dans l'OEIS) :

${\displaystyle a(n)=\left\lceil {\tfrac {2^{n+1}-2}{3}}\right\rceil ={\begin{cases}{\frac {2^{n+1}-2}{3}},&{\text{quand }}n{\text{ est pair,}}\\{\frac {2^{n+1}-1}{3}},&{\text{quand }}n{\text{ est impair.}}\end{cases}}}$^[7]

où ${\displaystyle \lceil x\rceil }$ est la partie entière par excès (plafond) de ${\displaystyle x}$.

Cette section ne cite pas suffisamment ses sources (mai 2024). 

Pour l'améliorer, ajoutez des références de qualité et vérifiables (comment faire ?) ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Considérons une représentation binaire du jeu. Résoudre le jeu signifie mettre toutes les cases à 1 (ou l'inverse les remettre toutes à 0).

Avec un baguenaudier physique, "remplir" ou "vider" les cases consiste à passer (dans le bon ordre) un arceau principal ou une cordelette dans ou hors d'un des petits anneaux du jeu pour, soit libérer la cordelette ou l'arceau principal de tous les petits anneaux, soit à l'inverse emprisonner la cordelette ou l'arceau par tous les petits anneaux: les "cases" représentent l'état de chacun des petits anneaux (c'est-à-dire si le grand arceau ou la cordelette passe ou pas au travers de chaque petit anneau).

Cependant le jeu avec la cordelette flexible nécessite des manipulations plus simples pour passer d'un état à l'autre ; le jeu avec l'arceau inflexible demande de plus de dextérité pour faire passer les petits anneaux les uns dans les autres, même si l'arceau passe ou pas en leur centre (qui sont alors soit de diamètres différents soit déformables de façon élastique, ou alors inflexibles mais de forme ovoïdale, ce qui nécessite alors de contrôler leur rotation de manière précise surtout si les ovales sont très faiblement aplanis, avec juste l'aplanissement nécessaire pour pouvoir passer un des petits anneaux dans un autre).

Dans la version chinoise du baguenaudier, la difficulté manipulatoire est augmentée par le fait que chacun des petits anneaux sont tous inflexibles et de même taille (de même que l'arceau) mais les petits anneaux sont tenus chacun par un crochet (pouvant pivoter librement) au bout d'une courte tige inflexible, les tiges (toutes de même longueur) étant maintenues parallèles avec un espacement régulier dans un support inflexible, mais pouvant coulisser longitudinalement au travers de ce support : au lieu d'orienter les anneaux, on peut les déplacer vers l'avant ou l'arrière en coulissant dans le support la tige où chaque anneau est lié pour ensuite pouvoir effectuer les rotations des anneaux à la position du crochet. Cette disposition est perturbante pour l'expérimentateur du jeu qui ne perçoit pas bien comment le problème est en fait plus simple qu'il ne semble, mais il nécessite une grande dextérité pour le résoudre car il faut orienter convenablement les anneaux (qui pivotent très librement autour de leur crochet) et ajuster le coulissement des tiges (qui lui aussi se fait librement) : on ne peut pas résoudre ce problème si les tiges ne sont pas à l'horizontale (pour qu'elles ne coulissent pas d'elles-mêmes dans le support à cause de la gravité, ce qui a pour effet aussi de réorienter chacun des anneaux mais pas de la façon voulue par l'opérateur).

Mais pour un expérimentateur qui connait la technique de manipulation, la version inflexible du baguenaudier permet une manipulation bien plus rapide (au moins un changement ou "coup" par seconde) qu'avec une navette flexible (où chaque changement peut demander plusieurs secondes en prenant garde à conserver les boucles flexibles de la navette pour qu'elles restent dans chaque anneau, mais l'élasticité de la flexion de la navette peut lui faire changer sa place si le manipulateur ne retient pas les boucle extrêmes en maintenant une tension longitudinale suffisante sur celle-ci, mais souvent cette navette est plus longue que nécessaire et ne reste pas tendue, une des boucles peut donc s'échapper facilement librement de l'anneau où le manipulateur l'avait placée).

Mais algorithmiquement les problèmes à résoudre pour sur ces baguenaudiers physiques (dont il existe de nombreuses variantes dans le monde, depuis plusieurs millénaires pour certaines) sont équivalents au problème mathématique à "cases" binaires (qui lui ne demande aucune dextérité de manipulation mais seulement la réflexion logique).

• On peut toujours inverser (passer de 1 à 0 ou vice-versa) la case 1.
• On ne peut inverser ("vider" ou "poser") la case ${\displaystyle j}$, ${\displaystyle j\in [2,n]}$ que :
  • si la case ${\displaystyle j-1}$ est à 1 et toutes les cases précédentes sont à 0, ou
  • si la case ${\displaystyle j-1}$ est à 0 et toutes les cases précédentes sont à 1.

Ces règles sont totalement symétriques, on obtient une solution en sens inverse si on inverse les valeurs 1 et 0 dans toutes les cases simultanément. Ce qui donne aussi une solution équivalente au problème inverse (libérer la cordelette ou l'arceau des petits anneaux, ou parvenir à le faire passer dans tous les petits anneaux).

De même le problème purement binaire utilise une numérotation (un ordre) préétablie des cases mais somme toute arbitraire (on peut tout autant permuter les cases). Le jeu physique impose en revanche un ordre, imposé par sa construction, mais cet ordre n'ajoute aucune difficulté à la résolution algorithmique du problème qui fournit une solution quel que soit cet ordre imposé au départ.

Il faut au minimum 10 coups (et moins de 10 secondes) pour résoudre le baguenaudier pour ${\displaystyle n=4}$. Tous les 2 coups, c'est la case 1 qui est inversée, tous les 4 coups c'est la case 2 qui est inversée, les cases dans la dernière moitié ne sont inversées chacune qu'une seule fois dans des coups séparés (avec 4 coups d'écart entre ces coups). Plusieurs solutions sont possibles (de façon combinatoire en raison de la symétrie du problème et de l'ordre initial arbitraire des cases), il y a donc ${\displaystyle n!=24}$ solutions minimales en 10 coups, dont en voici une (qui représente aussi une solution du problème inverse, en la lisant soit de gauche à droite soit de droite à gauche, ou bien en permutant l'interprétation des états 1 ou 0 de chaque case ; si on effectue ces deux changements d'interprétation simultanément, on obtient aussi une deuxième solution du même problème initial car cela revient à simplement inverser l'ordre des cases et donc donne une autre des 24 permutations possibles). :

Les baguenaudiers sont traditionnellement construits avec un nombre impair d'anneaux : les modèles les plus courants avec 5 anneaux demandent 21 coups (et ils peuvent donc s'ouvrir et se fermer facilement en moins de 20 secondes avec des composants inflexibles). Des modèles à 7 anneaux existent, qui demandent au minimum 85 coups et donc un peu plus d'une minute pour les ouvrir ou les fermer en un minimum de coups. Un modèle rigide à 9 anneaux demande au minimum 341 coups, et donc presque 6 minutes de manipulations continues (au moins un coup par seconde) pour l'ouvrir ou le fermer complètement sans erreur.

La fonction vider(n) fait passer les n cases du baguenaudier de 1 à 0, remplir(n) fait passer les n cases du baguenaudier de 0 à 1. poser(i) rend la case i égale à 1, enlever(i) rend la case i égale à 0.

def remplir(n):
   if n == 1:
      poser(1)
   elif n > 1:
      remplir(n-1)
      vider(n-2)
      poser(n)
      remplir(n-2)
      
def vider(n):
   if n == 1:
      enlever(1)
   elif n > 1:
      vider(n-2)
      enlever(n)
      remplir(n-2)
      vider(n-1)