Artikel top billede

(Foto: Computerworld)

Sådan klarer man Rubiks terning

Det kan tage uger at ordne terningen, hvis man ikke har en stærk algoritme.

Af Redaktionen, Alt om Data

Denne artikel er oprindeligt bragt på Alt om Data. Computerworld overtog i november 2022 Alt om Data. Du kan læse mere om overtagelsen her.

Vi har alle set algoritmer til at ordne Rubiks terning ved at gå trinvis frem: Først tager man alle hjørnerne, så går man i gang med siderne. Eller: lav en komplet side, så tag den næste og så den næste.

Der er flere metoder, og ved hjælp af nogle ret rigoristiske teknikker kan eksperterne klare terningen på under et minut. Men hvor rodet kan en terning blive? Eller med andre ord: Hvad er det mindste antal ændringer, der kræves? Skriv Guds algoritme.

For år tilbage havde Kings College i London en tradition for, at det matematiske institut hvert år afholdt en weekendtur til Windsors park. Der blev inviteret foredragsholdere, som talte om emner, der ellers ikke indgik i matematikundervisningen.

Ryd terningen

I 1979 var professor David Singmaster gæsteforelæser. Hans emne var et splinternyt legetøj, der hed Rubiks terning – den var endnu ikke kommet på markedet – og brugen af kombinationslære til at ordne den. Terningen var blevet opfundet af Erno Rubik i Ungarn cirka fem år tidligere, og på det tidspunkt stod Ideal Toys over for at lancere terningen verden over.

Singmaster havde terninger med, som de studerende kunne købe, og efter foredraget solgte han naturligvis dem alle. I løbet af et par måneder var vi så trænede, at vi kunne klare en terning på få minutter.

Eftersom de studerede matematik, forstod de matematikken bag terningen. Den oprindelige løsning, som Singmaster opdagede, brugte kombinationslære til at ordne den.

Han havde udviklet en række kombinerede bevægelser (hver af dem omfattede mellem syv og tolv rotationer), der bevægede tre hjørner på tre sider. Alle bevægelserne fulgte formen aba’ – det vil sige en række rotationer, a, efterfulgt af en enkelt rotation, b, fulgt af den omvendte række rotationer, der udgjorde a.

I stedet for planløst at bevæge vilkårligt skulle bevægelserne kun skifte position for tre underterninger. Ved at finde tre underterninger, der var ude af position, kunne man ordne terningen ved gentagne gange at foretage disse bevægelser.

Man kunne to bevægelser udenad – en til at skifte tre hjørner, en til at skifte tre sideunderterninger – indtil man kunne gøre det i søvne. Det betød, at man kunne klare en vilkårlig position på omkring to minutter. Det er ikke vanvittigt imponerende, men det er acceptabelt.

Der var stadig to ubesvarede spørgsmål: Hvor randomiseret kunne man gøre terningen, og hvad var det optimale antal bevægelser, som en almægtig terningløser – med andre ord en terningløser, der kunne lave en ideel analyse af terningen – skulle bruge for at få terningen tilbage i standardtilstanden?

Løsningen krævede naturligvis mange bevægelser – måske 100 – men hvad nu, hvis man kunne visualisere løsningen ideelt? 10? 20? 42?

Den optimale terninganalyse blev kendt som Guds algoritme. Ikke fordi der nødvendigvis findes sådan en algoritme, men fordi den giver os noget at stræbe efter i vores bestræbelser på at lave stadig bedre algoritmer.

I 1982 forudså Singmaster, at Guds algoritme måske kun krævede få bevægelser (»først i tyverne«), men han kunne ikke udvikle sin hypotese meget længere.

Den magiske terning

Før vi kan begynde at ordne terningen, må vi have en notation, så vi ikke drukner i beskrivende vendinger. I dag bruger vi stadig den samme notation, som Singmaster præsenterede i 1982 i sin bog Notes on Rubik’s Magic Cube.

Terningen består af tre former for underterninger, der er samlet som ved trylleri i en terning på 3×3×3. Der er 12 kant-underterninger, hver med to sider med forskellige farver. Der er også otte hjørne-underterninger, hver med tre synlige sider, der hver har sin farve.

Endelig er der seks center-underterninger, der hver har en side. De centrale kvadrater udgør en affjedret matrix, der holder det hele sammen. Disse centrale dele definerer farven på deres sider, når terningen er ordnet.

Hold terningen foran dig, så en enkelt side vender mod dig. Terningens seks sider hedder Front, Bagside, Venstre, Højre, Op og Ned. Vi bruger Op og Ned i stedet for Top og Bund, fordi vi skal bruge forbogstaverne til at angive bevægelserne på de forskellige sider, og det ville være forvirrende både at tale om Bagside og Bund. Bogstaverne F, B, V, H, O og N betegner en kvart rotation med uret.

