🤖 AI

CayleyR: Solving the TopSpin puzzle via cycle intersection

Dit artikel introduceert cayleyR, een R-package die de TopSpin(n,k) permutatiepuzzel oplost door gebruik te maken van een iteratieve bidirectionele zoektocht met cyclusintersectiedetectie in Cayley-grafen, verbeterd door C++ hashing en optionele Vulkan GPU-acceleratie.

Oorspronkelijke auteurs: Yuri Baramykov

Gepubliceerd 2026-07-16

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yuri Baramykov

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Raadsel van de Oneindige Doolhof

Stel je voor dat je in een enorm, onzichtbaar doolhof staat waar elke afslag die je neemt de hele lay-out van de wereld om je heen verandert. Dit is niet zomaar een spel van "links of rechts"; het is een spel van permutaties, een tak van de wiskunde genaamd groepentheorie, die bestudeert hoe dingen kunnen worden herschikt. Denk aan een kaartspel: als je ze schudt, creëer je een nieuwe volgorde. Als je ze nog een keer schudt, creëer je weer een andere. De "Cayley-graaf" is een kaart van elke mogelijke volgorde waarin die kaarten kunnen zijn, verbonden door de zetten die je maakt om van de ene naar de andere volgorde te gaan.

Het specifieke puzzel waar dit artikel over gaat, heet TopSpin. Stel je een cirkelvormig spoor voor met genummerde tokens (zoals kralen aan een ketting) en een venster dat een paar van hen kan omdraaien. Je kunt het hele spoor laten draaien of de tokens in het venster omdraaien. Het doel is simpel: de kralen van een rommelige bende terugbrengen naar hun perfecte, genummerde volgorde. Het probleem is dat naarmate je meer kralen toevoegt, het aantal mogelijke arrangementen explodeert. Voor slechts 20 kralen zijn er meer manieren om ze te arrangeren dan er atomen in het universum zijn. Traditionele computermethoden, die proberen elk pad één voor één te controleren, raken bijna onmiddellijk verdwaald in dit oneindige doolhof. Dit artikel introduceert een nieuwe manier om dat doolhof te navigeren, niet door elke weg te bewandelen, maar door pijlen te werpen en te hopen dat er twee op dezelfde plek landen.

Het Papier: Pijlen Werpen in het Donker

In dit artikel introduceert Yuri Baramykov een nieuwe softwaretool genaamd cayleyR en een slimme strategie om de TopSpin-puzzel op te lossen, zelfs wanneer de puzzel enorm groot is. In plaats van te proberen de hele doolhof van begin tot eind in kaart te brengen, gebruikt de auteur een methode genaamd Iterative Cycle Intersection (ICI).

Zo werkt het, met een speelse analogie: Stel je voor dat jij en een vriend verdwaald zijn in een gigantisch, cirkelvormig bos (de Cayley-graaf). Jullie beginnen aan tegenovergestelde kanten en willen elkaar in het midden ontmoeten.

De Oude Manier: Jullie proberen alle paden stap voor stap te bewandelen en elke boom die jullie zien te markeren. Dit duurt eeuwig omdat het bos te groot is.
De cayleyR-manier: In plaats van voorzichtig te wandelen, pakken jullie beiden een handvol "magische zaden" (willekeurige reeksen zetten). Jullie planten ze en kijken hoe ze groeien tot gigantische, lussen vormende ranken (cycli). Omdat het bos circulair is, komen deze ranken uiteindelijk weer bij zichzelf uit.
De Intersectie: Jullie blijven deze zaden werpen en ranken laten groeien. Uiteindelijk zal een van jouw ranken het pad van een van je vrienden kruisen. Wanneer ze elkaar raken, heb je een ontmoetingspunt gevonden! Je kunt dan het pad volgen vanaf je start, langs je rank, naar het ontmoetingspunt, en vervolgens de rank van je vriend achterstevoren volgen naar hun startpunt.

Het artikel legt uit dat deze "rank-groei"-strategie veel sneller is dan het bewandelen van elk pad. De software genereert willekeurige reeksen zetten, berekent de lussen die ze creëren en controleert of een van die lussen overlapt met de lussen die vanuit de andere kant worden gegenereerd. Als ze niet meteen overlappen, kiest de software de twee ranken die het dichtst bij elkaar liggen (met behulp van een "afstandsgids") en begint vanaf die punten nieuwe ranken te laten groeien. Dit proces wordt herhaald totdat de twee kanten elkaar ontmoeten.

