🤖 AI

CayleyR: Solving the TopSpin puzzle via cycle intersection

Cet article présente cayleyR, un package R qui résout le casse-tête de permutation TopSpin(n,k) en employant une recherche bidirectionnelle itérative avec détection d'intersection de cycles dans des graphes de Cayley, optimisée par le hachage C++ et une accélération optionnelle par GPU Vulkan.

Auteurs originaux : Yuri Baramykov

Publié 2026-07-16

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yuri Baramykov

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le Puzzle du Labyrinthe Infini

Imaginez que vous vous trouviez dans un immense labyrinthe invisible où chaque tour que vous prenez modifie toute la configuration du monde autour de vous. Il ne s'agit pas seulement d'un jeu de « gauche ou droite » ; c'est un jeu de permutations, une branche des mathématiques appelée la théorie des groupes qui étudie comment les choses peuvent être réorganisées. Pensez à un jeu de cartes : si vous les mélangez, vous créez un nouvel ordre. Si vous les mélangez à nouveau, vous en créez un autre. Le « graphe de Cayley » est une carte de chaque ordre possible de ces cartes, reliées par les mouvements que vous faites pour passer d'un ordre à un autre.

Le puzzle spécifique que ce document traite s'appelle TopSpin. Imaginez une piste circulaire avec des jetons numérotés (comme des perles sur un collier) et une fenêtre qui peut en retourner quelques-uns. Vous pouvez faire tourner toute la piste ou retourner les jetons dans la fenêtre. Le but est simple : remettre les perles d'un désordre chaotique à leur ordre parfait et numéroté. Le problème est qu'en ajoutant des perles, le nombre de configurations possibles explose. Pour seulement 20 perles, il y a plus de façons de les disposer qu'il n'y a d'atomes dans l'univers. Les méthodes informatiques traditionnelles, qui tentent de vérifier chaque chemin un par un, se retrouvent bloquées dans ce labyrinthe infini presque immédiatement. Ce document introduit une nouvelle façon de naviguer dans ce labyrinthe, non pas en parcourant chaque chemin, mais en lançant des fléchettes en espérant que deux d'entre elles atterrissent au même endroit.

Le Papier : Jeter des fléchettes dans le noir

Dans ce document, Yuri Baramykov introduit un nouvel outil logiciel appelé cayleyR et une stratégie ingénieuse pour résoudre le puzzle TopSpin, même lorsqu'il est immense. Au lieu d'essayer de cartographier l'intégralité du labyrinthe du début à la fin, l'auteur utilise une méthode appelée Intersection de Cycles Itératifs (ICI).

Voici comment cela fonctionne, en utilisant une analogie ludique : Imaginez que vous et un ami soyez perdus dans une forêt géante et circulaire (le graphe de Cayley). Vous partez de côtés opposés et vous voulez tous deux vous retrouver au milieu.

L'ancienne méthode : Vous essayez tous deux de parcourir chaque chemin, étape par étape, en marquant chaque arbre que vous voyez. Cela prend un temps infini car la forêt est trop grande.
La méthode cayleyR : Au lieu de marcher prudemment, vous saisissez tous deux une poignée de « graines magiques » (des séquences de mouvements aléatoires). Vous les plantez et les regardez pousser en de gigantesques lianes bouclées (des cycles). Comme la forêt est circulaire, ces lianes finissent par boucler sur elles-mêmes.
L'intersection : Vous continuez à jeter ces graines et à faire pousser des lianes. Finalement, l'une de vos lianes croise le chemin de l'une des lianes de votre ami. Lorsqu'elles se touchent, vous avez trouvé un point de rencontre ! Vous pouvez alors retracer le chemin depuis votre point de départ, le long de votre liane, jusqu'au point de rencontre, puis suivre la liane de votre ami en sens inverse jusqu'à son point de départ.

Le document explique que cette stratégie de « croissance de lianes » est beaucoup plus rapide que de parcourir chaque chemin. Le logiciel génère des séquences de mouvements aléatoires, calcule les boucles qu'elles créent et vérifie si l'une de ces boucles chevauche les boucles générées de l'autre côté. S'ils ne se chevauchent pas immédiatement, le logiciel choisit les deux lianes les plus proches les unes des autres (en utilisant un « guide de distance ») et commence à faire pousser de nouvelles lianes à partir de ces points. Il répète ce processus jusqu'à ce que les deux côtés se rencontrent.