Med uret gælder den retning, man roterer siden på, når man ser direkte på den. En halv rotation bliver betegnet ved enten at gentage bogstaver (for eksempel FF eller OO) eller ved at opløfte bogstavet til anden potens (for eksempel B2 eller H2).

En kvart rotation mod uret betegnes ved hjælp af en apostrof (for eksempel N’ eller V’). En kvart rotation mod uret kunne naturligvis betegnes ved at gentage et bogstav tre gange, men det ses sjældent.

Brug hjernen

Som et eksempel viser vi her, hvordan man får det simple korsmønster fra en standardterning: V2H2O2N2F2B2 (eller VVHHOONNFFBB). Hvis man vil tilbage til den ordnede terning, skal man blot gøre bevægelserne omvendt.

For at få det raffinerede centerprikmønster kan man prøve V’H·O’N·B’F·V’H (her har vi delt bevægelserne op i par for at gøre det nemmere at se, hvad der sker). Hvis man vil tilbage til den oprindelige terning, skal man igen gøre bevægelserne omvendt.

Singmasters oprindelige løsning bestod af tre hovedtrin: For det første vælger man en farve (vi satser altid på hvid, for det er den mest synlige), og så gendanner man den pågældende side. Det gør man normalt ved først at gendanne kant-underterningerne og derefter hjørne-underterningerne.

For det andet skal man gendanne det midterste lag. Det betyder naturligvis, at man skal sikre sig, at de fire kant-underterninger sidder rigtigt, og at de vender den rigtige vej.

For det tredje skal man gendanne den sidste side. Singmaster gjorde det i fire hovedfaser: Vend kant-underterningerne, så de alle viser den endelige farve og danner et kors med den centrale underterning (de kan naturligvis være i en forkert position); gendan kant-underterningerne til deres rigtige position; anbring hjørne-underterningerne i deres rigtige position (selv om de kan vende den forkerte vej), drej hjørnerne, indtil de vender den rigtige vej.

Singmasters algoritme gav garanti for at ordne terningen, men antallet af bevægelser var på ingen måde optimalt. Det kunne tage over 100 bevægelser at ordne terningen med hans algoritme.

Efter at Singmaster havde offentliggjort sin algoritme (en løsning, der krævede, at man lærte seks grundlæggende bevægelser og gentog dem igen og igen), gik det vilde ridt for at reducere antallet af bevægelser, så man kunne ordne terningen hurtigere.

Kort efter at Singmaster udgav sin første bog, udviklede Jessica Fridrich en firdelt algoritme kaldet CFOP (Cross, First two laywers, Orient last layer, Permute last layer), der viste sig at være ekstremt hurtig til den nye sport, der indebar hurtig løsning af terningen i konkurrencer.

Desværre kræver denne algoritme kendskab til 120 bevægelser, men en øvet terningløser kan analysere og ordne en randomiseret terning med omkring 50 rotationer.

Tempoet stiger

Philip Marshall (www.helm.lu/cube/MarshallPhilipp) beskrev nu en algoritme, der kun krævede to bevægelser (plus kunsten at vide, hvornår man skulle bruge dem), men den kunne ordne terningen på omkring 65 bevægelser.

Processen består af fem trin: kors, centersektionens kanter, topkanterne, fem hjørnedele, slut. Så kom Lars Petrus’ metode, som han udviklede i begyndelsen af 1980’erne.

Han valgte at undgå den traditionelle lagdelte teknik, som alle andre brugte, og gendanne terningen fra et hjørne, idet han byggede den ud via en løst 2×2×2-terning til en 2×2×3-rektangulær blok (også kaldet en cuboid) til den færdige terning.

Selv om de første få passager bruger adskillige slags bevægelser, bruger de sidste trin i Petrussystemet kun tre. Hele terningen kan ordnes med 45 bevægelser, forudsat at man har tid til at iagttage terningen på forhånd.

I fartkonkurrencer stiger antallet af bevægelser til omkring 60, fordi der er mindre tid til at iagttage terningen og udtænke den mest effektive løsning.

Bortset fra nogle justeringer af disse metoder i årenes løb er her, vi menneskelige terningløsere står i dag. De hurtigste terningløsere bruger varianter af disse metoder. Men hvad med computerløsninger? Kan de komme tættere på Guds algoritme ved omfattende analyser af den randomiserede terning?

De første forsøg blev gjort af professor Morwen B. Thistlethwaite, samtidig med at Singmaster udlagde sin metode, og de blev offentliggjort i Scientific American i 1981 af Douglas Hofstadter.

Thistlethwaite delte løsningsprocessen op i underproblemer. I stedet for at koncentrere sig om at løse dele af terningen, idet man bestræbte sig på ikke at lave ulykker, mens man ordnede resten af terningen, fokuserede han på de bevægelser, man havde lov til at foretage. Til det formål brugte han gruppeteori og computersøgning.