Wat het Papier Eigenlijk Vond

De auteur heeft niet alleen het idee uitgevonden; hij heeft een werkend computerprogramma gebouwd om het te testen. Hier is wat de experimenten lieten zien:

Het werkt op grote puzzels: De software loste TopSpin-puzzels met tot wel 20 tokens succesvol op (waarbij het aantal mogelijke arrangementen 20 faculteit is, of ongeveer 2,4 quintiljoen). Dit is een omvang die traditionele computers zou laten crashen.
Het is snel: In tests met 14 tokens vond de computer een oplossing in een gemiddelde van 1,12 seconden. Zelfs de moeilijkste puzzels in de test werden opgelost in minder dan 3s,5 seconden.
Niet alle zaden zijn gelijk: Het papier testte verschillende manieren om te kiezen welke "magische zaden" (willekeurige bewegingsreeksen) te planten. Ze ontdekten dat het kiezen van reeksen die de meeste unieke plekken bezoeken (de "meest unieke") het meest waarschijnlijk een oplossing vindt (het lost 83% van de testgevallen op), maar de paden die het vond waren soms erg lang. Het kiezen van reeksen die steeds weer dezelfde plekken bezoeken ("meest herhaald"), was de meest betrouwbare methode om korte paden snel te vinden.
Het is niet perfect: Het artikel is zeer duidelijk dat de gevonden paden niet noodzakelijkerwijs het kortst mogelijke pad zijn. Het algoritme vindt een pad, niet altijd het beste pad. De software bevat echter een "post-processing"-stap die probeert het pad achteraf in te korten, wat soms het aantal zetten met de helft vermindert.

Wat het Papier Uitsluit (en Wat Het Niet Doet)

Het is belangrijk om te weten wat dit papier niet zegt te doen:

Het is geen garantie voor het kortste pad: De auteur geeft expliciet aan dat het Iterative Cycle Intersection-algoritme niet de kortste route garandeert. Het vindt een oplossing, maar het kan een omweg nemen.
Het is nog geen wondermiddel voor elke puzzel: De huidige versie van de software is specifief ontworpen voor de TopSpin-puzzel. Hoewel de auteur suggereert dat het idee ook voor andere puzzels zou kunnen werken (zoals pancake sorting), bewijst het artikel alleen dat het werkt voor TopSpin.
Het "holografische" idee is slechts een gok: Het papier noemt een fancy nieuwe theorie genaamd "holografische dualiteit" die kan helpen om deze puzzels te visualiseren als vormen op een sfeer. De auteur geeft echter toe dat dit speculatief is. Er staat dat het "nog verkend moet worden" en dat de huidige versie van de software dit alleen gebruikt voor mooie plaatjes, niet om de puzzel daadwerkelijk op te lossen.

De Kern van het Verhaal

Dit artikel presenteert een nieuwe, speelse en zeer effectieve manier om een zeer moeilijke wiskundige puzzel op te lossen. Door te stoppen met de poging om de hele wereld in kaart te brengen en in plaats daarvan te zoeken naar waar twee willekeurige paden elkaar kruisen, kan de cayleyR-software TopSpin-puzzels met 20 tokens in slechts enkele seconden oplossen. Het is een herinnering dat je in een gigantisch doolhof niet altijd elke afslag hoeft te kennen; je hoeft alleen maar een plek te vinden waar twee wandelende paden elkaar toevallig ontmoeten. De software is gratis beschikbaar voor iedereen die het wil proberen, hoewel de auteur waarschuwt dat hoewel het snel oplossingen vindt, het niet altijd de perfecte vindt.

Technische Samenvatting: CAYLEYR: HET OPLOSSEN VAN DE TOPSPIN-PUZZEL VIA CYCLUSINTERSECTIE

1. Probleemstelling
Het artikel behandelt de computationele uitdaging van het oplossen van de TopSpin $(n, k)$ -puzzel, een permutatiepuzzel bestaande uit $n$ tokens op een circulaire baan en een draaipoortvenster met breedte $k$ . Het doel is om een gegeven initiële permutatie te transformeren naar een doelpermutatie met behulp van twee primaire bewegingen: een cyclische verschuiving van de gehele baan (Links $L$ of Rechts $R$ ) en een omkering van de $k$ tokens binnen het venster ( $X_k$ ).