Ce que le papier a réellement découvert

L'auteur n'a pas seulement inventé l'idée ; il a construit un programme informatique fonctionnel pour la tester. Voici ce que les expériences ont montré :

Cela fonctionne sur de gros puzzles : Le logiciel a résolu avec succès des puzzles TopSpin allant jusqu'à 20 jetons (où le nombre de configurations possibles est 20 factorielle, soit environ 2,4 quintillions). C'est une taille qui ferait planter les ordinateurs traditionnels.
C'est rapide : Lors de tests avec 14 jetons, l'ordinateur a trouvé une solution en une moyenne de 1,12 seconde. Même les puzzles les plus difficiles du test ont été résolus en moins de 3,5 secondes.
Toutes les graines ne sont pas égales : Le papier a testé différentes façons de choisir quelles « graines magiques » (séquences de mouvements aléatoires) planter. Ils ont découvert que choisir des séquences qui visitent le plus de points uniques (appelées « most unique ») était le plus susceptible de trouver une solution (résolvant 83 % des cas de test), mais que les chemins trouvés étaient parfois très longs. Choisir des séquences qui visitaient les mêmes points de manière répétée (« most repeated ») était le plus fiable pour trouver des chemins courts rapidement.
Ce n'est pas parfait : Le papier est très clair sur le fait que les chemins trouvés ne sont pas nécessairement les chemins les plus courts. L'algorithme trouve un chemin, pas toujours le meilleur chemin. Cependant, le logiciel inclut une étape de « post-traitement » qui tente de raccourcir le chemin après coup, réduisant parfois le nombre de mouvements de moitié.

