Rubiks terning matematik

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. juli 2021; checks kræver 17 redigeringer .

Rubiks terning matematik

Mediefiler på Wikimedia Commons

Mathematics of the Rubik's Cube er et sæt matematiske metoder til at studere egenskaberne af Rubik's Cube fra et abstrakt matematisk synspunkt. Denne gren af matematik studerer kubesamlingsalgoritmer og evaluerer dem. Baseret på grafteori , gruppeteori , beregnelighedsteori og kombinatorik .

Der er mange algoritmer designet til at overføre Rubik's Cube fra en vilkårlig konfiguration til den endelige konfiguration (den samlede terning). I 2010 blev det strengt bevist, at ikke mere end 20 drejninger af fladerne er tilstrækkelige til at overføre Rubik's Cube fra en vilkårlig konfiguration til en samlet konfiguration (ofte kaldet "samling" eller "løsning") [1] . Dette tal er diameteren på Cayley-grafen for Rubiks terninggruppen [2] . I 2014 blev det bevist, at 26 træk altid er nok til at løse Rubik's Cube ved kun at bruge 90° drejninger af fladerne [3] .

En algoritme, der løser et puslespil i det mindst mulige antal træk, kaldes Gud -algoritmen .

Notation

Denne artikel bruger "Singmaster-notation" [4] [5] udviklet af David Singmaster og udgivet af ham i 1981 for at angive rotationssekvensen af ansigterne på en 3×3×3 Rubiks terning .

Bogstaverne repræsenterer 90° drejning med uret af henholdsvis venstre ( venstre ), højre ( højre ), front ( foran ), bagside ( bagside ), top ( op ) og bund ( ned ) sider. 180° drejninger er angivet ved at tilføje et 2 til højre for bogstavet, eller ved at tilføje et hævet 2 til højre for bogstavet. En 90° rotation mod uret angives ved at tilføje en tankestreg ( ′ ) eller tilføje en hævet skrift -1 til højre for bogstavet. Så for eksempel er posterne og ækvivalente, såvel som indtastningerne og . $L,R,F,B,U,D$ $L^{2}$ $L2$ $L'$ $L^{{-1}}$

Konfiguration Graph Metrics

Der er to mest almindelige måder at måle længden af en løsning på ( metrisk ). Den første måde - en omgang af løsningen anses for at være en drejning af ansigtet med 90° ( kvart omgang metrisk , QTM ). Ifølge den anden metode betragtes en halv drejning af ansigtet også for 1 træk ( face turn metric , FTM , nogle gange betegnes det med HTM - half-turn metric ). Således skal F2 (drejning af frontfladen 180°) tælles som to træk i QTM-metrikken eller 1 træk i FTM-metrikken [6] [7] .

For i teksten at angive længden af rækkefølgen for den anvendte metrik, bruges notationen [8] [9] [10] , der består af tallene for antallet af træk og det lille første bogstav i den metriske betegnelse. 14f står for "14 træk i FTM-metrikken" og 10q står for "10 træk i QTM-metrikken". For at angive, at antallet af træk er minimum i en given metrik, bruges en stjerne : 10f* angiver optimaliteten af løsningen i 10 FTM-træk.

Rubiks terninggruppe

Rubiks terning kan ses som et eksempel på en matematisk gruppe .

Hver af de seks rotationer af Rubiks terningflader kan betragtes som et element i den symmetriske gruppe af sættet med 48 Rubiks terningetiketter, der ikke er midten af overfladerne. Mere specifikt kan man markere alle 48 etiketter med tal fra 1 til 48 og tildele hvert af træk et element i den symmetriske gruppe . $\{F,B,U,D,L,R\}$ $S_{{48}}$

Derefter defineres Rubiks terninggruppe som den undergruppe , der genereres af seks fladerotationer: $G$ $S_{{48}}$

G=\langle F,B,U,D,L,R\rangle .

Grupperækkefølgen er [11] [12] $G$

|G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\,252\,003 \,274\,489\,856\,000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11.

Hver af konfigurationerne kan løses i højst 20 træk (hvis vi tæller enhver drejning af ansigtet som et træk) [1] . $4{,}325\cdot 10^{19}$

Den højeste rækkefølge af et element i er 1260. For eksempel skal rækkefølgen af træk gentages 1260 gange før Rubiks terning vender tilbage til sin oprindelige tilstand [13] . $G$ $(R\ U^{2}\ D^{{\prime }}\ B\ D^{{\prime }})$

Guds algoritme

Søgningen efter Guds algoritme begyndte senest i 1980, da en mailingliste for fans af Rubik's Cube blev åbnet [6] . Siden da har matematikere, programmører og amatører søgt at finde Guds algoritme, så de i praksis løser Rubiks terning med et minimum af træk. Relateret til dette problem var problemet med at bestemme antallet af Gud - antallet af træk, der altid er tilstrækkeligt til at fuldføre puslespillet.

I 2010, Palo Alto programmør Thomas Rokiki, Darmstadt matematiklærer Herbert Kotsemba, University of Kent matematiker Morley Davidson og ingeniør hos Google Inc. John Dethridge beviste, at en Rubiks terning fra enhver adskilt tilstand kan samles i 20 træk. I dette tilfælde blev enhver drejning af ansigtet betragtet som et træk. Beregningsmængden var 35 års CPU-tid doneret af Google [1] [14] [15] . Tekniske data om ydeevne og antal computere blev ikke offentliggjort. Varigheden af beregningerne var flere uger [16] [17] [18] .

I 2014 beviste Thomas Rockicki og Morley Davidson, at Rubiks terning ikke kan løses i mere end 26 træk uden brug af 180° drejninger. Mængden af beregninger var 29 års processortid i Ohio supercomputing center [3] .

Nedre grænser for antallet af Gud