Algebraïsch gezien komt de toestandsruimte overeen met de Cayley-graaf $\Gamma(G, \{L, R, X_k\})$ , waarbij $G$ de symmetrische groep $S_n$ is (voor even $k$ ) of de alternerende groep $A_n$ (voor oneven $k$ ). Het oplossen van de puzzel komt neer op het vinden van een pad tussen twee knopen in deze graaf. De auteurs merken op dat voor $n > 10$ de toestandsruimte ( $n!$ ) superexponentieel groeit, waardoor klassieke kortste-pad-algoritmen zoals Breadth-First Search (BFS) onhandelbaar worden. Bovendien is de geconstateerde diameter van de graaf $\Theta(n^2)$ , wat de moeilijkheid vergroot.

2. Methodologie: Iteratieve Cyclusintersectie (ICI)
Het artikel stelt een fundamenteel andere strategie voor dan de niveau-voor-niveau graafverkenning: het Iteratieve Cyclusintersectie (ICI) algoritme. In plaats van de zoekfrontier uniform uit te breiden, genereert ICI willekeurige "cycli" vanaf zowel het start- als het doeltoestand, en zoekt naar een intersectie tussen deze families van cycli.

Het algoritme werkt in iteratieve rondes en onderhoudt twee toestandsopslagplaatsen ( $S$ en $F$ ) die uitwaaieren vanuit respectievelijk de starttoestand ( $\sigma_s$ ) en de eindtoestand ( $\sigma_f$ ). Elke ronde bestaat uit vier fasen:

Generatie van willekeurige combinaties: Een batch willekeurige operatiesequenties (woorden) van lengte $\ell$ wordt gegenereerd.
Cyclusexpansie: Voor elke sequentie berekent het algoritme de volledige cyclus van toestanden die wordt gegenereerd door de samengestelde permutatie herhaaldelijk toe te passen totdat deze terugkeert naar de zaadtoestand (seed). Alle tussenliggende toestanden worden in de respectievelijke opslagplaats geregistreerd.
Intersectiecontrole: Het algoritme controleert op gedeelde toestanden tussen $S$ en $F$ met behulp van hash-geïndexeerde lookups. Indien een intersectie $\sigma^*$ wordt gevonden, wordt het pad gereconstrueerd door de cyclusketens terug te volgen naar de oorsprong.
Brugselectie: Als er geen intersectie optreedt, selecteert het algoritme "brugtoestanden" om de expansie te herstarten. Toestanden in $S$ worden gerangschikt op basis van hun afstand tot $\sigma_f$ , en toestanden in $F$ op basis van hun afstand tot $\sigma_s$ . De 10 dichtstbijzijnde toestanden aan elke zijde worden overwogen, en er wordt willekeurig één uit elk wordt gekozen om als de nieuwe zaadtoestand voor de volgende ronde te dienen.

Padreconstructie en Verfijning:
Wanneer een intersectie wordt gevonden, wordt het volledige pad samengesteld door de segmenten over alle rondes heen te ketenen. De auteurs merken op dat het resulterende pad niet gegarandeerd het kortste is. Om dit aan te pakken, bevat het pakket een post-verwerkingsstap (short path bfs) die lokale, dieptebeperkte BFS "sprongen" uitvoert om tussenliggende segmenten te vervangen door kortere routes.

Hybride Strategie (Hub-gebaseerd Transportnetwerk):
Voor grotere instanties beschrijft het artikel een hybride benadering (find_path_bfs). Deze methode bouwt eerst ijle "snelwegbomen" met behulp van beperkte diepte BFS vanaf beide eindpunten om "hub"-toestanden te identificeren. Vervolgens selecteert het het dichtstbijzijnde paar hubs en roept het ICI aan om de kloof tussen hen te overbruggen. Dit vermindert de effectieve zoekafstand voordat de stochastische cyclusintersectiefase begint.

3. Belangrijkste Bijdragen
Het artikel schetst drie hoofd bijdragen:

