Rubiks kub matematik

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 juli 2021; kontroller kräver 17 redigeringar .

Rubiks kub matematik

Mediafiler på Wikimedia Commons

Mathematics of the Rubik's Cube är en uppsättning matematiska metoder för att studera egenskaperna hos Rubiks kub ur en abstrakt matematisk synvinkel. Denna gren av matematik studerar kubmonteringsalgoritmer och utvärderar dem. Baserad på grafteori , gruppteori , beräkningsbarhetsteori och kombinatorik .

Det finns många algoritmer utformade för att överföra Rubiks kub från en godtycklig konfiguration till den slutliga konfigurationen (den sammansatta kuben). 2010 bevisades det rigoröst att inte mer än 20 varv av ytorna räcker för att överföra Rubiks kub från en godtycklig konfiguration till en sammansatt konfiguration (ofta kallad "montering" eller "lösning") [1] . Detta nummer är diametern på Cayley-grafen för Rubiks kubgrupp [2] . 2014 bevisades det att 26 drag alltid räcker för att lösa Rubiks kub med endast 90° varv av ytorna [3] .

En algoritm som löser ett pussel i minsta möjliga antal drag kallas för Gud algoritmen .

Notation

Den här artikeln använder "Singmaster-notation" [4] [5] utvecklad av David Singmaster och publicerad av honom 1981 för att beteckna rotationssekvensen av ansiktena på en 3×3×3 Rubiks kub .

Bokstäverna representerar 90° medurs rotation av vänster ( vänster ), höger ( höger ), fram ( fram ), bak ( bak ), topp ( upp ) respektive botten ( ned ) sidor. 180° varv indikeras genom att lägga till en 2:a till höger om bokstaven, eller genom att lägga till en upphöjd 2 till höger om bokstaven. En 90° moturs rotation indikeras genom att lägga till ett bindestreck ( ′ ) eller lägga till en upphöjd -1 till höger om bokstaven. Så till exempel är posterna och likvärdiga, liksom posterna och . $L,R,F,B,U,D$ $L^{2}$ $L2$ $L'$ $L^{{-1}}$

Configuration Graph Metrics

Det finns två vanligaste sätt att mäta längden på en lösning ( metrisk ). Det första sättet - ett varv av lösningen anses vara ett varv med 90° ( kvartsvarv metriskt , QTM ). Enligt den andra metoden övervägs ett halvt varv av ansiktet också för 1 drag ( face turn metric , FTM , ibland betecknas det med HTM - half-turn metric ). Således bör F2 (vända framsidan 180°) räknas som två drag i QTM-måttet eller 1 drag i FTM-måttet [6] [7] .

För att i texten ange längden på sekvensen för den använda metriken används beteckningen [8] [9] [10] , bestående av siffrorna för antalet drag och den gemena första bokstaven i den metriska beteckningen. 14f står för "14 drag i FTM-måttet" och 10q står för "10 drag i QTM-måttet". För att indikera att antalet drag är det minsta i ett givet mått, används en asterisk : 10f* anger optimaliteten för lösningen i 10 FTM-drag.

Rubiks kubgrupp

Rubiks kub kan ses som ett exempel på en matematisk grupp .

Var och en av de sex rotationerna av Rubiks kubytor kan betraktas som en del av den symmetriska gruppen av uppsättningen av 48 Rubiks kubetiketter som inte är mitten av ytorna. Mer specifikt kan man markera alla 48 etiketterna med siffror från 1 till 48 och tilldela varje drag ett element i den symmetriska gruppen . $\{F,B,U,D,L,R\}$ $S_{{48}}$

Då definieras Rubiks kubgrupp som den undergrupp som genereras av sex ansiktsrotationer: $G$ $S_{{48}}$

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