Det er let at vise, at der er løselige konfigurationer [19] , som ikke kan løses i mindre end 17 træk i FTM-metrikken eller 19 træk i QTM-metrikken.

Dette estimat kan forbedres ved at tage højde for yderligere identiteter: kommutativiteten af rotationer af to modsatte flader (LR = RL, L2 R = RL2 osv.) Denne tilgang gør det muligt at opnå en nedre grænse for antallet af Gud i 18f eller 21q [20] [21] .

Dette skøn har længe været det bedst kendte. Det følger af et ikke-konstruktivt bevis, da det ikke angiver et specifikt eksempel på en konfiguration, der kræver 18f eller 21q for at bygge.

En af de konfigurationer, der ikke kunne findes en kort løsning på, var den såkaldte " superflip " eller "12-flip". I "Superflip" er alle hjørne- og kantterninger på deres pladser, men hver kantterning er orienteret modsat [22] . Toppunktet svarende til superflip i Rubiks terninggrafen er et lokalt maksimum: enhver bevægelse fra denne konfiguration reducerer afstanden til den oprindelige konfiguration. Dette antydede, at superflip er i den maksimale afstand fra den oprindelige konfiguration. Det vil sige, at et superflip er et globalt maksimum [23] [24] [25] .

I 1992 fandt Dick T. Winter en løsning på superflip i 20f [26] . I 1995 beviste Michael Reed optimaliteten af denne løsning [27] , som et resultat af hvilket den nedre grænse for antallet af Gud blev 20 FTM. I 1995 opdagede Michael Reid løsningen på "superflip" i 24q [28] . Optimiteten af denne løsning blev bevist af Jerry Bryan [29] . I 1998 fandt Michael Reed en konfiguration, hvis optimale løsning var 26q* [30] .

Øvre grænser for Guds tal

For at opnå en øvre grænse for Guds tal, er det tilstrækkeligt at specificere enhver puslespilssamlingsalgoritme bestående af et begrænset antal træk.

De første øvre grænser for antallet af Gud var baseret på "menneskelige" algoritmer bestående af flere stadier. Tilføjelse af estimaterne fra oven for hvert af stadierne gjorde det muligt at opnå et endeligt estimat i størrelsesordenen flere titusinder eller hundredvis af træk.

Sandsynligvis det første konkrete skøn fra oven blev givet af David Singmaster i 1979. Hans samlingsalgoritme gjorde det muligt at samle puslespillet i ikke mere end 277 træk [16] [31] . Singmaster rapporterede senere, at Alvin Berlekamp , John Conway og Richard Guy udviklede en montagealgoritme, der ikke kræver mere end 160 træk. Snart fandt en gruppe af "Conways Cambridge Cubists", som var ved at udarbejde en liste over kombinationer for et ansigt, en 94-vejs algoritme [16] [32] . I 1982 udgav magasinet Kvant en liste over kombinationer, der gør det muligt at løse Rubiks terning i 79 træk [33] .

Thistlethwaites algoritme

I begyndelsen af 1980'erne udviklede den engelske matematiker Morvin Thistlethwaite en algoritme, der markant forbedrede den øvre grænse. Detaljerne i algoritmen blev offentliggjort af Douglas Hofstadter i 1981 i Scientific American . Algoritmen var baseret på gruppeteori og omfattede fire trin.

Beskrivelse

Thistlethwaite brugte en række undergrupper af længde 4

G=G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq G_{3}\supseteq G_{4}=\{1\},

hvor

$G_{0}=\langle L,R,F,B,U,D\rangle .$

Denne gruppe er den samme som Rubik's Cube-gruppen . Dens rækkefølge er [34] [35]

G

{\dfrac {8!\cdot 3^{8}}{3}}\cdot {\dfrac {12!\cdot 2^{12}}{2}}\cdot {\dfrac {1}{ 2}}=43\,252\,003\,274\,489\,856\,000.

$G_{1}=\langle L^{2},R^{2},F,B,U,D\rangle .$

Denne undergruppe omfatter alle konfigurationer, der kan løses uden brug af rotationer af venstre eller højre side med ±90°. Dens rækkefølge er

{\dfrac {8!\cdot 3^{8}}{3}}\cdot 12!\cdot {\dfrac {1}{2}}=21\,119\,142\,223\, 872\.000.

$G_{2}=\langle L^{2},R^{2},F^{2},B^{2},U,D\rangle .$

Denne undergruppe omfatter alle konfigurationer, der kan løses, forudsat at rotationer af de fire lodrette flader med ±90° er forbudt. Dens rækkefølge er

8!\cdot (8!\cdot 4!)\cdot {\dfrac {1}{2))=19\,508\,428\,800.

$G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle .$

Denne undergruppe omfatter alle konfigurationer, der kan løses ved kun at bruge 180° drejninger (halvdrejninger). Det blev kaldt "gruppen af kvadrater" (firkanter gruppe). Dens rækkefølge er

(4!\cdot 4)\cdot {\dfrac {4!\cdot 4!\cdot 4!}{2))\cdot 1=663\,552.

$G_{4}=\{1\}.$

Denne undergruppe inkluderer en enkelt indledende konfiguration.

I det første trin reduceres en vilkårligt givet konfiguration fra gruppen til en konfiguration, der ligger i undergruppen . Målet med det andet trin er at bringe kuben til konfigurationen i undergruppen uden at bruge rotationer af venstre og højre side med ±90°. På tredje trin reduceres Rubiks terning til en konfiguration, der tilhører gruppen , mens rotationer af de lodrette flader med ±90° er forbudt. På den sidste fjerde fase samles Rubik's Cube fuldstændigt ved at dreje fladerne 180°. $G$ $G_{1}$ $G_{2}$ $G_{3}$