Han begyndte med den såkaldte terninggruppe. Det er en matematisk gruppe, hvis operationer er alle de sædvanlige bevægelser, vi har nævnt her: F, B, V, H, O, N og de bevægelser, man kan uddrage af dem (F2, F’, B2, B’ og så videre).

Antallet af mulige positioner i denne terninggruppe er enormt: 4,3× 1.019. Nu anbragte han en mindre gruppe, der kun tillod disse bevægelser: V, H, F, B, O2 og N2.

Dernæst udarbejdede han et sæt tabeller over bevægelser, der førte terningen fra den store gruppe til den mindre gruppe. I denne mindre gruppe udtænkte han en endnu mindre gruppe, der kun tillod V, H, F2, B2 og N2 og regnede så ud, hvordan han kunne overføre terningen til et medlem af denne gruppe.

Derfra gik han til den næste mere restriktive gruppe, der kun tillod V2, H2, F2, B2, O2 og N2. Fra denne gruppe førte en kort søgning til den sidste og mindste af alle grupperne: identitetsgruppen (den løste terning).

Det er vigtigt at huske, at Thistlethwaites algoritme kræver mange søgninger ved hvert trin ned af gruppekæden, og den kan kun udføres af computere, ikke af mennesker. Ved hjælp af denne algoritme kan man ordne terningen med højst 51 bevægelser.

Tæt på Guds algoritme

Den seneste forbedring blev udført af Herbert Kociemba i 1992 (www.kociemba.org/cube.htm). Han byggede sin algoritme på Thistlethwaites, idet han fjernede de fleste af de mellemliggende grupper.

Kociembas algoritme brugte kun tre grupper: Terninggruppen, gruppen O, N, F2, B2, V2 og H2 og identitetsgruppen. Han kaldte den for en tofase-algoritme, fordi man transformerer terningen til et medlem af den mindre gruppe, hvorefter man transformerer den til det eneste medlem af identitetsgruppen.

Det vigtige ved gruppen O, N, F2, B2, V2 og H2 er, at hjørnernes retninger ikke kan ændres med disse handlinger. Desuden forbliver kanterne i mellemstykket mellem Op og Ned i dette stykke.

Den første fase bruger en modificeret A*-søgealgoritme, der kaldes iterative deepening A* (eller IDA), til at finde de bevægelser, der kan tvinge hjørnerne og kanterne (og midterstykket) til at passe ind i den anden gruppe. Så søger den anden fase efter de bevægelser, der kan ordne terningen ved kun at bruge de begrænsede bevægelser, der er tilladt.

Faktisk er algoritmen lidt mere raffineret, end den umiddelbart ser ud til. Den ordner terningen flere gange for at finde den kortest mulige vej.

Først bruger den den korteste vej, som den første søgning gav, og transformerer den deraf følgende terning til den ordnede tilstand.

Så bruger den mindre vellykkede veje fra den oprindelige søgning og prøver at transformere dem til den ordnede tilstand.

Efter at have udført denne proces vælger den den korteste vej som løsningen. Normalt finder den en vej på 20 bevægelser eller mindre til at ordne terningen.

Bemærk dog, at den korteste vej, som den finder, ikke nødvendigvis er den optimale løsning. Derfor kan Kociembas algoritme, der ganske vist er meget effektiv, kun nærme sig Guds algoritme. Den venter vi stadig på.

En af de mere djævelske varianter er sudokuterningen. Farverne er væk, de er blevet erstattet af tallene fra 1 til 9. Målet er at sikre, at alle tallene forekommer på hver af de seks sider.

For at løse denne opgave skal man være velbevandret i de bevægelser, der skal til for at ordne Rubiks terning. Disse bevægelser er nemlig beregnet til at flytte visse kanter eller hjørner uden at gøre skade på resten af den delvis ordnede terning.

På sudokuterningen definerer center-underterningerne tallenes orientering i det ordnede puslespil. De hjælper også med at definere hjørne-underterningerne, så det næste skridt består i at regne ud, hvor de otte hjørne-underterninger skal hen (både tallene på underterningerne og deres orientering hjælper her), og bruge bevægelserne til at flytte dem hen i den korrekte position og orientering.

Til sidst gælder det om at finde de 12 kant-underterningers placering og orientering. Hvis du bruger de bevægelser, du har øvet dig på, burde du kunne flytte dem uden at forstyrre hjørne-underterningerne.

[themepacific_accordion]
[themepacific_accordion_section title="Fakta"]

Bevægelser i mellemstykket

[/themepacific_accordion_section]
[themepacific_accordion_section title="Fakta"]

Terninger af forskellig størrelse

[/themepacific_accordion_section]
[themepacific_accordion_section title="Fakta"]

Snoede centre

[/themepacific_accordion_section]
[/themepacific_accordion]