Gruppordningen är [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.

Var och en av konfigurationerna kan lösas i högst 20 drag (om vi räknar varje vändning av ansiktet som ett drag) [1] . $4{,}325\cdot 10^{19}$

Den högsta ordningen för ett element i är 1260. Till exempel måste sekvensen av drag upprepas 1260 gånger innan Rubiks kub återgår till sitt ursprungliga tillstånd [13] . $G$ $(R\ U^{2}\ D^{{\prime }}\ B\ D^{{\prime }})$

Guds algoritm

Sökandet efter Guds algoritm började senast 1980, då en e-postlista för fans av Rubiks kub öppnades [6] . Sedan dess har matematiker, programmerare och amatörer försökt hitta Guds algoritm så att i praktiken, med ett minimum av drag, lösa Rubiks kub. Relaterat till detta problem var problemet med att bestämma antalet Gud - antalet drag som alltid är tillräckligt för att slutföra pusslet.

2010, Palo Alto -programmeraren Thomas Rokiki, Darmstadt -matteläraren Herbert Kotsemba, matematikern Morley Davidson från University of Kent och ingenjör på Google Inc. John Dethridge bevisade att en Rubiks kub från vilket som helst demonterat tillstånd kan monteras i 20 drag. I det här fallet betraktades varje vändning av ansiktet som ett drag. Mängden beräkning var 35 års CPU-tid som donerats av Google [1] [14] [15] . Tekniska data om prestanda och antal datorer avslöjades inte. Beräkningarnas varaktighet var flera veckor [16] [17] [18] .

2014 bevisade Thomas Rockicki och Morley Davidson att Rubiks kub kan lösas i högst 26 drag utan användning av 180° vändningar. Volymen av beräkningar var 29 års processortid i Ohio superdatorcenter [3] .

Nedre gränser för antalet Gud

Det är lätt att visa att det finns lösbara konfigurationer [19] som inte kan lösas med mindre än 17 drag i FTM-måttet eller 19 drag i QTM-måttet.

Denna uppskattning kan förbättras genom att ta hänsyn till ytterligare identiteter: kommutativiteten för rotationer av två motsatta ytor (LR = RL, L2 R = R L2, etc.) Detta tillvägagångssätt gör det möjligt att få en nedre gräns för antalet Gud i 18f eller 21q [20] [21] .

Denna uppskattning har länge varit den mest kända. Det följer av ett icke-konstruktivt bevis, eftersom det inte indikerar ett specifikt exempel på en konfiguration som kräver 18f eller 21q för att bygga.

En av de konfigurationer för vilka ingen kort lösning kunde hittas var den så kallade " superflip " eller "12-flip". I "Superflip" är alla hörn- och kantkuber på sina platser, men varje kantkub är orienterad motsatt [22] . Spetsen som motsvarar superflipen i Rubiks kubgraf är ett lokalt maximum: varje rörelse från denna konfiguration minskar avståndet till den ursprungliga konfigurationen. Detta antydde att superflip är på maximalt avstånd från den initiala konfigurationen. Det vill säga, en superflip är ett globalt maximum [23] [24] [25] .

1992 hittade Dick T. Winter en lösning på superflip i 20f [26] . 1995 bevisade Michael Reed optimaliteten av denna lösning [27] , som ett resultat av vilket den nedre gränsen för antalet av Gud blev 20 FTM. 1995 upptäckte Michael Reid lösningen på "superflipen" i 24q [28] . Optimaliteten av denna lösning bevisades av Jerry Bryan [29] . 1998 hittade Michael Reed en konfiguration vars optimala lösning var 26q* [30] .

Övre gränser för Guds nummer

För att få en övre gräns för Guds tal räcker det med att specificera vilken pusselsammansättningsalgoritm som helst som består av ett ändligt antal drag.

De första övre gränserna för antalet Gud baserades på "mänskliga" algoritmer bestående av flera stadier. Genom att lägga till uppskattningarna från ovan för var och en av stegen gjorde det möjligt att få en slutlig uppskattning i storleksordningen flera tiotals eller hundratals drag.

Förmodligen den första konkreta uppskattningen från ovan gavs av David Singmaster 1979. Hans monteringsalgoritm gjorde att pusslet kunde sättas ihop i högst 277 drag [16] [31] . Singmaster rapporterade senare att Alvin Berlekamp , John Conway och Richard Guy utvecklade en monteringsalgoritm som inte kräver mer än 160 drag. Snart hittade en grupp "Conways Cambridge-kubister", som höll på att sammanställa en lista med kombinationer för ett ansikte, en 94-vägsalgoritm [16] [32] . 1982 publicerade tidningen Kvant en lista över kombinationer som gör det möjligt att lösa Rubiks kub i 79 drag [33] .

Thistlethwaites algoritm

I början av 1980-talet utvecklade den engelske matematikern Morvin Thistlethwaite en algoritm som avsevärt förbättrade den övre gränsen. Detaljerna i algoritmen publicerades av Douglas Hofstadter 1981 i Scientific American . Algoritmen baserades på gruppteori och omfattade fyra steg.

Beskrivning

Thistlethwaite använde ett antal undergrupper med längd 4

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

var

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

Denna grupp är samma som Rubiks kub-gruppen . Dess ordning är [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 .$

Denna undergrupp inkluderar alla konfigurationer som kan lösas utan användning av rotationer på vänster eller höger sida med ±90°. Dess ordning är

{\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 .$

Denna undergrupp inkluderar alla konfigurationer som kan lösas förutsatt att rotationer av de fyra vertikala ytorna med ±90° är förbjudna. Dess ordning är

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 .$

Denna undergrupp inkluderar alla konfigurationer som kan lösas med endast 180° varv (halvvarv). Den kallades "gruppen av rutor" (rutagruppen). Dess ordning är

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

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

Denna undergrupp inkluderar en enda initial konfiguration.

I det första steget reduceras en godtyckligt given konfiguration från gruppen till en konfiguration som ligger i undergruppen . Målet med det andra steget är att föra kuben till konfigurationen i undergruppen utan att använda rotationer av vänster och höger yta med ±90°. I det tredje steget reduceras Rubiks kub till en konfiguration som tillhör gruppen , medan rotationer av de vertikala ytorna med ±90° är förbjudna. I det sista, fjärde steget, monteras Rubiks kub helt genom att vrida sidorna 180°. $G$ $G_{1}$ $G_{2}$ $G_{3}$

Undergruppsindexen vid är 2048, 1082565, 29400 respektive 663552. $[G_{i}:G_{{i+1}}]$ $i=0,1,2,3$

För var och en av de fyra familjerna med högra coset byggs en uppslagstabell , vars storlek matchar indexet för undergruppen i gruppen . För varje angränsande undergruppsklass innehåller uppslagstabellen en sekvens av drag som översätter alla konfigurationer från denna angränsande klass till en konfiguration som ligger i själva undergruppen . $G_{i}/G_{{i+1}}$ $T_{i}$ $G_{{i+1}}$ $G_{i}$ $G_{{i}}$ $T_{i}$ $G_{i}$

För att minska antalet poster i uppslagstabellerna använde Thistlethwaite förenklade preliminära drag. Den fick ursprungligen en poäng på 85 drag. Under 1980 reducerades denna poäng till 80 drag, sedan till 63 och 52 [16] [36] . Thistlethwaites elever gjorde en fullständig analys av vart och ett av stegen. De maximala värdena i tabellerna är 7, 10, 13 respektive 15 FTM-slag. Eftersom 7 + 10 + 13 + 15 = 45, kan Rubiks kub alltid lösas i 45 FTM [25] [37] [38] drag .

Greve Schreier

Schreier-grafen är en grafassocierad med en grupp, en genereringsmängd och en undergrupp. Varje hörn av Schreier-grafen är en rätt cosetför vissa. Kanterna på greve Schreier är 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})$

Vart och ett av de fyra stegen i Thistlethwaites algoritm är en bredd-först genomgång av Schreier-grafen , där är genereringsuppsättningen för gruppen . $S_{i}(G_{i},X_{i},G_{{i+1}})$ $X_{i}$ $G_{i}$

Således är den övre uppskattningen på 45 drag

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

var

\epsilon(v_{i})

är excentriciteten hos vertexet som motsvarar enhetens coset .

v_{i}\in S_{i}

G_{{i+1}}

Begreppet en Schreier-graf användes i verk av Radu [39] , Kunkle och Cooperman [40] .

Ändringar av thistlethwaites algoritm

I december 1990 använde Hans Kloosterman en modifierad version av Thistlethwaites metod för att bevisa att 42 drag räckte [1] [20] [41] .

I maj 1992 visade Michael Reid att 39f eller 56q var tillräckligt [42] . I sin modifiering användes följande kedja av undergrupper:

$G_{0}=\langle 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\}$