Undergruppeindekserne på er henholdsvis 2048, 1082565, 29400 og 663552. $[G_{i}:G_{{i+1}}]$ $i=0,1,2,3$

For hver af de fire familier af højre cosets er der bygget en opslagstabel , hvis størrelse matcher indekset for undergruppen i gruppen . For hver tilstødende undergruppeklasse indeholder opslagstabellen en sekvens af bevægelser, der oversætter enhver konfiguration fra denne tilstødende klasse til en konfiguration, der ligger i selve undergruppen . $G_{i}/G_{{i+1}}$ $T_{i}$ $G_{{i+1}}$ $G_{i}$ $G_{{i}}$ $T_{i}$ $G_{i}$

For at reducere antallet af poster i opslagstabellerne brugte Thistlethwaite at forenkle foreløbige træk. Den fik oprindeligt en score på 85 træk. I løbet af 1980 blev denne score reduceret til 80 træk, derefter til 63 og 52 [16] [36] . Thistlethwaites elever lavede en komplet analyse af hvert af faserne. De maksimale værdier i tabellerne er henholdsvis 7, 10, 13 og 15 FTM-slag. Da 7 + 10 + 13 + 15 = 45, kan Rubiks terning altid løses i 45 FTM [25] [37] [38] træk .

Grev Schreier

Schreier-grafen er en graf,knyttet til en gruppe, et generatorsæt og en undergruppe. Hvert toppunkt på Schreier-grafen er en ret cosetfor nogle. Kanterne på grev Schreier er par. $S(G,X,H)$ $G$ $X=\{x_{i}|i\in I\}$ $H\subseteq G$ $Hg=\{hg|h\in H\}$ $g\in G$ $(Hg,Hgx_{i})$

Hvert af de fire stadier af Thistlethwaites algoritme er en bredde-første gennemgang af Schreier-grafen , hvor er gruppens generatorsæt . $S_{i}(G_{i},X_{i},G_{{i+1}})$ $X_{i}$ $G_{i}$

Således er det øverste estimat på 45 træk

\sum _{i=0}^{3}\epsilon (v_{i}),

hvor

\epsilon(v_{i})

er excentriciteten af toppunktet svarende til enhedens coset .

v_{i}\in S_{i}

G_{{i+1}}

Begrebet en Schreier-graf blev brugt i Radu [39] , Kunkle og Coopermans værker [40] .

Ændringer af thistlethwaites algoritme

I december 1990 brugte Hans Kloosterman en modificeret version af Thistlethwaites metode til at bevise tilstrækkeligheden af 42 træk [1] [20] [41] .

I maj 1992 viste Michael Reid, at 39f eller 56q var tilstrækkeligt [42] . I sin modifikation blev følgende kæde af undergrupper brugt:

$G_{0}=\lang U,F,R,L,B,D\rangle$
$G_{1}=\langle U,R,F\rangle$
$G_{2}=\langle U,R^{2},F^{2}\rangle$
$G_{3}=\{1\}$

Et par dage senere sænkede Dick T. Winter sin FTM-score til 37 træk [43] .

I december 2002 udviklede Ryan Hayes en version af Thistlethwaites algoritme designet til at løse Rubik 's Cube hurtigt [44] .

To-faset Kotsemba algoritme

Thistlethwaites algoritme blev forbedret i 1992 af Herbert Kotsemba, en matematiklærer fra Darmstadt.

Beskrivelse

Kotsemba reducerede antallet af algoritmetrin til to [20] [45] [46] :

$G_{0}=\lang U,D,L,R,F,B\rangle$
$G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle$
$G_{2}=\{1\}$

En visuel beskrivelse af gruppen kan opnås, hvis følgende markering er lavet [20] [47] : $G_{1}$

Marker alle U- og D- etiketter med et "+"-tegn.
Etiketter F og B på kantelementer FR , FL , BL og BR er markeret med et "-".
Lad alle andre etiketter være umarkerede.

Så vil alle konfigurationer af gruppen have den samme markering (sammenfaldende med markeringen på den samlede terning). $G_{1}$

Løsningen består af to faser. I det første trin oversættes den givne konfiguration af en række bevægelser til en eller anden konfiguration . Med andre ord er opgaven i det første trin at gendanne den markup, der svarer til den oprindelige konfiguration, idet man ignorerer etiketternes farver. $x\in G_{0}$ $s_{1}$ $x^{{\prime }}\i G_{1}$

På det andet trin overføres konfigurationen ved en sekvens af bevægelser til den oprindelige konfiguration. I dette tilfælde bliver sidefladernes rotationer med ±90° ikke brugt, på grund af hvilken markeringen automatisk gemmes. $x^{{\prime }}\i G_{1}$ $s_{2}$

Limning af sekvenser af træk er en suboptimal løsning til den oprindelige konfiguration [20] [46] [48] . $s_{1}$ $s_{2}$

Alternative suboptimale løsninger

Kotsembas algoritme stopper ikke efter at have fundet den første løsning. Alternative optimale løsninger i første fase kan føre til kortere løsninger i anden fase, hvilket vil reducere løsningens samlede længde. Algoritmen fortsætter også med at søge efter ikke-optimale løsninger i den første fase for at øge deres længde [20] [46] [48] .

Implementeringsfunktioner

For at søge efter løsninger på hvert af de to stadier, bruges IDA* -algoritmen med heuristiske funktioner baseret på omkostningerne ved at løse de tilsvarende delopgaver [48] .

Den første fases opgave er reduceret til at finde en vej i rummet med tre koordinater fra mærkningen med koordinater ( x 1 , y 1 , z 1 ) til mærkningen (0, 0, 0) [49] :

Orientering x 1 af otte hjørneelementer (2187 værdier)
Y 1 -orienteringen af tolv kantelementer (2048 værdier)
Arrangement z 1 af fire kantelementer FR , FL , BL og BR (495 værdier)