Ce que le papier écarte (et ce qu'il ne fait pas)

Il est important de savoir ce que ce document ne prétend pas faire :

Ce n'est pas une garantie du chemin le plus court : L'auteur stipule explicitement que l'algorithme d'Intersection de Cycles Itératifs ne garantit pas l'itinéraire le plus court. Il trouve une solution, mais il peut faire un détour.
Ce n'est pas encore un remède miracle pour chaque puzzle : La version actuelle du logiciel est spécifiquement conçue pour le puzzle TopSpin. Bien que l'auteur suggère que l'idée pourrait fonctionner pour d'autres puzzles (comme le tri de pancakes), le document prouve seulement qu'elle fonctionne pour TopSpin.
L'idée « holographique » n'est qu'une supposition : Le document mentionne une nouvelle théorie sophistiquée appelée « dualité holographique » qui pourrait aider à visualiser ces puzzles comme des formes sur une sphère. Cependant, l'auteur admet que cela est spéculatif. Il précise qu'il « reste à explorer » et que la version actuelle du logiciel n'utilise cela que pour de jolies images, et non pour résoudre réellement le puzzle.

L'essentiel

Ce document présente une nouvelle façon ludique et hautement efficace de résoudre un puzzle mathématique très difficile. En cessant de tenter de cartographier le monde entier pour plutôt chercher l'endroit où deux chemins aléatoires se croisent, le logiciel cayleyR peut résoudre des puzzles TopSpin de 20 jetons en seulement quelques secondes. C'est un rappel que, dans un immense labyrinthe, vous n'avez pas forcément besoin de connaître chaque tournant ; vous avez juste besoin de trouver un endroit où deux chemins errants se rencontrent par hasard. Le logiciel est gratuit et disponible pour que quiconque puisse l'essayer, bien que l'auteur prévienne que, s'il trouve des solutions rapidement, il ne trouve pas toujours la solution parfaite.

Résumé Technique : CAYLEYR : RÉSOLUTION DU PUZZLE TOPSPIN VIA L'INTERSECTION DE CYCLES

1. Énoncé du Problème
Le document traite du défi computationnel de la résolution du puzzle TopSpin $(n, k)$ , un puzzle de permutations impliquant $n$ jetons sur une piste circulaire et une fenêtre de type tourniquet d'une largeur $k$ . L'objectif est de transformer une permutation initiale donnée en une permutation cible en utilisant deux mouvements principaux : un décalage cyclique de l'ensemble de la piste (Gauche $L$ ou Droite $R$ ) et une inversion des $k$ jetons à l'intérieur du tourniquet ( $X_k$ ).

Algébriquement, l'espace d'états correspond au graphe de Cayley $\Gamma(G, \{L, R, X_k\})$ , où $G$ est le groupe symétrique $S_n$ (pour $k$ pair) ou le groupe alterné $A_n$ (pour $k$ impair). Résoudre le puzzle équivaut à trouver un chemin entre deux sommets de ce graphe. Les auteurs notent que pour $n > 10$ , l'espace d'états ( $n!$ ) croît de manière super-exponentielle, rendant les algorithmes classiques de recherche de chemin le plus court comme la recherche en largeur (BFS) intraitables. De plus, le diamètre conjecturé du graphe est de $\Theta(n^2)$ , ce qui accentue la difficulté.

2. Méthodologie : Intersection de Cycles Itérative (ICI)
Le document propose une stratégie fondamentalement différente de l'exploration de graphe niveau par niveau : l'algorithme d'Intersection de Cycles Itérative (ICI). Au lieu d'étendre le front de recherche de manière uniforme, l'ICI génère des « cycles » aléatoires à partir des états de départ et de cible, et recherche une intersection entre ces familles de cycles.

L'algorithme fonctionne par cycles itératifs, maintenant deux magasins d'états ( $S$ et $F$ ) s'étendant à partir de l'état de départ ( $\sigma_s$ ) et de l'état final ( $\sigma_f$ ), respectivement. Chaque cycle se compose de quatre phases :

Génération de Combinaisons Aléatoires : Un lot de séquences d'opérations aléatoires (mots) de longueur $\ell$ est généré.
Expansion de Cycle : Pour chaque séquence, l'algorithme calcule le cycle complet d'états générés par l'application répétée de la permutation composée jusqu'à ce qu'elle revienne à la graine (seed). Tous les états intermédiaires sont enregistrés dans le magasin respectif.
Vérification d'Intersection : L'algorithme vérifie la présence d'états partagés entre $S$ et $F$ en utilisant des recherches indexées par hachage. Si une intersection $\sigma^*$ est trouvée, le chemin est reconstruit en remontant les chaînes de cycles vers les origines.
Sélection de Pont : Si aucune intersection ne se produit, l'algorithme sélectionne des « états de pont » pour redémarrer l'expansion. Les états de $S$ sont classés par leur distance à $\sigma_f$ , et les états de $F$ sont classés par leur distance à $\sigma_s$ . Les 10 états les plus proches de chaque côté sont considérés, et l'un d'eux est choisi aléatoirement de chaque côté pour servir de nouvelle graine pour le cycle suivant.

Reconstruction et Raffinement du Chemin :
Lorsqu'une intersection est trouvée, le chemin complet est assemblé en chaînant les segments à travers tous les cycles. Le document note que le chemin résultant n'est pas garanti d'être le plus court. Pour y remédier, le package inclut une étape de post-traitement (short path bfs) qui effectue des « sauts » de BFS locaux à profondeur limitée pour remplacer les segments intermédiaires par des routes plus courtes.

Stratégie Hybride (Réseau de Transport Basé sur des Hubs) :
Pour les instances plus larges, le document décrit une approche hybride (find_path_bfs). Cette méthode construit d'abord des « arbres d'autoroutes » clairsemés en utilisant un BFS à profondeur limitée depuis les deux extrémités afin d'identifier des états « hubs ». Elle sélectionne ensuite la paire de hubs la plus proche et invoque l'algorithme ICI pour combler l'écart entre eux. Cela réduit la distance de recherche effective avant que la phase d'intersection de cycles stochastique ne commence.

3. Contributions Clés
Le document expose trois contributions principales :

L'Algorithme ICI : Une nouvelle stratégie de recherche de chemin pour les graphes de Cayley des groupes de permutations qui repose sur l'intersection de cycles et la sélection de ponts guidée par la distance, plutôt que sur une expansion exhaustive de niveau.
Le Package cayleyR : Un package R open-source (avec un backend C++ via Rcpp) implémentant l'algorithme. Les fonctionnalités clés incluent :
- Stockage d'états indexé par hachage pour une insertion et une recherche en $O(1)$ amorti.
- Accélération optionnelle par GPU Vulkan pour le traitement par lots des transformations d'états et les calculs de distance par paires.
- « Coordonnées célestes », un plongement géométrique du nombre d'opérations sur une sphère pour la visualisation et une future utilisation heuristique.
Démonstrations de Scalabilité : Des expériences computationnelles montrant la capacité de l'algorithme à résoudre des instances de TopSpin allant jusqu'à $n=20$ , une échelle auparavant difficile pour les solveurs exacts.

4. Résultats Expérimentaux
Les auteurs présentent des benchmarks sur une station de travail Linux (AMD Ryzen 5 5600) utilisant cayleyR version 0.1.0/0.2.1 :

Critères de Classement : Le choix de la manière de classer les séquences d'opérations aléatoires impacte significativement la performance. Le critère « le plus unique » (priorisant les séquences qui visitent le plus d'états distincts) a obtenu le taux de succès le plus élevé (83 % sur 12 instances, $n=14\text{--}30$ ) mais a souvent produit des chemins très longs. Inversement, les séquences « les plus répétées » ont offert une grande fiabilité (75 % de succès) avec des chemins systématiquement plus courts et des temps de recherche rapides (médiane < 1s).
Scalabilité avec la Distance de Mélange (Scramble Distance) : Sur TopSpin(14, 4) avec des distances de mélange variables ( $n_{moves}=20\text{--}150$ ), l'algorithme a résolu les 14 instances. Le temps de recherche moyen était de 1,12 seconde, et le temps total (incluant le raccourcissement du chemin) était en moyenne de 2,3 secondes. Le nombre de cycles ICI requis n'était pas corrélé de manière monotone avec la distance de mélange, soulignant la nature stochastique de la méthode.
Scalabilité avec la Taille du Puzzle ( $n$ ) : Sur des instances avec $n=10\text{--}16$ et une distance de mélange fixe, les temps de recherche sont restés sous la barre des 0,5 seconde. Les auteurs attribuent cela au fait que l'algorithme ne matérialise qu'une petite fraction de l'espace d'états, ce qui le rend moins sensible à la croissance super-exponentielle de $n!$ par rapport au BFS.