Några dagar senare sänkte Dick T. Winter sin FTM-poäng till 37 drag [43] .

I december 2002 utvecklade Ryan Hayes en version av Thistlethwaites algoritm utformad för att snabbt lösa Rubiks kub [44] .

Tvåfas Kotsemba-algoritm

Thistlethwaites algoritm förbättrades 1992 av Herbert Kotsemba, en matematiklärare från Darmstadt.

Beskrivning

Kotsemba minskade antalet algoritmsteg till två [20] [45] [46] :

$G_{0}=\langle 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 visuell beskrivning av gruppen kan erhållas om följande markering görs [20] [47] : $G_{1}$

Markera alla U- och D- etiketter med ett "+"-tecken.
Etiketter F och B på kantelementen FR , FL , BL och BR är markerade med ett "-".
Lämna alla andra etiketter omarkerade.

Då kommer alla konfigurationer av gruppen att ha samma markering (sammanfaller med markeringen på den sammansatta kuben). $G_{1}$

Lösningen består av två steg. I det första steget översätts den givna konfigurationen av en sekvens av drag till någon konfiguration . Med andra ord är uppgiften för det första steget att återställa markeringen som motsvarar den initiala konfigurationen, och ignorera färgerna på etiketterna. $x\in G_{0}$ $s_{1}$ $x^{{\prime }}\i G_{1}$

I det andra steget överförs konfigurationen genom en sekvens av rörelser till den initiala konfigurationen. I detta fall används inte sidoytornas rotationer med ±90°, vilket gör att markeringen automatiskt sparas. $x^{{\prime }}\i G_{1}$ $s_{2}$

Att limma sekvenser av drag är en suboptimal lösning på den ursprungliga konfigurationen [20] [46] [48] . $s_{1}$ $s_{2}$

Alternativa suboptimala lösningar

Kotsembas algoritm slutar inte efter att ha hittat den första lösningen. Alternativa optimala lösningar i det första steget kan leda till kortare lösningar i det andra steget, vilket minskar lösningens totala längd. Algoritmen fortsätter även att söka efter icke-optimala lösningar i det första steget för att öka deras längd [20] [46] [48] .

Implementeringsfunktioner

För att söka efter lösningar i vart och ett av de två stegen används IDA* -algoritmen med heuristiska funktioner baserade på kostnaderna för att lösa motsvarande deluppgifter [48] .

Uppgiften för det första steget reduceras till att hitta en väg i rymden med tre koordinater från märkningen med koordinater ( x 1 , y 1 , z 1 ) till märkningen (0, 0, 0) [49] :

Orientering x 1 av åtta hörnelement (2187 värden)
Y 1 -orienteringen för tolv kantelement (2048 värden)
Arrangemang z 1 av fyra kantelement FR , FL , BL och BR (495 värden)

Betrakta tre delproblem med att hitta en väg från markeringen ( x 1 , y 1 , z 1 ) till markeringen ( x 1 ', y 1 ', 0), ( x 1 ', 0, z 1 '), (0, y 1 ', z 1 '). Värdet på den heuristiska funktionen h 1 som används i det första steget är lika med den maximala kostnaden för att lösa dessa delproblem. Kostnaderna för att lösa deluppgifter är förberäknade och lagras i form av databaser med mallar [50] [51] .

Uppgiften för det andra steget reduceras till att hitta en väg i rymden med tre koordinater från konfigurationen ( x 2 , y 2 , z 2 ) till konfigurationen (0, 0, 0) [52] :

Permutation x 2 åtta hörnelement (40320 värden)
Permutation y 2 av de åtta kantelementen på topp- och bottenytorna (40320 värden)
Permutation z 2 av de fyra kantelementen i mellanlagret (24 värden)

Betrakta tre delproblem med att hitta en väg från konfiguration ( x 2 , y 2 , z 2 ) till konfiguration ( x 2 ', y 2 ', 0), ( x 2 ', 0, z 2 '), (0, y 2 ', z2 ') . Värdet på den heuristiska funktionen h 2 som används i det andra steget är lika med den maximala kostnaden för att lösa dessa delproblem.

Algoritmen använder ytterligare optimeringar som syftar till att öka prestanda och minska minnet som upptas av tabeller [20] [45] [46] [53] .

Programvaruimplementeringar

Cube Explorer är en mjukvaruimplementering av algoritmen för Windows OS. Nedladdningslänkar finns på Herbert Kotsembas hemsida [54] . År 1992, på en Atari ST PC med 1 MB minne och en frekvens på 8 MHz, tillät algoritmen att hitta en lösning som inte var längre än 22 drag inom 1-2 minuter [20] [45] . På en modern dator gör Cube Explorer det möjligt att på några sekunder hitta en lösning som inte är längre än 20 drag för en godtyckligt given konfiguration [45] .