Overvej tre underproblemer med at finde en sti fra markeringen ( x 1 , y 1 , z 1 ) til markeringen ( x 1 ', y 1 ', 0), ( x 1 ', 0, z 1 '), (0, y 1 ', z 1 '). Værdien af den heuristiske funktion h 1 brugt i det første trin er lig med de maksimale omkostninger ved at løse disse delproblemer. Omkostningerne til løsning af delopgaver er forudberegnet og gemt i form af databaser med skabeloner [50] [51] .

Opgaven i anden fase er reduceret til at finde en vej i rummet med tre koordinater fra konfigurationen ( x 2 , y 2 , z 2 ) til konfigurationen (0, 0, 0) [52] :

Permutation x 2 otte hjørneelementer (40320 værdier)
Permutation y 2 af de otte kantelementer på top- og bundflader (40320 værdier)
Permutation z 2 af de fire kantelementer i det midterste lag (24 værdier)

Overvej tre underproblemer med at finde en vej fra konfiguration ( x 2 , y 2 , z 2 ) til konfiguration ( x 2 ', y 2 ', 0), ( x 2 ', 0, z 2 '), (0, y 2 ', z2 ') . Værdien af den heuristiske funktion h 2 brugt i andet trin er lig med de maksimale omkostninger ved at løse disse delproblemer.

Algoritmen bruger yderligere optimeringer, der har til formål at øge ydeevnen og reducere hukommelsen optaget af tabeller [20] [45] [46] [53] .

Softwareimplementeringer

Cube Explorer er en softwareimplementering af algoritmen til Windows OS. Download links findes på Herbert Kotsembas hjemmeside [54] . I 1992, på en Atari ST PC med 1 MB hukommelse og en frekvens på 8 MHz, tillod algoritmen at finde en løsning på højst 22 træk inden for 1-2 minutter [20] [45] . På en moderne computer gør Cube Explorer det muligt på få sekunder at finde en løsning på ikke længere end 20 træk for en vilkårligt givet konfiguration [45] .

Der findes en online version af algoritmen [55] .

Analyse

I 1995 viste Michael Reed, at den første og anden fase af Kotsembas algoritme højst kunne kræve henholdsvis 12 og 18 træk (FTM). Det følger af dette, at Rubiks terning altid kan løses i 30 træk. Yderligere analyse viste, at 29f eller 42q [25] [56] altid er tilstrækkeligt .

Korffs algoritme

Kotsembas algoritme giver dig mulighed for hurtigt at finde korte, suboptimale løsninger. Det kan dog tage lang tid at bevise optimaliteten af den fundne løsning. Der var behov for en specialiseret algoritme til at finde optimale løsninger.

I 1997 udgav han en algoritme, der tillod ham optimalt at løse vilkårlige konfigurationer af Rubiks terning. Ti tilfældigt udvalgte konfigurationer blev løst i ikke mere end 18 FTM-træk [57] [58] .

Selve Korff-algoritmen fungerer som følger. Først og fremmest bestemmes delproblemer, der er enkle nok til at udføre en fuldstændig opregning. Følgende tre delopgaver [25] blev brugt :

Puslespillets tilstand bestemmes kun af de otte hjørneterninger, kanternes positioner og orientering ignoreres.
Puslespillets tilstand bestemmes af seks af de 12 kantterninger, de andre terninger ignoreres.
Puslespillets tilstand bestemmes af de andre seks kantterninger.

Antallet af træk, der skal til for at løse hvert af disse underproblemer, er en nedre grænse for antallet af træk, der skal til for at fuldføre løsningen. En vilkårligt givet konfiguration af Rubik's Cube løses ved hjælp af IDA* -algoritmen , som bruger dette estimat som en heuristik. Omkostningerne til løsning af delopgaver opbevares i form af databaser med skabeloner [50] [57] .

Selvom denne algoritme altid vil finde optimale løsninger, afgør den ikke direkte, hvor mange træk der i værste fald kan kræves.

En implementering af algoritmen i C kan findes i [59] .

Yderligere forbedringer

I 2005 forbedrede Michael Reids QTM-score Silviu Radu til 40q [60] . I 2006 beviste Silviu Radu, at Rubiks terning kan løses i 27f [39] eller 35q [61] .

I 2007 brugte Daniel Kunkle og Gene Cooperman en supercomputer til at bevise, at alle uløste konfigurationer ikke kan løses i mere end 26 FTM-træk. Ideen var at bringe Rubik's Cube ind i en af 15.752 undersæt af kvadratkonfigurationer , som hver kan endelig løses med et par ekstra træk. De fleste af konfigurationerne blev løst på denne måde i ikke mere end 26 træk. De resterende konfigurationer blev underkastet yderligere analyse, som viste, at de også kan løses i 26 træk [40] [62] .

I 2008 udgav Thomas Rokicki et beregningsbevis for løseligheden af FTM 25-træks puslespillet [63] . I august 2008 annoncerede Rokiki et bevis på solvabilitet i 23f [64] . Senere blev dette estimat forbedret til 22f [65] . I 2009 formåede han også at vise løsbarheden i 29 QTM-træk [66] .

I 2010 annoncerede Thomas Rokicki, Herbert Kotsemba, Morley Davidson og John Dethridge et bevis på, at enhver Rubik's Cube-konfiguration kan løses i højst 20 træk i FTM-metrikken [1] [14] . Sammen med det tidligere kendte lavere estimat på 20f* beviste dette, at Rubik's Cube God-tallet i FTM-metrikken er 20.

I august 2014 annoncerede Rockiki og Davidson, at Gud-tallet for Rubik's Cube i QTM-metrikken er 26 [3] [67] .