5. Signification et Revendications
Le document positionne cayleyR comme un outil pratique pour résoudre des puzzles de permutations qui dépassent les limites de la recherche exhaustive classique. Sa signification réside dans :

Efficacité : Il évite les goulots d'étranglement de mémoire et de temps des bases de données de motifs et du BFS en utilisant la génération de cycles aléatoires et l'intersection par hachage.
Scalabilité : Il traite avec succès des instances allant jusqu'à $n=20$ , où l'espace d'états est de $20!$ .
Modularité : Bien qu'actuellement adapté à TopSpin, les auteurs affirment que le cadre sous-jacent (intersection de cycles, sélection de pont, magasins indexés par hachage) est applicable à d'autres puzzles de permutation (ex: tri de crêpes, Hungarian Rings) pourvu qu'ils puissent être modélisés comme des graphes de Cayley.

Les auteurs restent modestes quant à l'optimalité des solutions, reconnaissant que l'ICI ne garantit pas les chemins les plus courts et que le plongement des « coordonnées célestes » est actuellement un outil de visualisation expérimental plutôt qu'une heuristique prouvée pour l'estimation de distance. Des travaux futurs sont proposés pour explorer les cadres de dualité holographique pour l'intersection de cycles et pour généraliser l'interface du générateur pour des classes de puzzles plus larges.

Le Puzzle du Labyrinthe Infini

Le Papier : Jeter des fléchettes dans le noir

Ce que le papier a réellement découvert

Ce que le papier écarte (et ce qu'il ne fait pas)

L'essentiel

Articles similaires