Het ICI Algoritme: Een nieuwe padvindingsstrategie voor Cayley-grafen van permutatiegroepen die berust op cyclusintersectie en afstand-gestuurde brugselectie in plaats van uitputtende niveau-expansie.
Het cayleyR Pakket: Een open-source R-pakket (met een C++ backend via Rcpp) dat het algoritme implementeert. Belangrijke kenmerken zijn:
- Hash-geïndexeerde toestandsopslag voor $O(1)$ geamortiseerde insertie en lookup.
- Optionele Vulkan GPU-acceleratie voor batch toestands-transformaties en paarwijze afstandsberekeningen.
- "Hemelse coördinaten", een geometrische embedding van operatie-aantallen op een sfeer voor visualisatie en potentieel toekomstig heuristisch gebruik.
Schaalbaarheidsdemonstraties: Computationele experimenten die de bekwaamheid van het algoritme tonen om TopSpin-instanties met $n$ tot 20 op te lossen, een schaal die voorheen moeilijk was voor exacte solvers.

4. Experimentele Resultaten
De auteurs presenteren benchmarks op een Linux workstation (AMD Ryzen 5 5600) met behulp van cayleyR versie 0.1.0/0.2.1:

Rangschikkingscriteria: De keuze van hoe willekeurige operatiesequenties te rangschikken heeft een significante impact op de prestaties. Het criterium "meest uniek" (prioriteit geven aan sequenties die de meeste verschillende toestanden bezoeken) bereikte het hoogste succespercentage (83% op 12 instanties, $n=14\text{--}30$ ) maar produceerde vaak zeer lange paden. Daarentegen boden "meest herhaalde" sequenties een hoge betrouwbaarheid (75% succes) met consistent korte paden en snelle zoektijden (mediaan < 1s).
Schaalbaarheid met Scramble Afstand: Op TopSpin(14, 4) met variërende scramble afstanden ( $n_{moves}=20\text{--}150$ ), loste het algoritme alle 14 instanties op. De gemiddelde zoektijd was 1,12 seconden, waarbij de totale tijd (inclusclusief padverkorting) gemiddeld 2,3 seconden bedroeg. Het aantal vereiste ICI-cycli correleerde niet monotoon met de scramble afstand, wat de stochastische aard van de methode benadrukt.
Schaalbaarheid met Puzzelgrootte ( $n$ ): Op instanties met $n=10\text{--}16$ en een vaste scramble afstand, bleven de zoektijden onder de 0,5 seconden. De auteurs wijten dit aan het feit dat het algoritme slechts een klein fractie van de toestandsruimte materialiseert, waardoor het minder gevoelig is voor de superexponentiële groei van $n!$ vergeleken met BFS.

5. Betekenis en Claims
Het artikel positioneert cayleyR als een praktisch hulpmiddel voor het oplossen van permutatiepuzzels die de limieten van klassieke exhaustieve zoekopdrachten overschrijden. De betekenis ligt in:

Efficiëntie: Het vermijdt de geheugen- en tijd-bottlenecks van patronendatabases en BFS door het gebruik van willekeurige cyclusgeneratie en hash-gebaseerde intersectie.
Schaalbaarheid: Het handelt succesvol instanties tot $n=20$ af, waarbij de toestandsruimte $20!$ is.
Modulariteit: Hoewel momenteel specifiek afgestemd op TopSpin, beweren de auteurs dat het onderliggende framework (cyclusintersectie, brugselectie, hash-geïndexeerde opslagplaatsen) toepasbaar is op andere permutatiepuzzels (bijv. pancake sorting, Hungarian Rings), mits deze als Cayley-grafen gemodelleerd kunnen worden.

De auteurs blijven bescheiden over de optimaliteit van de oplossingen, waarbij ze erkennen dat ICI geen kortste paden garandeert en dat de "hemelse coördinaten" embedding momenteel een experimenteel visualisatietool is in plaats van een bewezen heuristiek voor afstandsbepaling. Toekomstig werk wordt voorgesteld om holografische dualiteitsframeworks voor cyclusintersectie te verkennen en om de generator-interface te generaliseren voor bredere klassen van puzzels.

Het Raadsel van de Oneindige Doolhof

Het Papier: Pijlen Werpen in het Donker

Wat het Papier Eigenlijk Vond

Wat het Papier Uitsluit (en Wat Het Niet Doet)

De Kern van het Verhaal

Meer zoals dit