Søg efter antipoder

Konfigurationen af Rubiks terning, som er placeret i den maksimale afstand fra den oprindelige konfiguration, kaldes antipoden. Enhver antipode i FTM-metrikken har en optimal løsning i 20f*, og enhver antipode i QTM-metrikken har en optimal løsning i 26q* [3] [68] .

Det er kendt, at der er millioner af antipoder i FTM-metrikken [69] . En sådan konfiguration er "superflip". Tværtimod er der i QTM-metrikken kun én antipodal konfiguration kendt (ikke tæller konfigurationerne opnået fra den ved rotationer) - den såkaldte. superflip komponeret med fire plet [30] [67] [68] [70] . Kun to konfigurationer er kendt i en afstand på 25q* fra den oprindelige konfiguration og omkring 80 tusinde konfigurationer i en afstand på 24q* [3] [69] .

Asymptotiske estimater

I 2011 blev n × n × n kube Gud-tallet vist at være Θ( n 2 / log( n )) [71] [72] .

Andre gåder

Void Cube

Void Cube er en 3x3x3 Rubik's Cube uden centrale brikker.

Længden af den optimale løsning for et " void-superflip " i FTM-metrikken er 20 [73] [74] , hvilket er et bevis på, at 20 træk er nødvendige. Da Void Cube er et svækket problem [50] af Rubik's Cube, gælder det eksisterende bevis på, at 20 træk er tilstrækkeligt til Rubik's Cube [1] for Void Cube. Derfor er Gud-tallet for Void Cube i FTM-metrikken 20.

Terning 4×4×4

Antallet af konfigurationer af 4×4×4-puslespillet ( Eng. Rubik's Revenge ) er [75]

{\frac {8!\times 3^{7}\times 24!^{2}}{4!^{6}\times 24}}=7401196841564901869874093974498574336000000000\}ca. 1^0 sek. {45}.

Metrics 4×4×4

Der er flere måder at bestemme metrikken for en 4x4x4 terning. Dette afsnit bruger følgende metrics:

qs (kvart skive): en omgang anses for at rotere ethvert af de 12 puslespilslag med ±90°;
qw (kvart vridning): en omgang anses for at rotere enhver ydre blok (dvs. kun flader eller flader med flere tilstødende lag ved siden af sig i en række ) med ±90°;
qb (kvartblok): en omgang anses for at rotere enhver ydre eller indre blok (dvs. enhver sekvens af på hinanden følgende parallelle lag) med ±90° i forhold til resten af puslespillet;
hs , hw , hb : Samme som de foregående 3 metrikker, bortset fra at 180° rotationer også er tilladt.

Længden af den optimale løsning af en vilkårlig konfiguration i qb -metrikken er ikke større end i qw- eller qs -metrikken , da alle bevægelser af de to andre q-metrikker er tilladt i qb -metrikken. Det samme gælder for h-metrics.

Estimater af antallet af Gud terning 4×4×4

I 2006-2007 Bruce Norskog lavede en 5-trins analyse af 4x4x4 terningen, svarende til 4-trinsanalysen udført af Thistlethwaite for 3x3x3 Rubik's Cube. Analysen gav øvre grænser for 82 træk i hw- metrikken [76] , 77 træk i hs- metrikken [77] [78] og 67 træk i hb- metrikken [76] .

I 2011 bestemte Thomas Rokiki, baseret på flere eksisterende ideer, nedre grænser for antallet af Gud i seks metrikker for kubiske puslespil med størrelser fra 2×2×2 til 20×20×20 [79] .

I 2013 sænkede Shuang Chen (陈霜) sin hw -score fra 82 til 57 omgange [80] .

I 2015 bekræftede Thomas Rokicki topscore på 57 hw og modtog nye topscore på 56 hs og 53 hb [81] . Et par dage senere lykkedes det Shuang Chen (陈霜) at opnå øvre grænser på 55 hw og 53 hs ved at omdefinere trinene i beviset [82] [83] .

De nuværende kendte øvre og nedre score for 4×4×4-matricen i forskellige metrikker er vist i tabellen:

4x4x4 Cube God Number Estimater

målinger	hs	hw	hb	qs	qw	qb
lavere skøn	32	35	29	37	41	33
top estimat	53	55	53	?	?	?

Megaminx

Megaminx er den enkleste analog af Rubiks terning i form af et dodecahedron. Antallet af konfigurationer af 12-farve Megaminx er 1,01·10 68 .

I 2012 bestemte Herbert Kotsemba en nedre grænse for Megaminx' Gud-tal til 45 fladerotationer gennem enhver vinkel eller 55 rotationer gennem en vinkel på ±72° [84] [85] .
I 2016 forbedrede Herbert Kotsemba det lavere estimat af Gud-tallet for Megaminx og øgede det til 48 ansigtsrotationer i enhver vinkel [86] .

Se også

Noter