Det finns en onlineversion av algoritmen [55] .

Analys

1995 visade Michael Reed att den första och andra fasen av Kotsembas algoritm kunde kräva högst 12 respektive 18 drag (FTM). Det följer av detta att Rubiks kub alltid kan lösas i 30 drag. Ytterligare analys visade att 29f eller 42q [25] [56] alltid är tillräckligt .

Korffs algoritm

Kotsembas algoritm gör att du snabbt kan hitta korta, suboptimala lösningar. Det kan dock ta lång tid att bevisa optimaliteten hos den hittade lösningen. En specialiserad algoritm för att hitta optimala lösningar behövdes.

1997 publicerade han en algoritm som gjorde det möjligt för honom att optimalt lösa godtyckliga konfigurationer av Rubiks kub. Tio slumpmässigt valda konfigurationer löstes i högst 18 FTM-drag [57] [58] .

Själva Korff-algoritmen fungerar enligt följande. Först och främst bestäms delproblem som är enkla nog att utföra en fullständig uppräkning. Följande tre deluppgifter [25] användes :

Pusslets tillstånd bestäms endast av de åtta hörnkuberna, kanternas positioner och orienteringar ignoreras.
Pusslets tillstånd bestäms av sex av de 12 kanttärningarna, de andra tärningarna ignoreras.
Pusslets tillstånd bestäms av de andra sex kanttärningarna.

Antalet drag som krävs för att lösa vart och ett av dessa delproblem är en nedre gräns för antalet drag som krävs för att slutföra lösningen. En godtyckligt given konfiguration av Rubiks kub löses med IDA*-algoritmen , som använder denna uppskattning som en heuristik. Kostnaderna för att lösa deluppgifter lagras i form av databaser med mallar [50] [57] .

Även om denna algoritm alltid kommer att hitta optimala lösningar, avgör den inte direkt hur många drag som kan krävas i värsta fall.

En implementering av algoritmen i C finns i [59] .

Ytterligare förbättringar

2005 förbättrade Michael Reids QTM-poäng Silviu Radu till 40q [60] . 2006 bevisade Silviu Radu att Rubiks kub kan lösas i 27f [39] eller 35q [61] .

2007 använde Daniel Kunkle och Gene Cooperman en superdator för att bevisa att alla olösta konfigurationer kan lösas i högst 26 FTM-drag. Tanken var att föra in Rubiks kub i en av 15 752 delmängder av kvadratkonfigurationer , som var och en kan lösas till slut med några extra drag. De flesta av konfigurationerna löstes på detta sätt i högst 26 drag. De återstående konfigurationerna utsattes för ytterligare analys, som visade att de också kan lösas i 26 drag [40] [62] .

År 2008 publicerade Thomas Rokicki ett beräkningsbevis på lösbarheten hos FTM 25-dragpusslet [63] . I augusti 2008 tillkännagav Rokiki ett bevis på lösbarhet i 23f [64] . Senare förbättrades denna uppskattning till 22f [65] . 2009 lyckades han också visa lösbarheten i 29 QTM-drag [66] .

2010 tillkännagav Thomas Rokicki, Herbert Kotsemba, Morley Davidson och John Dethridge ett bevis på att vilken Rubiks kub-konfiguration som helst kan lösas i högst 20 drag i FTM-metriken [1] [14] . Tillsammans med den tidigare kända lägre uppskattningen av 20f* bevisade detta att Rubik's Cube God-talet i FTM-måttet är 20.

I augusti 2014 meddelade Rockiki och Davidson att gudsnumret för Rubiks kub i QTM-måttet är 26 [3] [67] .

Sök efter antipoder

Konfigurationen av Rubiks kub, som är belägen på maximalt avstånd från den ursprungliga konfigurationen, kallas antipoden. Alla antipoder i FTM-måttet har en optimal lösning i 20f*, och alla antipoder i QTM-måttet har en optimal lösning i 26q* [3] [68] .

Det är känt att det finns miljontals antipoder i FTM-metriken [69] . En sådan konfiguration är "superflip". Tvärtom, i QTM-metriken är för närvarande endast en antipodalkonfiguration känd (utan att räkna de konfigurationer som erhålls från den genom rotationer) - den så kallade. superflip komponerad med fyra fläckar [30] [67] [68] [70] . Endast två konfigurationer är kända på ett avstånd av 25q* från den initiala konfigurationen och cirka 80 tusen konfigurationer på ett avstånd av 24q* [3] [69] .

Asymptotiska uppskattningar

År 2011 visades n × n × n kubens gudsnummer vara Θ( n 2 / log( n )) [71] [72] .

Andra pussel

Void Cube

Void Cube är en 3x3x3 Rubiks kub utan centrala delar.

Längden på den optimala lösningen för en "void- superflip " i FTM-metriken är 20 [73] [74] , vilket är ett bevis på att 20 drag är nödvändiga. Eftersom Void Cube är ett försvagat problem [50] av Rubik's Cube, gäller det befintliga beviset på att 20 drag räcker för Rubik's Cube [1] för Void Cube. Därför är Gud-numret för Void Cube i FTM-måttet 20.

Kub 4×4×4