↑ 1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; og Dethridge, J. Guds tal er 20 . Hentet 19. juli 2013. Arkiveret fra originalen 21. juli 2013.
↑ Ifølge systemet af generatorer, bestående af drejninger af flader med ±90° og 180°.
↑ 1 2 3 4 5 Rokicki, T. og Davidson, M. Guds tal er 26 i Quarter-Turn Metric . Hentet 4. juli 2015. Arkiveret fra originalen 7. juli 2015.
↑ Joyner, 2002 , s. 7.
↑ Moralske og matematiske lektioner fra en Rubik-terning // Ny videnskabsmand. - 1982.
↑ 1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. The Cube: Den ultimative guide til verdens bedst sælgende puslespil - hemmeligheder, historier, løsninger . - 2009. - S. 26. - 142 s.
↑ Jaap Scherphuis. Nyttig matematik . Metrics (engelsk) (downlink) . Hentet 17. juli 2013. Arkiveret fra originalen 24. november 2012.
↑ Jerry Bryan. Notationskonvention (27. maj 2006). Hentet 28. juli 2013. Arkiveret fra originalen 9. november 2014. (ubestemt)
↑ David Singmaster. Kubisk cirkulær . - 1982. - Iss. 5 & 6 . — S. 26 .
↑ Jaap Scherphuis. Puslespil statistik . Hentet 17. juli 2013. Arkiveret fra originalen 21. juni 2013.
↑ Schönert, Martin analyserer Rubiks terning med GAP . Dato for adgang: 19. juli 2013. Arkiveret fra originalen 20. januar 2013.
↑ Jaap Scherphuis. Rubik's Cube 3x3x3 (engelsk) (ikke tilgængeligt link) . Hentet 19. juli 2013. Arkiveret fra originalen 28. juli 2013.
↑ Joyner, 2008 , s. 93 , 108.
↑ 1 2 Herbert Kociemba. To-fase-algoritme og Guds algoritme: Guds tal er 20 (engelsk) (link ikke tilgængeligt) . Dato for adgang: 23. juli 2013. Arkiveret fra originalen 2. maj 2013.
↑ Tomas Rokicki, Herbert Kociemba, Morley Davidson og John Dethridge. Diameteren af Rubik's Cube Group er tyve // SIAM J. Discrete Math.. - 2013. - Vol. 27, nr. 2. - P. 1082-1105. - doi : 10.1137/120867366 .
↑ 1 2 3 4 Rik van Grol. Søgen efter Guds nummer . Math Horizons (november 2010). Hentet 26. juli 2013. Arkiveret fra originalen 9. november 2014.
↑ Stefan Edelkamp, Stefan Schrōdl. Heuristisk søgning: teori og anvendelser. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
↑ SIAM J. Discrete Math., 27(2), 1082–1105 . Hentet 19. november 2013. Arkiveret fra originalen 3. december 2019. (ubestemt)
↑ En "opløselig" konfiguration er en konfiguration, der kan oversættes til en kompileret. Da grafen for Rubiks terning er urettet, følger det, at enhver konfiguration opnået fra den oprindelige vilkårlige sekvens af træk kan bestemmes. Men der er uløselige konfigurationer. For eksempel, hvis et af hjørnerne af terningen drejes 120° i samlet tilstand, opnås en uløselig konfiguration.
↑ 1 2 3 4 5 6 7 8 V. Dubrovsky, A. Kalinin. Nyt om kubologi // Kvant . - 1992. - Nr. 11 . - S. 52-56 .
↑ Jaap Scherphuis. Nyttig matematik . God's Algorithm (engelsk) (utilgængeligt link) . Hentet 17. juli 2013. Arkiveret fra originalen 24. november 2012.
↑ Michael Reid. Michael Reids Rubiks terningside . M-symmetriske positioner (engelsk) (24. maj 2005) . Hentet 17. juli 2013. Arkiveret fra originalen 6. juli 2015.
↑ David Singmaster. Kubisk cirkulær . - 1982. - Iss. 5 & 6 . — S. 24 .
↑ Joyner, 2002 , s. 149.
↑ 1 2 3 4 Stefan Pochmann. Analyse af menneskelige løsningsmetoder for Rubiks terning og lignende gåder (Diploma-afhandling ) . Arkiveret fra originalen den 9. november 2014.
↑ Dik T. Winter. Kociembas algoritme (engelsk) (18. maj 1992). Hentet 17. juli 2013. Arkiveret fra originalen 15. juli 2013.
↑ Michael Reid. superflip kræver 20 ansigtsdrejninger ( 18. januar 1995). Hentet 17. juli 2013. Arkiveret fra originalen 8. juli 2013.
↑ Michael Reid. superflip (engelsk) (10. januar 1995). Hentet 17. juli 2013. Arkiveret fra originalen 19. juni 2014.
↑ Jerry Bryan. Qturn længder af M-symmetriske positioner ( 19. februar 1995). Hentet 17. juli 2013. Arkiveret fra originalen 20. juni 2014.
↑ 12 Michael Reid . superflip komponeret med fire plet (engelsk) (2. august 1998). Hentet 4. juli 2015. Arkiveret fra originalen 4. oktober 2015.
↑ L. A. Kaluzhnin, V. I. Sushchansky. Transformationer og permutationer. - M. , 1985. - S. 143. - 160 s.
↑ David Singmaster. Noter om Rubiks magiske terning (neopr.) . — Enslow Publishers, 1981. - S. 30 .
↑ V. Dubrovsky. The Magic Cube Algorithm // Kvant . - 1982. - Nr. 7 . - S. 22-25 .
↑ Rækkefølgen af denne og de næste tre grupper beregnes som produktet af tre faktorer, der angiver henholdsvis antallet af opløselige hjørnekonfigurationer, antallet af opløselige kantkonfigurationer og den overordnede "paritets"-begrænsning på den opløselige konfiguration.
↑ Jaap Scherphuis. Kube undergrupper . Undergrupper genereret af ansigtsbevægelser (eng.) (utilgængeligt link) . Dato for adgang: 19. juli 2013. Arkiveret fra originalen 20. januar 2013.
↑ Mark Longridge. Progressive forbedringer i løsning af algoritmer . Hentet 28. juli 2013. Arkiveret fra originalen 9. oktober 2013.
↑ V. Dubrovsky. Mathematics of the Magic Cube // Kvant . - 1982. - Nr. 8 . - S. 22-27, 48 .
↑ Jaap Scherphuis. Thistlethwaites 52 - bevægelses algoritme . Hentet 17. juli 2013. Arkiveret fra originalen 28. juli 2013.
↑ 12 silviu . Rubik kan løses i 27f . Domain of the Cube Forum (1. april 2006). Hentet 20. juli 2013. Arkiveret fra originalen 27. august 2013. (ubestemt)
↑ 1 2 Kunkle, D.; Cooperman, C. (2007). "Seksogtyve træk er tilstrækkeligt til Rubiks terning" (PDF) . Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC '07) . ACM Tryk. Arkiveret (PDF) fra originalen 2019-02-18 . Hentet 2013-07-17 . Forældet parameter brugt |deadlink=( hjælp )
↑ Michael Reid. en øvre grænse for guds tal (engelsk) (29. april 1992). Dato for adgang: 17. juli 2013. Arkiveret fra originalen 24. august 2013.
↑ Michael Reid. ny øvre grænse (engelsk) (22. maj 1992). Hentet 19. juli 2013. Arkiveret fra originalen 24. august 2013.
↑ Dik T. Winter. Korrigerede beregninger er nu udført. (engelsk) (28. maj 1992). Hentet 19. juli 2013. Arkiveret fra originalen 20. juni 2014.
↑ Ryan Heise. Den menneskelige Thistlethwaite-algoritme . Dato for adgang: 19. juli 2013. Arkiveret fra originalen 2. august 2016.
↑ 1 2 3 4 Herbert Kociemba. Tofasealgoritmedetaljer . _ Hentet 20. juli 2013. Arkiveret fra originalen 2. maj 2013.
↑ 1 2 3 4 Jaap Scherphuis. Computer gådefuldt . Kociembas algoritme . Hentet 23. juli 2013. Arkiveret fra originalen 25. juni 2013.
↑ Herbert Kociemba. Undergruppen H og dens cosets . Hentet 23. juli 2013. Arkiveret fra originalen 22. maj 2013.
↑ 1 2 3 Herbert Kociemba. To - fase-algoritmen . Dato for adgang: 23. juli 2013. Arkiveret fra originalen 2. maj 2013.
↑ Biektion mellem konfigurationer og tripler af koordinater Den arkiverede kopi af 2. maj 2013 på Wayback Machine er indstillet på en sådan måde, at mållayoutet for den første fase (dvs. enhver konfiguration fra gruppen G 1 ) svarer til triplen (0) 0, 0).
↑ 1 2 3 Stuart Russell, Peter Norvig. Kompilering af tilladelige heuristiske funktioner // Kunstig intelligens: en moderne tilgang = Kunstig intelligens: En moderne tilgang. - 2. udg. - M . : Williams, 2006. - S. 170 - 173. - 1408 s. — ISBN 5-8459-0887-6 .
↑ Engelsk. mønsterdatabaser . I præsentationen af forfatteren af algoritmen Arkivkopi dateret 2. maj 2013 på Wayback Machine - "beskæringstabeller".
↑ På grund af paritetsbegrænsningen af elementernes permutation forekommer kun halvdelen af alle tripler af koordinater.
↑ Herbert Kociemba. Beskæringstabeller . _ Dato for adgang: 23. juli 2013. Arkiveret fra originalen 2. maj 2013.
↑ Herbert Kociemba. Download (engelsk) . Hentet 20. juli 2013. Arkiveret fra originalen 2. maj 2013.
↑ Eric Dietz. Løs din terning på mindre end 25 træk . Hentet 20. juli 2013. Arkiveret fra originalen 9. januar 2022.
↑ Michael Reid. nye øvre grænser (engelsk) (7. januar 1995). Hentet 19. juli 2013. Arkiveret fra originalen 24. august 2013.
↑ 1 2 Richard E. Korf. At finde optimale løsninger til Rubiks terning ved hjælp af mønsterdatabaser . – 1997.
↑ Arthur Fisher . Rubik's Reduced (engelsk) , Popular Science (oktober 1997), s. 58.
↑ Michael Reid. Rubiks terningside . Optimal Rubiks terningløser (28. oktober 2006) . Hentet 20. juli 2013. Arkiveret fra originalen 5. juli 2015. (ubestemt)
↑ Silviu Radu, A New Upper Bound on Rubik's Cube Group, arΧiv : math/0512485 .
↑ silviu. Rubik kan løses i 35q . Domain of the Cube Forum (22. marts 2006). Hentet 20. juli 2013. Arkiveret fra originalen 9. november 2014. (ubestemt)
↑ Northeastern University-forskere løser Rubiks terning i 26 træk . Hentet 20. juli 2013. Arkiveret fra originalen 23. oktober 2019. (ubestemt)
↑ Tom Rokicki, Twenty-Five Moves Suffice for Rubik's Cube, arΧiv : 0803.3435 .
↑ stenet. Treogtyve træk er tilstrækkeligt . Domain of the Cube Forum (29. april 2008). Hentet 20. juli 2013. Arkiveret fra originalen 27. august 2013. (ubestemt)
↑ stenet. Toogtyve træk er tilstrækkeligt (utilgængeligt link) . Domain of the Cube Forum (12. august 2008). Hentet 20. juli 2013. Arkiveret fra originalen 5. december 2011. (ubestemt)
↑ stenet. Niogtyve QTM-bevægelser er tilstrækkelige . Domain of the Cube Forum (15. juni 2009). Dato for adgang: 20. juli 2013. Arkiveret fra originalen den 26. juli 2011. (ubestemt)
↑ 1 2 Adam P. Goucher. Superflip komponeret med fourspot . Complex Projective 4-Space (25. september 2015). Hentet 23. oktober 2015. Arkiveret fra originalen 1. februar 2016. (ubestemt)
↑ 1 2 Jaap Scherphuis. Cayley Graphs . Afstande (engelsk) . Hentet 4. juli 2015. Arkiveret fra originalen 6. juli 2015.
↑ 1 2 Kendte afstand-20 positioner i halvdrejningsmetrikken. Kendte afstand-24 eller større positioner i kvart-sving-metrikken . Hentet 4. juli 2015. Arkiveret fra originalen 29. juni 2015. (ubestemt)
↑ Smukke mønstre Rubiks terning | Edge Flip, Dot | Superflip, med 4 prikker . Hentet 4. juli 2015. Arkiveret fra originalen 5. juli 2015. (ubestemt)
↑ Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lubiw, Anna & Winslow, Andrew (2011), Algorithms for Solving Rubik's Cubes, arΧiv : 1106.5736v1 [cs.DS].
↑ Larry Hardesty. Matematikken for Rubiks terning . Ny forskning fastslår forholdet mellem antallet af kvadrater i et puslespil af Rubiks-terning-typen og det maksimale antal træk, der kræves for at løse det . MIT News Office (29. juni 2011) . Hentet 23. juli 2013. Arkiveret fra originalen 19. september 2013.
↑ stenet. Ugyldig terningdiameter på mindst 20 (metrisk ansigtsdrejning) . Domain of the Cube Forum (19. januar 2010). Hentet 28. juli 2013. Arkiveret fra originalen 9. november 2014. (ubestemt)
↑ stenet. Ugyldig terningdiameter på mindst 20 (sandsynligvis 20) . Speedsolving.com (19. januar 2010). Hentet 28. juli 2013. Arkiveret fra originalen 9. november 2014. (ubestemt)
↑ Jaap Scherphuis. Rubiks hævn . Hentet 28. juli 2013. Arkiveret fra originalen 27. juli 2013.
↑ 1 2 Bruce Norskog. Nye øvre grænser: 82 drejninger, 67 blokdrejninger . Domain of the Cube Forum (13. august 2007). Hentet 28. juli 2013. Arkiveret fra originalen 29. maj 2014. (ubestemt)
↑ Bruce Norskog. 4x4x4 kan løses i 77 single-slice vendinger . Domain of the Cube Forum (26. juli 2007). Hentet 28. juli 2013. Arkiveret fra originalen 29. maj 2014. (ubestemt)
↑ Større rubik terning bundet (downlink) . Projekt Euler. Hentet 28. juli 2013. Arkiveret fra originalen 29. maj 2014. (ubestemt)
↑ stenet. Nedre grænser for nxnxn Rubiks terninger (til n=20) i seks metrikker . Domain of the Cube Forum (18. juli 2011). Hentet 28. juli 2013. Arkiveret fra originalen 9. november 2014. (ubestemt)
↑ CS. Løsning af 4x4x4 i 57 træk(OBTM) . Domain of the Cube Forum (30. september 2013). Hentet 19. november 2013. Arkiveret fra originalen 26. november 2013. (ubestemt)
↑ stenet. 4x4x4 øvre grænser: 57 OBTM bekræftet; 56 SST og 53 BT beregnet. . Domain of the Cube Forum (3. marts 2015). Hentet 1. juli 2015. Arkiveret fra originalen 29. maj 2015. (ubestemt)
↑ CS. 4x4x4 ny øvre grænse: 55 OBTM . Domain of the Cube Forum (3. juli 2015). Hentet 1. juli 2015. Arkiveret fra originalen 29. maj 2015. (ubestemt)
↑ CS. 4x4x4 ny øvre grænse: 53 SSTM . Domain of the Cube Forum (3. september 2015). Hentet 1. juli 2015. Arkiveret fra originalen 29. maj 2015. (ubestemt)
↑ Herbert Kociemba. Megaminx har brug for mindst 45 træk . Domain of the Cube Forum (28. februar 2012). Hentet 28. juli 2013. Arkiveret fra originalen 9. november 2014. (ubestemt)
↑ Herbert Kociemba. Nedre grænse for Megaminx i htm og qtm . Speedsolving.com (3. januar 2012). Hentet 28. juli 2013. Arkiveret fra originalen 9. november 2014. (ubestemt)
↑ Nedre grænse for Megaminx i htm og qtm . Hentet 2. september 2016. Arkiveret fra originalen 17. september 2016. (ubestemt)