Antalet konfigurationer av 4×4×4-pusslet ( Eng. Rubik's Revenge ) är [75]

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

Mätvärden 4×4×4

Det finns flera sätt att bestämma måtten för en 4x4x4 kub. Det här avsnittet använder följande mätvärden:

qs (kvartsskiva): ett varv anses rotera något av de 12 pussellagren med ±90°;
qw (kvartsvridning): ett varv anses rotera vilket yttre block som helst (d.v.s. endast ytor eller ytor med flera intilliggande lager intill sig i rad ) med ±90°;
qb (kvartsblock): ett varv anses rotera vilket yttre eller inre block (d.v.s. valfri sekvens av på varandra följande parallella lager) med ±90° i förhållande till resten av pusslet;
hs , hw , hb : Samma som de tre föregående måtten, förutom att 180° rotationer också är tillåtna.

Längden på den optimala lösningen av en godtycklig konfiguration i qb-måttet är inte större än i qw- eller qs -måttet , eftersom alla rörelser av de andra två q-måtten är tillåtna i qb -måttet. Detsamma gäller för h-metrics.

Uppskattningar av antalet Gud kub 4×4×4

Under 2006-2007 Bruce Norskog gjorde en 5-stegsanalys av 4x4x4-kuben, liknande den 4-stegsanalys som Thistlethwaite gjorde för 3x3x3 Rubik's Cube. Analysen gav övre gränser för 82 drag i hw- måttet [76] , 77 drag i hs- måttet [77] [78] och 67 drag i hb- måttet [76] .

År 2011 bestämde Thomas Rokiki, baserat på flera befintliga idéer, nedre gränser för antalet Gud i sex mått för kubiska pussel med storlekar från 2×2×2 till 20×20×20 [79] .

2013 sänkte Shuang Chen (陈霜) sin hw- poäng från 82 till 57 varv [80] .

2015 bekräftade Thomas Rokicki toppbetyget på 57 hw och fick nya toppbetyg på 56 hs och 53 hb [81] . Några dagar senare lyckades Shuang Chen (陈霜) få övre gränser på 55 hw och 53 hs genom att omdefiniera bevisets steg [82] [83] .

De nuvarande kända övre och nedre poängen för 4×4×4-matrisen i olika mått visas i tabellen:

4x4x4 Cube God Antal uppskattningar

metrik	hs	H w	hb	qs	qw	qb
lägre uppskattning	32	35	29	37	41	33
högsta uppskattning	53	55	53	?	?	?

Megaminx

Megaminx är den enklaste analogen av Rubiks kub i form av en dodekaeder. Antalet konfigurationer av 12-färgs Megaminx är 1,01·10 68 .

År 2012 bestämde Herbert Kotsemba att en nedre gräns för Megaminxs Gud-tal var 45 ansiktsrotationer genom vilken vinkel som helst, eller 55 rotationer genom en vinkel på ±72° [84] [85] .
Under 2016 förbättrade Herbert Kotsemba den lägre uppskattningen av Gud-talet för Megaminx, och ökade det till 48 ansiktsrotationer i valfri vinkel [86] .

Se även

Anteckningar

↑ 1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; och Dethridge, J. Guds nummer är 20 . Hämtad 19 juli 2013. Arkiverad från originalet 21 juli 2013.
↑ Enligt systemet med generatorer, bestående av varv på ytorna med ±90° och 180°.
↑ 1 2 3 4 5 Rokicki, T. och Davidson, M. Guds nummer är 26 i Quarter-Turn Metric . Hämtad 4 juli 2015. Arkiverad från originalet 7 juli 2015.
↑ Joyner, 2002 , sid. 7.
↑ Moraliska och matematiska lektioner från en Rubik-kub // New Scientist. — 1982.
↑ 1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. The Cube: Den ultimata guiden till världens bästsäljande pussel - hemligheter, berättelser, lösningar . - 2009. - S. 26. - 142 sid.
↑ Jaap Scherphuis. Användbar matematik . Mätvärden (engelska) (nedlänk) . Hämtad 17 juli 2013. Arkiverad från originalet 24 november 2012.
↑ Jerry Bryan. Notationskonvention (27 maj 2006). Hämtad 28 juli 2013. Arkiverad från originalet 9 november 2014. (obestämd)
↑ David Singmaster. Cubic Circular . - 1982. - Iss. 5 & 6 . — S. 26 .
↑ Jaap Scherphuis. Pusselstatistik . _ Hämtad 17 juli 2013. Arkiverad från originalet 21 juni 2013.
↑ Schönert, Martin Analyserar Rubiks kub med GAP . Datum för åtkomst: 19 juli 2013. Arkiverad från originalet 20 januari 2013.
↑ Jaap Scherphuis. Rubik's Cube 3x3x3 (engelska) (inte tillgänglig länk) . Hämtad 19 juli 2013. Arkiverad från originalet 28 juli 2013.
↑ Joyner, 2008 , s. 93 , 108.
↑ 1 2 Herbert Kociemba. Tvåfasalgoritm och Guds algoritm: Guds nummer är 20 (engelska) (länk ej tillgänglig) . Datum för åtkomst: 23 juli 2013. Arkiverad från originalet den 2 maj 2013.
↑ Tomas Rokicki, Herbert Kociemba, Morley Davidson och John Dethridge. Rubiks kubgrupps diameter är tjugo // SIAM J. Discrete Math.. - 2013. - Vol. 27, nr. 2. - P. 1082-1105. - doi : 10.1137/120867366 .
↑ 1 2 3 4 Rik van Grol. Jakten på Guds nummer . Math Horizons (november 2010). Hämtad 26 juli 2013. Arkiverad från originalet 9 november 2014.
↑ Stefan Edelkamp, Stefan Schrōdl. Heuristisk sökning: teori och tillämpningar. - Morgan Kaufmann Publishers , 2012. - 712 sid. — ISBN 978-0-12-372512-7 .
↑ SIAM J. Discrete Math., 27(2), 1082–1105 . Hämtad 19 november 2013. Arkiverad från originalet 3 december 2019. (obestämd)
↑ En "lösbar" konfiguration är en konfiguration som kan översättas till en kompilerad. Eftersom grafen för Rubiks kub är oriktad, följer det att varje konfiguration som erhålls från den ursprungliga godtyckliga sekvensen av drag är avgörbar. Men det finns olösliga konfigurationer. Till exempel, om en av kubens hörn roteras 120° i monterat tillstånd, kommer en olöslig konfiguration att erhållas.
↑ 1 2 3 4 5 6 7 8 V. Dubrovsky, A. Kalinin. Nyheter om kubologi // Kvant . - 1992. - Nr 11 . - S. 52-56 .
↑ Jaap Scherphuis. Användbar matematik . God's Algorithm (engelska) (inte tillgänglig länk) . Hämtad 17 juli 2013. Arkiverad från originalet 24 november 2012.
↑ Michael Reid. Michael Reids Rubiks kubsida . M-symmetriska positioner (engelska) (24 maj 2005) . Hämtad 17 juli 2013. Arkiverad från originalet 6 juli 2015.
↑ David Singmaster. Cubic Circular . - 1982. - Iss. 5 & 6 . — S. 24 .
↑ Joyner, 2002 , sid. 149.
↑ 1 2 3 4 Stefan Pochmann. Analysera mänskliga lösningsmetoder för Rubiks kub och liknande pussel (Diplomauppsats ) . Arkiverad från originalet den 9 november 2014.
↑ Dik T. Winter. Kociembas algoritm (engelska) (18 maj 1992). Hämtad 17 juli 2013. Arkiverad från originalet 15 juli 2013.
↑ Michael Reid. superflip kräver 20 ansiktsvändningar ( 18 januari 1995). Hämtad 17 juli 2013. Arkiverad från originalet 8 juli 2013.
↑ Michael Reid. superflip (engelska) (10 januari 1995). Hämtad 17 juli 2013. Arkiverad från originalet 19 juni 2014.
↑ Jerry Bryan. Qturn Lengths of M-Symmetric Positions ( 19 februari 1995). Hämtad 17 juli 2013. Arkiverad från originalet 20 juni 2014.
↑ 12 Michael Reid . superflip komponerad med fyra fläckar (engelska) (2 augusti 1998). Hämtad 4 juli 2015. Arkiverad från originalet 4 oktober 2015.
↑ L. A. Kaluzhnin, V. I. Sushchansky. Transformationer och permutationer. - M. , 1985. - S. 143. - 160 sid.
↑ David Singmaster. Anteckningar om Rubiks magiska kub (neopr.) . — Enslow Publishers, 1981. - S. 30 .
↑ V. Dubrovsky. The Magic Cube Algorithm // Kvant . - 1982. - Nr 7 . - S. 22-25 .
↑ Ordningen för denna och de följande tre grupperna beräknas som produkten av tre faktorer som anger respektive antal lösbara hörnkonfigurationer, antalet lösbara kantkonfigurationer och den övergripande "paritets"-begränsningen på den lösbara konfigurationen.
↑ Jaap Scherphuis. Kubundergrupper . Undergrupper genererade av ansiktsrörelser (eng.) (inte tillgänglig länk) . Datum för åtkomst: 19 juli 2013. Arkiverad från originalet 20 januari 2013.
↑ Mark Longridge. Progressiva förbättringar i att lösa algoritmer . Hämtad 28 juli 2013. Arkiverad från originalet 9 oktober 2013.
↑ V. Dubrovsky. Mathematics of the Magic Cube // Kvant . - 1982. - Nr 8 . - S. 22-27, 48 .
↑ Jaap Scherphuis. Thistlethwaites 52-stegs algoritm . Hämtad 17 juli 2013. Arkiverad från originalet 28 juli 2013.
↑ 12 silviu . Rubik kan lösas i 27f . Domain of the Cube Forum (1 april 2006). Hämtad 20 juli 2013. Arkiverad från originalet 27 augusti 2013. (obestämd)
↑ 1 2 Kunkle, D.; Cooperman, C. (2007). "Tjugosex drag räcker för Rubiks kub" (PDF) . Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC '07) . ACM Tryck. Arkiverad (PDF) från originalet 2019-02-18 . Hämtad 2013-07-17 . Utfasad parameter används |deadlink=( hjälp )
↑ Michael Reid. en övre gräns för guds nummer (engelska) (29 april 1992). Datum för åtkomst: 17 juli 2013. Arkiverad från originalet den 24 augusti 2013.
↑ Michael Reid. ny övre gräns (engelska) (22 maj 1992). Hämtad 19 juli 2013. Arkiverad från originalet 24 augusti 2013.
↑ Dik T. Winter. Korrigerade beräkningar är nu gjorda. (engelska) (28 maj 1992). Hämtad 19 juli 2013. Arkiverad från originalet 20 juni 2014.
↑ Ryan Heise. Den mänskliga Thistlethwaite-algoritmen . Tillträdesdatum: 19 juli 2013. Arkiverad från originalet 2 augusti 2016.
↑ 1 2 3 4 Herbert Kociemba. Tvåfasalgoritmdetaljer . _ Hämtad 20 juli 2013. Arkiverad från originalet 2 maj 2013.
↑ 1 2 3 4 Jaap Scherphuis. Dator förbryllande . Kociembas algoritm . Hämtad 23 juli 2013. Arkiverad från originalet 25 juni 2013.
↑ Herbert Kociemba. Undergruppen H och dess cosets . Hämtad 23 juli 2013. Arkiverad från originalet 22 maj 2013.
↑ 1 2 3 Herbert Kociemba. Tvåfasalgoritmen . _ Datum för åtkomst: 23 juli 2013. Arkiverad från originalet den 2 maj 2013.
↑ Bijektion mellan konfigurationer och trippel av koordinater Den arkiverade kopian av 2 maj 2013 på Wayback Machine är inställd på ett sådant sätt att mållayouten för det första steget (d.v.s. valfri konfiguration från gruppen G 1 ) motsvarar trippeln (0) , 0, 0).
↑ 1 2 3 Stuart Russell, Peter Norvig. Sammanställning av tillåtna heuristiska funktioner // Artificiell intelligens: ett modernt tillvägagångssätt = Artificial Intelligence: A Modern Approach. - 2:a uppl. - M . : Williams, 2006. - S. 170 - 173. - 1408 sid. — ISBN 5-8459-0887-6 .
↑ Engelska. mönsterdatabaser . I presentationen av författaren till algoritmen Arkivkopia daterad 2 maj 2013 på Wayback Machine - "beskärningstabeller".
↑ På grund av paritetsbegränsningen för permutationen av element uppstår endast hälften av alla trippel av koordinater.
↑ Herbert Kociemba. Beskärningstabeller . _ Datum för åtkomst: 23 juli 2013. Arkiverad från originalet den 2 maj 2013.
↑ Herbert Kociemba. Ladda ner (engelska) . Hämtad 20 juli 2013. Arkiverad från originalet 2 maj 2013.
↑ Eric Dietz. Lös din kub på mindre än 25 drag . Hämtad 20 juli 2013. Arkiverad från originalet 9 januari 2022.
↑ Michael Reid. nya övre gränser (engelska) (7 januari 1995). Hämtad 19 juli 2013. Arkiverad från originalet 24 augusti 2013.
↑ 1 2 Richard E. Korf. Hitta optimala lösningar för Rubiks kub med hjälp av mönsterdatabaser . — 1997.
↑ Arthur Fisher . Rubik's Reduced (engelska) , Popular Science (oktober 1997), s. 58.
↑ Michael Reid. Rubiks kubsida . Optimal Rubiks kublösare (28 oktober 2006) . Hämtad 20 juli 2013. Arkiverad från originalet 5 juli 2015. (obestämd)
↑ Silviu Radu, A New Upper Bound on Rubik's Cube Group, arΧiv : math/0512485 .
↑ silviu. Rubik kan lösas i 35q . Domain of the Cube Forum (22 mars 2006). Hämtad 20 juli 2013. Arkiverad från originalet 9 november 2014. (obestämd)
↑ Forskare från Northeastern University löser Rubiks kub i 26 drag . Hämtad 20 juli 2013. Arkiverad från originalet 23 oktober 2019. (obestämd)
↑ Tom Rokicki, Twenty-Five Moves Suffice for Rubik's Cube, arΧiv : 0803.3435 .
↑ stenig. Tjugotre drag räcker . Domain of the Cube Forum (29 april 2008). Hämtad 20 juli 2013. Arkiverad från originalet 27 augusti 2013. (obestämd)
↑ stenig. Tjugotvå drag räcker (inte tillgänglig länk) . Domain of the Cube Forum (12 augusti 2008). Hämtad 20 juli 2013. Arkiverad från originalet 5 december 2011. (obestämd)
↑ stenig. Tjugonio QTM-rörelser räcker . Domain of the Cube Forum (15 juni 2009). Datum för åtkomst: 20 juli 2013. Arkiverad från originalet den 26 juli 2011. (obestämd)
↑ 1 2 Adam P. Goucher. Superflip komponerad med fourspot . Complex Projective 4-Space (25 september 2015). Hämtad 23 oktober 2015. Arkiverad från originalet 1 februari 2016. (obestämd)
↑ 1 2 Jaap Scherphuis. Cayley Graphs . Avstånd (engelska) . Hämtad 4 juli 2015. Arkiverad från originalet 6 juli 2015.
↑ 1 2 Kända avstånd-20 positioner i halvvarvsmåttet. Kända avstånd-24 eller högre positioner i kvartalssvängsmåttet . Hämtad 4 juli 2015. Arkiverad från originalet 29 juni 2015. (obestämd)
↑ Vackra mönster Rubiks kub | Edge Flip, Dot | Superflip, med 4 prickar . Hämtad 4 juli 2015. Arkiverad från originalet 5 juli 2015. (obestämd)
↑ Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lubiw, Anna & Winslow, Andrew (2011), Algoritmer för att lösa Rubiks kuber, arΧiv : 1106.5736v1 [cs.DS].
↑ Larry Hardesty. Matematiken för Rubiks kub . Ny forskning fastställer förhållandet mellan antalet rutor i ett pussel av typen Rubiks-kub och det maximala antalet drag som krävs för att lösa det . MIT News Office (29 juni 2011) . Hämtad 23 juli 2013. Arkiverad från originalet 19 september 2013.
↑ stenig. Tom kubdiameter minst 20 (metrisk ansiktsväng) . Domain of the Cube Forum (19 januari 2010). Hämtad 28 juli 2013. Arkiverad från originalet 9 november 2014. (obestämd)
↑ stenig. Tom kubdiameter minst 20 (troligen 20) . Speedsolving.com (19 januari 2010). Hämtad 28 juli 2013. Arkiverad från originalet 9 november 2014. (obestämd)
↑ Jaap Scherphuis. Rubiks hämnd . Hämtad 28 juli 2013. Arkiverad från originalet 27 juli 2013.
↑ 1 2 Bruce Norskog. Nya övre gränser: 82 vridvarv, 67 blockvarv . Domain of the Cube Forum (13 augusti 2007). Hämtad 28 juli 2013. Arkiverad från originalet 29 maj 2014. (obestämd)
↑ Bruce Norskog. 4x4x4 kan lösas i 77 single-slice-varv . Domain of the Cube Forum (26 juli 2007). Hämtad 28 juli 2013. Arkiverad från originalet 29 maj 2014. (obestämd)
↑ Större rubikkub bunden (nedlänk) . Projekt Euler. Hämtad 28 juli 2013. Arkiverad från originalet 29 maj 2014. (obestämd)
↑ stenig. Nedre gränser för nxnxn Rubiks kuber (till n=20) i sex mått . Domain of the Cube Forum (18 juli 2011). Hämtad 28 juli 2013. Arkiverad från originalet 9 november 2014. (obestämd)
↑ CS. Lösa 4x4x4 i 57 drag(OBTM) . Domain of the Cube Forum (30 september 2013). Hämtad 19 november 2013. Arkiverad från originalet 26 november 2013. (obestämd)
↑ stenig. 4x4x4 övre gränser: 57 OBTM bekräftade; 56 SST och 53 BT beräknade. . Domain of the Cube Forum (3 mars 2015). Hämtad 1 juli 2015. Arkiverad från originalet 29 maj 2015. (obestämd)
↑ CS. 4x4x4 ny övre gräns: 55 OBTM . Domain of the Cube Forum (3 juli 2015). Hämtad 1 juli 2015. Arkiverad från originalet 29 maj 2015. (obestämd)
↑ CS. 4x4x4 ny övre gräns: 53 SSTM . Domain of the Cube Forum (3 september 2015). Hämtad 1 juli 2015. Arkiverad från originalet 29 maj 2015. (obestämd)
↑ Herbert Kociemba. Megaminx behöver minst 45 drag . Domain of the Cube Forum (28 februari 2012). Hämtad 28 juli 2013. Arkiverad från originalet 9 november 2014. (obestämd)
↑ Herbert Kociemba. Nedre gräns för Megaminx i htm och qtm . Speedsolving.com (3 januari 2012). Hämtad 28 juli 2013. Arkiverad från originalet 9 november 2014. (obestämd)
↑ Nedre gräns för Megaminx i htm och qtm . Hämtad 2 september 2016. Arkiverad från originalet 17 september 2016. (obestämd)

Föreslagen läsning

V. Zalgaller, S. Zalgaller. Ungersk ledad kub // Kvant . - 1980. - Nr 12 . - S. 17 - 21 . (ryska)
V. Dubrovsky. The Magic Cube Algorithm // Kvant . - 1982. - Nr 7 . - S. 22-25 . (ryska)
V. Dubrovsky. Mathematics of the Magic Cube // Kvant . - 1982. - Nr 8 . - S. 22 - 27, 48 . (ryska)
V. Dubrovsky, A. Kalinin. Nyheter om kubologi // Kvant . - 1992. - Nr 11 . - S. 52 - 56 . (ryska)
L. A. Kaluzhnin, V. I. Sushchansky. Transformationer och permutationer. - M. , 1985. - S. 143. - 160 sid.
David Singmaster. Cubic Circular . - 1981 - 1985.
David Singmaster, Alexander Frey. Handbok för Cubik Math. — 1987.
David Joyner. Äventyr i gruppteori: Rubiks kub, Merlins maskin och andra matematiska leksaker . - Baltimore: Johns Hopkins University Press, 2002. - ISBN 0-8018-6947-1 .
David Joyner. Äventyr i gruppteori: Rubiks kub, Merlins maskin och andra matematiska leksaker . - Andra upplagan. - JHU Press, 2008. - 328 sid. - ISBN 0-801-89726-2 , 978-0-801-89726-9.
ED Demaine, ML Demaine, S. Eisenstat, A. Lubiw, A. Winslow. Algoritmer för att lösa Rubiks kuber // Föreläsningsanteckningar i datavetenskap. - 2011. - T. 6942 . - S. 689-700 . - doi : 10.1007/978-3-642-23719-5_58 .