Foreslået læsning

V. Zalgaller, S. Zalgaller. Ungarsk artikuleret terning // Kvant . - 1980. - Nr. 12 . - S. 17 - 21 . (Russisk)
V. Dubrovsky. The Magic Cube Algorithm // Kvant . - 1982. - Nr. 7 . - S. 22-25 . (Russisk)
V. Dubrovsky. Mathematics of the Magic Cube // Kvant . - 1982. - Nr. 8 . - S. 22 - 27, 48 . (Russisk)
V. Dubrovsky, A. Kalinin. Nyt om kubologi // Kvant . - 1992. - Nr. 11 . - S. 52 - 56 . (Russisk)
L. A. Kaluzhnin, V. I. Sushchansky. Transformationer og permutationer. - M. , 1985. - S. 143. - 160 s.
David Singmaster. Cubic Cirkulære . - 1981 - 1985.
David Singmaster, Alexander Frey. Håndbog i Cubik Math. - 1987.
David Joyner. Eventyr i gruppeteori: Rubiks terning, Merlins maskine og andet matematisk legetøj . - Baltimore: Johns Hopkins University Press, 2002. - ISBN 0-8018-6947-1 .
David Joyner. Eventyr i gruppeteori: Rubiks terning, Merlins maskine og andet matematisk legetøj . - Anden version. - JHU Press, 2008. - 328 s. - ISBN 0-801-89726-2 , 978-0-801-89726-9.
ED Demaine, ML Demaine, S. Eisenstat, A. Lubiw, A. Winslow. Algoritmer til løsning af Rubiks terninger // Forelæsningsnotater i datalogi. - 2011. - T. 6942 . - S. 689-700 . - doi : 10.1007/978-3-642-23719-5_58 .