Länkar

Konstantin Knop. Rubik's Cube: Assault on the Stronghold . Hämtad 20 juli 2013. Arkiverad från originalet 20 oktober 2009. (ryska)
Rik van Grol. Jakten på Guds nummer . Math Horizons (november 2010). Hämtad: 26 juli 2013.

Omtryckt i: Rik van Grol. The Quest for God's Number // The Best Writing on Mathematics 2011 / Mircea Pitici, Freeman Dyson . - Princeton University Press , 2011. - S. 27-34. — 416 sid. - ISBN 1-400-83954-8 , 978-1-400-83954-4.

Jaap Scherphuis. Jaaps pusselsida . - Ett urval av information om en mängd olika pussel och metoder för att lösa dem. Hämtad: 20 juli 2013.
Herbert Kociemba. Cube Explorer 5.01 (engelska) . — Hemsida för Herbert Kotsemba. Detaljerad beskrivning av algoritmerna som används i programmet Cube Explorer. Hämtad: 20 juli 2013.
Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. Guds nummer är 20 (engelska) . Hämtad: 20 juli 2013.
Martin Schönert. Cube Lovers-arkiv konverterade till HTML . — 1947 artiklar mellan juli 1980 och juni 1996. Hämtad 20 juli 2013.
Mark Longridge. Kubforumets domän . — Diskussioner om kubens matematik. Hämtad: 20 juli 2013.
WD Joyner. Föreläsningsanteckningar om matematiken i Rubiks kub (engelska) (inte tillgänglig länk) . Hämtad 22 juli 2013. Arkiverad från originalet 5 september 2013.
Tomas Rokicki. Computers and the Cube (bilder) (engelska) (3 november 2009). — MATH 78SI : Speedcubing: historia, teori och praktik . Studentinitierad kurs på Stanford (hösten 2009). Hämtad: 30 juli 2013.