Rubikin kuution matematiikka

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. heinäkuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 17 muokkausta .

Rubikin kuution matematiikka

Mediatiedostot Wikimedia Commonsissa

Rubikin kuution matematiikka on joukko matemaattisia menetelmiä Rubikin kuution ominaisuuksien tutkimiseen abstraktista matemaattisesta näkökulmasta. Tämä matematiikan haara tutkii kuution kokoamisalgoritmeja ja arvioi niitä. Perustuu graafiteoriaan , ryhmäteoriaan , laskettavuusteoriaan ja kombinatoriikkaan .

On olemassa monia algoritmeja , jotka on suunniteltu siirtämään Rubikin kuutio mielivaltaisesta kokoonpanosta lopulliseen kokoonpanoon (koottuun kuutioon). Vuonna 2010 todistettiin tiukasti, että korkeintaan 20 pintojen kierrosta riittää siirtämään Rubikin kuution mielivaltaisesta kokoonpanosta koottuun kokoonpanoon (kutsutaan usein "kokoonpanoksi" tai "ratkaisuksi") [1] . Tämä luku on Rubikin kuutioryhmän Cayley-graafin halkaisija [2] . Vuonna 2014 todistettiin, että 26 liikettä riittää aina ratkaisemaan Rubikin kuution käyttämällä vain 90° kasvojen käännöksiä [3] .

Algoritmia, joka ratkaisee pulman mahdollisimman pienellä määrällä liikkeitä, kutsutaan God -algoritmiksi .

Merkintä

Tässä artikkelissa käytetään David Singmasterin kehittämää ja hänen vuonna 1981 julkaisemaa "Singmaster-merkintää" [4] [5] kuvaamaan 3×3×3 Rubikin kuution pintojen kiertojärjestystä .

Kirjaimet edustavat vasemman ( vasemman ), oikean ( oikean ), etu- ( etu- ), taka- ( taka- ), ylä- ( ylös ) ja alapuolen ( alas ) kiertoa 90° myötäpäivään. 180° käännökset ilmaistaan lisäämällä 2 kirjaimen oikealle puolelle tai lisäämällä yläindeksi 2 kirjaimen oikealle puolelle. 90° vastapäivään kiertäminen osoitetaan lisäämällä viiva ( ′ ) tai lisäämällä yläindeksi -1 kirjaimen oikealle puolelle. Joten esimerkiksi merkinnät ja ovat vastaavia, samoin kuin merkinnät ja . $L,R,F,B,U,D$ $L^{2}$ $L2$ $L'$ $L^{{-1}}$

Määrityskaavion metriikka

On kaksi yleisintä tapaa mitata ratkaisun pituus ( metriikka ). Ensimmäinen tapa - yksi ratkaisun käännös katsotaan kasvojen käännökseksi 90° ( neljänneskierrosmetriikka , QTM ). Toisen menetelmän mukaan 1 liikkeessä huomioidaan myös kasvojen puolikierros ( kasvojen kääntymismetriikka , FTM , joskus sitä merkitään HTM - puolikierrosmetriikalla ). Näin ollen F2 (etupuolen kääntäminen 180°) tulisi laskea kahdeksi liikkeeksi QTM-metriikassa tai yhdeksi siirroksi FTM-metriikassa [6] [7] .

Merkitsemään tekstissä käytetyn metriikan sekvenssin pituutta käytetään merkintää [8] [9] [10] , joka koostuu siirtojen lukumäärän numeroista ja metritunnuksen pienestä ensimmäisestä kirjaimesta. 14f tarkoittaa "14 liikettä FTM-metriikassa" ja 10q tarkoittaa "10 liikettä QTM-metriikassa". Osoittaakseen, että liikkeiden määrä on tietyn metriikan vähimmäismäärä, käytetään tähteä : 10f* tarkoittaa ratkaisun optimaalisuutta 10 FTM-siirrossa.

Rubikin kuutioryhmä

Rubikin kuutiota voidaan pitää esimerkkinä matemaattisesta ryhmästä .

Jokaista Rubikin kuution kasvojen kuudesta kierrosta voidaan pitää osana 48 Rubikin kuution etiketin joukon symmetristä ryhmää, jotka eivät ole kasvojen keskipisteitä. Tarkemmin sanottuna voidaan merkitä kaikki 48 tarraa numeroilla 1-48 ja määrittää jokaiselle siirrolle symmetrisen ryhmän elementti . $\{F,B,U,D,L,R\}$ $S_{{48}}$

Sitten Rubikin kuutioryhmä määritellään aliryhmäksi , joka on muodostettu kuudella kasvojen kierrolla: $G$ $S_{{48}}$

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

Ryhmäjärjestys on [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.

Jokainen konfiguraatio voidaan ratkaista enintään 20 liikkeellä (jos lasketaan mikä tahansa kasvojen käännös liikkeeksi) [1] . $4{,}325\cdot 10^{19}$

Elementin korkein järjestys on 1260. Esimerkiksi liikesarja on toistettava 1260 kertaa ennen kuin Rubikin kuutio palaa alkuperäiseen tilaansa [13] . $G$ $(R\ U^{2}\ D^{{\prime }}\ B\ D^{{\prime }})$

Jumalan algoritmi

Jumalan algoritmin etsiminen aloitettiin viimeistään vuonna 1980, jolloin avattiin postituslista Rubikin kuution faneille [6] . Siitä lähtien matemaatikot, ohjelmoijat ja amatöörit ovat pyrkineet löytämään Jumalan algoritmin, jotta käytännössä Rubikin kuutio voidaan ratkaista mahdollisimman pienellä määrällä liikkeitä. Tähän ongelmaan liittyi Jumalan lukumäärän määrittäminen - liikkeiden lukumäärä, joka riittää aina palapelin suorittamiseen.

Vuonna 2010 Palo Alton ohjelmoija Thomas Rokiki, Darmstadtin matematiikan opettaja Herbert Kotsemba, Kentin yliopiston matemaatikko Morley Davidson ja Google Inc :n insinööri. John Dethridge osoitti, että Rubikin kuutio voidaan koota mistä tahansa osiin puretusta tilasta 20 liikkeessä. Tässä tapauksessa mikä tahansa kasvojen käännös katsottiin yhdeksi liikkeeksi. Laskentamäärä oli 35 vuotta Googlen lahjoittamaa CPU-aikaa [1] [14] [15] . Teknisiä tietoja suorituskyvystä ja tietokoneiden lukumäärästä ei julkistettu. Laskelmien kesto oli useita viikkoja [16] [17] [18] .

Vuonna 2014 Thomas Rockicki ja Morley Davidson osoittivat, että Rubikin kuutio voidaan ratkaista enintään 26 liikkeellä ilman 180 asteen käännöksiä. Laskelmien määrä oli 29 vuotta prosessoriaikaa Ohion superlaskentakeskuksessa [3] .

Jumalan lukumäärän alarajat

On helppo osoittaa, että on olemassa ratkaistavia konfiguraatioita [19] , joita ei voida ratkaista alle 17 siirrolla FTM-metriikassa tai 19 siirrolla QTM-metriikassa.

Tätä arviota voidaan parantaa ottamalla huomioon lisäidentiteetit: kahden vastakkaisen pinnan rotaatioiden kommutatiivisuus (LR = RL, L2 R = R L2 jne.) Tällä lähestymistavalla voidaan saada alaraja Jumalan lukumäärälle 18f:ssä tai 21q [20] [21 ] .

Tämä arvio on ollut pitkään tunnetuin. Se seuraa ei-rakentavasta todistuksesta, koska se ei osoita erityistä esimerkkiä konfiguraatiosta, jonka rakentamiseen tarvitaan 18f tai 21q.

Yksi konfiguraatioista, joille ei löytynyt lyhyttä ratkaisua, oli niin kutsuttu " superflip " tai "12-flip". "Superflipissä" kaikki kulma- ja reunakuutiot ovat paikoillaan, mutta jokainen reunakuutio on suunnattu vastakkain [22] . Rubikin kuutiograafin superflipiä vastaava kärkipiste on paikallinen maksimi: mikä tahansa liike tästä konfiguraatiosta pienentää etäisyyttä alkuperäiseen konfiguraatioon. Tämä viittasi siihen, että superflip on suurimmalla etäisyydellä alkuperäisestä konfiguraatiosta. Eli superflip on globaali maksimi [23] [24] [25] .

Vuonna 1992 Dick T. Winter löysi ratkaisun superflipiin 20f:ssä [26] . Vuonna 1995 Michael Reed osoitti tämän ratkaisun optimaalisen [27] , minkä seurauksena Jumalan lukumäärän alarajaksi tuli 20 FTM. Vuonna 1995 Michael Reid löysi ratkaisun "superflipiin" 24q:ssa [28] . Tämän ratkaisun optimaalisuuden osoitti Jerry Bryan [29] . Vuonna 1998 Michael Reed löysi konfiguraation, jonka optimaalinen ratkaisu oli 26q* [30] .

Jumalan luvun yläraja

Jumalan luvun ylärajan saamiseksi riittää, että määritetään mikä tahansa pulmakokoonpanoalgoritmi, joka koostuu rajallisesta määrästä liikkeitä.

Jumalan lukumäärän ensimmäiset ylärajat perustuivat "ihmis"-algoritmeihin, jotka koostuivat useista vaiheista. Ylhäältä tulevien arvioiden lisääminen kullekin vaiheelle mahdollisti lopullisen arvion useiden kymmenien tai satojen siirtojen suuruudesta.

Todennäköisesti ensimmäisen konkreettisen arvion ylhäältä antoi David Singmaster vuonna 1979. Hänen kokoamisalgoritminsa mahdollisti palapelin kokoamisen enintään 277 liikkeellä [16] [31] . Singmaster raportoi myöhemmin, että Alvin Berlekamp , John Conway ja Richard Guy kehittivät kokoonpanoalgoritmin, joka ei vaadi enempää kuin 160 liikettä. Pian ryhmä "Conwayn Cambridgen kubisteja", jotka laativat luetteloa yhdelle kasvolle yhdistelmistä, löysi 94-suuntaisen algoritmin [16] [32] . Vuonna 1982 Kvant - lehti julkaisi luettelon yhdistelmistä, jotka mahdollistavat Rubikin kuution ratkaisemisen 79 liikkeessä [33] .

Thistlethwaiten algoritmi

1980-luvun alussa englantilainen matemaatikko Morvin Thistlethwaite kehitti algoritmin, joka paransi merkittävästi ylärajaa. Douglas Hofstadter julkaisi algoritmin yksityiskohdat vuonna 1981 Scientific American -lehdessä . Algoritmi perustui ryhmäteoriaan ja sisälsi neljä vaihetta.

Kuvaus

Thistlethwaite käytti useita alaryhmiä , joiden pituus oli 4

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

missä

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

Tämä ryhmä on sama kuin Rubikin kuutio -ryhmä . Sen järjestys on [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 .$

Tämä alaryhmä sisältää kaikki konfiguraatiot, jotka voidaan ratkaista ilman vasemman tai oikean puolen kiertoja ±90°. Sen järjestys on

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

Tämä alaryhmä sisältää kaikki konfiguraatiot, jotka voidaan ratkaista edellyttäen, että neljän pystysuoran pinnan kierto ±90° on kielletty. Sen järjestys on

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

Tämä alaryhmä sisältää kaikki kokoonpanot, jotka voidaan ratkaista käyttämällä vain 180° käännöksiä (puolikäännöksiä). Sitä kutsuttiin "neliöiden ryhmäksi" (neliöryhmä). Sen järjestys on

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

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

Tämä alaryhmä sisältää yhden alkukokoonpanon.

Ensimmäisessä vaiheessa mielivaltaisesti annettu konfiguraatio ryhmästä pelkistetään konfiguraatioksi, joka sijaitsee alaryhmässä . Toisen vaiheen tavoitteena on saada kuutio alaryhmän konfiguraatioon käyttämättä vasemman ja oikean pinnan kiertoja ±90°. Kolmannessa vaiheessa Rubikin kuutio pelkistetään ryhmään , kun taas pystypintojen pyörittäminen ±90° on kielletty. Viimeisessä, neljännessä vaiheessa Rubikin kuutio kootaan kokonaan kääntämällä kasvoja 180°. $G$ $G_{1}$ $G_{2}$ $G_{3}$

Alaryhmäindeksit ovat 2048, 1082565 , 29400 ja 663552. $[G_{i}:G_{{i+1}}]$ $i = 0,1,2,3$

Jokaiselle neljälle oikeiden kosettien perheelle rakennetaan hakutaulukko , jonka koko vastaa ryhmän aliryhmän indeksiä . Jokaiselle alaryhmän viereisyysluokalle hakutaulukko sisältää siirtosarjan, joka muuttaa minkä tahansa konfiguraation tästä viereisyysluokasta kokoonpanoksi, joka sijaitsee itse aliryhmässä . $G_{i}/G_{{i+1}}$ $T_{i}$ $G_{{i+1}}$ $G_{i}$ $G_{{i}}$ $T_{i}$ $G_{i}$

Tämätlethwaite käytti yksinkertaistavia alustavia liikkeitä vähentääkseen hakutaulukoiden merkintöjen määrää. Se sai alun perin pisteet 85 liikettä. Vuonna 1980 tämä pistemäärä laski 80 siirtoon, sitten 63:een ja 52:een [16] [36] . Thistlethwaiten oppilaat tekivät täydellisen analyysin jokaisesta vaiheesta. Taulukoiden maksimiarvot ovat 7, 10, 13 ja 15 FTM-iskua. Koska 7 + 10 + 13 + 15 = 45, Rubikin kuutio voidaan aina ratkaista 45 FTM [25] [37] [38] siirrolla .

Kreivi Schreier

Schreier-graafi on kuvaaja, joka liittyy ryhmään, generointijoukkoon ja aliryhmään. Jokainen Schreier-graafin kärkipiste on oikea cosetjoillekin. Kreivi Schreierin reunat ovat pareja. $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})$

Jokainen Thistlethwaiten algoritmin neljästä vaiheesta on Schreier-graafin leveys-ensimmäinen läpikulku , jossa on ryhmän generoiva joukko . $S_{i}(G_{i},X_{i},G_{{i+1}})$ $X_{i}$ $G_{i}$

Siten ylempi arvio 45 siirrosta on

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

missä

\epsilon(v_{i})

on yksikkökosettia vastaavan kärjen epäkeskisyys .

v_{i}\in S_{i}

G_{{i+1}}

Schreier-graafin käsitettä käytettiin Radun [39] , Kunklen ja Coopermanin [40] teoksissa .

Thistlethwaiten algoritmin muutokset

Joulukuussa 1990 Hans Kloosterman käytti modifioitua versiota Thistlethwaiten menetelmästä todistaakseen 42 liikkeen riittävyyden [1] [20] [41] .

Toukokuussa 1992 Michael Reid osoitti, että 39f tai 56q oli riittävä [42] . Sen muunnoksessa käytettiin seuraavaa alaryhmien ketjua:

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

Muutamaa päivää myöhemmin Dick T. Winter alensi FTM-pisteensä 37 siirtoon [43] .

Joulukuussa 2002 Ryan Hayes kehitti version Thistlethwaiten algoritmista, joka oli suunniteltu ratkaisemaan Rubikin kuutio nopeasti [44] .

Kaksivaiheinen Kotsemba-algoritmi

Thistlethwaiten algoritmia paransi vuonna 1992 Darmstadtista kotoisin oleva matematiikan opettaja Herbert Kotsemba.

Kuvaus

Kotsemba vähensi algoritmivaiheiden lukumäärän kahteen [20] [45] [46] :

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

Ryhmän visuaalinen kuvaus saadaan, jos tehdään seuraava merkintä [20] [47] : $G_{1}$

Merkitse kaikki U- ja D - tarrat "+"-merkillä.
Reunaelementtien FR , FL , BL ja BR etiketit F ja B on merkitty "-".
Jätä kaikki muut tarrat merkitsemättä.

Sitten kaikilla ryhmän kokoonpanoilla on sama merkintä (yhdenmukaisesti kootun kuution merkinnän kanssa). $G_{1}$

Ratkaisu koostuu kahdesta vaiheesta. Ensimmäisessä vaiheessa annettu konfiguraatio käännetään siirtosarjalla johonkin kokoonpanoon . Toisin sanoen ensimmäisen vaiheen tehtävänä on palauttaa alkuperäistä konfiguraatiota vastaava merkintä jättäen huomioimatta tarrojen värit. $x\in G_{0}$ $s_{1}$ $x^{{\prime }}\in G_{1}$

Toisessa vaiheessa konfiguraatio siirretään siirtosarjalla alkuperäiseen konfiguraatioon. Tällöin sivupintojen kiertoja ±90° ei käytetä, minkä vuoksi merkintä tallentuu automaattisesti. $x^{{\prime }}\in G_{1}$ $s_{2}$

Liikkeiden liimaaminen on epäoptimaalinen ratkaisu alkuperäiseen konfiguraatioon [20] [46] [48] . $s_{1}$ $s_{2}$

Vaihtoehtoisia alioptimaalisia ratkaisuja

Kotsemban algoritmi ei pysähdy ensimmäisen ratkaisun löytämisen jälkeen. Vaihtoehtoiset optimaaliset ratkaisut ensimmäisessä vaiheessa voivat johtaa lyhyempiin ratkaisuihin toisessa vaiheessa, mikä vähentää ratkaisun kokonaispituutta. Algoritmi jatkaa myös ei-optimaalisten ratkaisujen etsimistä ensimmäisessä vaiheessa niiden pituuden kasvattamiseksi [20] [46] [48] .

Toteutusominaisuudet

Ratkaisujen etsimiseen molemmissa kahdessa vaiheessa käytetään IDA* -algoritmia heurististen funktioiden kanssa, jotka perustuvat vastaavien osatehtävien ratkaisemisen kustannuksiin [48] .

Ensimmäisen vaiheen tehtävä rajoittuu kolmen koordinaatin polun löytämiseen avaruudesta koordinaattimerkinnöistä ( x 1 , y 1 , z 1 ) merkintään (0, 0, 0) [49] :

Suunta x 1 kahdeksasta kulmaelementistä (2187 arvoa)
Kahdentoista reunaelementin y 1 -suuntaus (2048 arvoa)
Järjestely z 1 neljästä reunaelementistä FR , FL , BL ja BR (495 arvoa)

Harkitse kolmea aliongelmaa polun löytämiseksi merkinnöistä ( x 1 , y 1 , z 1 ) merkintään ( x 1 ', y 1 ', 0), ( x 1 ', 0, z 1 '), (0, y 1 ', z 1 '). Ensimmäisessä vaiheessa käytetyn heuristisen funktion h 1 arvo on yhtä suuri kuin näiden aliongelmien ratkaisemisen enimmäiskustannukset. Osatehtävien ratkaisemisen kustannukset lasketaan etukäteen ja tallennetaan tietokantoihin, joissa on malleja [50] [51] .

Toisen vaiheen tehtävä rajoittuu kolmen koordinaatin polun löytämiseen avaruudessa konfiguraatiosta ( x 2 , y 2 , z 2 ) konfiguraatioon (0, 0, 0) [52] :

Permutaatio x 2 kahdeksan kulmaelementtiä (40320 arvoa)
Ylä- ja alapinnan kahdeksan reunaelementin permutaatio y 2 (40320 arvoa)
Keskikerroksen neljän reunaelementin permutaatio z 2 (24 arvoa)

Harkitse kolmea aliongelmaa polun löytämiseksi konfiguraatiosta ( x 2 , y 2 , z 2 ) konfiguraatioon ( x 2 ', y 2 ', 0 ), ( x 2 ', 0, z 2 '), (0, y 2 ) ', z2 ') . Toisessa vaiheessa käytetyn heuristisen funktion h 2 arvo on yhtä suuri kuin näiden osaongelmien ratkaisemisen maksimikustannukset.

Algoritmi käyttää lisäoptimointeja, joilla pyritään lisäämään suorituskykyä ja vähentämään taulukoiden [20] [45] [46] [53] käyttämää muistia .

Ohjelmistototeutukset

Cube Explorer on Windows-käyttöjärjestelmän algoritmin ohjelmistototeutus. Latauslinkit ovat Herbert Kotsemban verkkosivuilla [54] . Vuonna 1992 Atari ST PC :ssä, jossa oli 1 MB muisti ja taajuus 8 MHz, algoritmi mahdollisti ratkaisun löytämisen enintään 22 liikettä 1-2 minuutissa [20] [45] . Nykyaikaisessa tietokoneessa Cube Explorer mahdollistaa ratkaisun löytämisen muutamassa sekunnissa enintään 20 liikkeellä mielivaltaisesti annetulle kokoonpanolle [45] .

Algoritmista on olemassa online-versio [55] .

Analyysi

Vuonna 1995 Michael Reed osoitti, että Kotsemban algoritmin ensimmäinen ja toinen vaihe voivat vaatia enintään 12 ja 18 liikettä (FTM). Tästä seuraa, että Rubikin kuutio voidaan aina ratkaista 30 siirrolla. Lisäanalyysi osoitti, että 29f tai 42q [25] [56] on aina riittävä .

Korffin algoritmi

Kotsemban algoritmin avulla löydät nopeasti lyhyitä, epäoptimaalisia ratkaisuja. Löydetyn ratkaisun optimaalisuuden osoittaminen voi kuitenkin viedä huomattavasti aikaa. Optimaalisten ratkaisujen löytämiseen tarvittiin erikoisalgoritmi.

Vuonna 1997 hän julkaisi algoritmin, jonka avulla hän pystyi optimaalisesti ratkaisemaan mielivaltaisia Rubikin kuution kokoonpanoja. Kymmenen satunnaisesti valittua kokoonpanoa ratkaistiin enintään 18 FTM-siirrolla [57] [58] .

Itse Korff-algoritmi toimii seuraavasti. Ensinnäkin määritetään osaongelmat, jotka ovat riittävän yksinkertaisia täydellisen luettelon suorittamiseksi. Käytettiin seuraavia kolmea alatehtävää [25] :

Palapelin tilan määräävät vain kahdeksan kulmakuutiota, reunojen paikat ja suunnat jätetään huomiotta.
Palapelin tilan määrää kuusi 12 reunanoppaa, muut nopat jätetään huomiotta.
Palapelin tilan määräävät kuusi muuta reunanoppaa.

Kunkin aliongelman ratkaisemiseen vaadittavien liikkeiden määrä on alaraja ratkaisun suorittamiseen tarvittavien liikkeiden lukumäärälle. Satunnaisesti annettu Rubikin kuution konfiguraatio ratkaistaan käyttämällä IDA* -algoritmia , joka käyttää tätä arviota heuristisena. Osatehtävien ratkaisemisen kustannukset tallennetaan tietokantoihin, joissa on malleja [50] [57] .

Vaikka tämä algoritmi löytää aina optimaaliset ratkaisut, se ei suoraan määritä kuinka monta liikettä pahimmassa tapauksessa tarvitaan.

Algoritmin toteutus C:ssä löytyy julkaisusta [59] .

Muita parannuksia

Vuonna 2005 Michael Reidin QTM-pisteet paransivat Silviu Radun arvoon 40q [60] . Vuonna 2006 Silviu Radu osoitti, että Rubikin kuutio voidaan ratkaista 27f [39] tai 35q [61] .

Vuonna 2007 Daniel Kunkle ja Gene Cooperman käyttivät supertietokonetta todistaakseen, että kaikki ratkaisemattomat kokoonpanot voidaan ratkaista enintään 26 FTM-siirrolla. Ajatuksena oli tuoda Rubikin kuutio yhteen 15 752 neliökokoonpanosta , joista jokainen voidaan lopulta ratkaista muutamalla ylimääräisellä liikkeellä. Suurin osa kokoonpanoista ratkaistiin tällä tavalla enintään 26 siirrolla. Jäljelle jääville kokoonpanoille tehtiin lisäanalyysi, joka osoitti, että ne voidaan ratkaista myös 26 siirrolla [40] [62] .

Vuonna 2008 Thomas Rokicki julkaisi laskennallisen todisteen FTM 25-liikkeen pulman ratkaistavuudesta [63] . Elokuussa 2008 Rokiki ilmoitti 23f:n ratkaisevuudesta [64] . Myöhemmin tämä arvio parani arvoon 22f [65] . Vuonna 2009 hän onnistui myös osoittamaan ratkaistavuuden 29 QTM-siirrolla [66] .

Vuonna 2010 Thomas Rokicki, Herbert Kotsemba, Morley Davidson ja John Dethridge ilmoittivat todisteen siitä, että mikä tahansa Rubikin kuution konfiguraatio voidaan ratkaista enintään 20 siirrolla FTM-metriikassa [1] [14] . Yhdessä aiemmin tunnetun alemman arvion 20f* kanssa tämä osoitti, että Rubikin kuution jumalanumero FTM-metriikassa on 20.

Elokuussa 2014 Rockiki ja Davidson ilmoittivat, että Rubikin kuution jumalanumero QTM-metriikassa on 26 [3] [67] .

Hae antipodeja

Rubikin kuution konfiguraatiota, joka sijaitsee suurimmalla etäisyydellä alkuperäisestä konfiguraatiosta, kutsutaan antipodiksi. Millä tahansa antipodilla FTM-metriikassa on optimaalinen ratkaisu 20f*:ssa, ja kaikilla QTM-metriikan antipodilla on optimaalinen ratkaisu 26q*:ssa [3] [68] .

Tiedetään, että FTM-metriikassa on miljoonia antipodeja [69] . Yksi tällainen kokoonpano on "superflip". Päinvastoin, QTM-metriikassa tunnetaan tällä hetkellä vain yksi antipodaalinen konfiguraatio (lukuun ottamatta siitä rotaatioilla saatuja konfiguraatioita) - ns. superflip koostuu neljästä pisteestä [30] [67] [68] [70] . Vain kaksi konfiguraatiota tunnetaan 25q*:n etäisyydellä alkuperäisestä konfiguraatiosta ja noin 80 tuhatta konfiguraatiota 24q*:n etäisyydellä [3] [69] .

Asymptoottiset arviot

Vuonna 2011 n × n × n kuution jumalanumeron osoitettiin olevan Θ( n 2 / log( n )) [71] [72] .

Muut palapelit

Void Cube

Void Cube on 3x3x3 Rubikin kuutio, jossa ei ole keskiosia.

Optimaalisen ratkaisun pituus "tyhjä superflip " FTM-metriikassa on 20 [73] [74] , mikä on todiste siitä, että 20 liikettä tarvitaan. Koska tyhjiökuutio on Rubikin kuution heikentynyt ongelma [50] , olemassa oleva todiste 20 liikkeen riittävyydestä Rubikin kuutiolle [1] pätee tyhjiökuutioon. Siksi tyhjäkuution jumalanumero FTM-metriikassa on 20.

Kuutio 4×4×4

4×4×4 palapelin ( Eng. Rubik's Revenge ) kokoonpanojen määrä on [75]

{\frac {8!\times 3^{7}\times 24!^{2}}{4!^{6}\times 24}}=74011968415649018698740939744985743360000000000,1}pro0^7 {45}.

Mittarit 4×4×4

On olemassa useita tapoja määrittää 4x4x4-kuution mittari. Tämä osio käyttää seuraavia mittareita:

qs (neljännesviipale): yhden kierroksen katsotaan kiertävän mitä tahansa 12 palapelikerrosta ±90°;
qw (neljänneskierre): yhden kierroksen katsotaan kääntävän mitä tahansa ulompaa kappaletta (eli vain pinnat tai pinnat, joiden vieressä on useita vierekkäisiä kerroksia rivissä ) ±90°;
qb (neljänneslohko): yhden kierroksen katsotaan kiertävän mitä tahansa ulko- tai sisälohkoa (eli mitä tahansa peräkkäisten rinnakkaisten kerrosten sarjaa) ±90° suhteessa muuhun pulmapeliin;
hs , hw , hb : Samat kuin kolme edellistä metriikkaa, paitsi että myös 180° kierrokset ovat sallittuja.

Mielivaltaisen konfiguraation optimaalisen ratkaisun pituus qb -metriikassa ei ole suurempi kuin qw- tai qs -metriikassa , koska kaikki kahden muun q-metriikan liikkeet ovat sallittuja qb -metriikassa. Sama koskee h-metriikkaa.

Arviot Jumalan kuution 4×4×4 lukumäärästä

Vuosina 2006-2007 Bruce Norskog teki 5-vaiheisen analyysin 4x4x4-kuutiosta, joka on samanlainen kuin Thistlethwaiten 3x3x3-Rubikin kuutiolle tekemä 4-vaiheinen analyysi. Analyysi tuotti ylärajaksi 82 liikettä hw -metriikassa [76] , 77 liikettä hs -metriikassa [77] [78] ja 67 liikettä hb -metriikassa [76] .

Vuonna 2011 Thomas Rokiki määritti useiden olemassa olevien ajatusten perusteella alarajat Jumalan lukumäärälle kuudessa metriikassa kuutiopulmille, joiden koko oli 2×2×2 - 20×20×20 [79] .

Vuonna 2013 Shuang Chen (陈霜) laski hw -pisteensä 82:sta 57 kierrokseen [80] .

Vuonna 2015 Thomas Rokicki vahvisti huippupisteet 57 hw ja sai uudet huippupisteet 56 hs ja 53 hb [81] . Muutamaa päivää myöhemmin Shuang Chen (陈霜) onnistui saamaan ylärajat 55 hw ja 53 hs määrittelemällä uudelleen todisteen vaiheet [82] [83] .

Nykyiset tunnetut ylemmät ja alemmat pisteet 4 × 4 × 4 -suulakkeelle eri mittareissa näkyvät taulukossa:

Arviot 4x4x4 kuution jumalan lukumäärästä

mittareita	hs	hw	hb	qs	qw	qb
pienempi arvio	32	35	29	37	41	33
huippuarvio	53	55	53	?	?	?

Megaminx

Megaminx on Rubikin kuution yksinkertaisin analogi dodekaedrin muodossa. 12-värisen Megaminxin konfiguraatioiden määrä on 1,01·10 68 .

Vuonna 2012 Herbert Kotsemba määritti Megaminxin jumalaluvun alarajaksi 45 kasvojen kiertoa minkä tahansa kulman läpi tai 55 kiertoa ±72° kulman läpi [84] [85] .
Vuonna 2016 Herbert Kotsemba paransi Megaminxin jumalaluvun alempaa arviota nostaen sen 48 kasvojen kiertoon millä tahansa kulmalla [86] .

Katso myös

Muistiinpanot

↑ 1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; ja Dethridge, J. Jumalan numero on 20 . Haettu 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 21. heinäkuuta 2013.
↑ Generaattorijärjestelmän mukaan, joka koostuu pintojen käännöksistä ±90° ja 180°.
↑ 1 2 3 4 5 Rokicki , T. ja Davidson, M. Jumalan numero on 26 neljänneskierrosmetriikassa . Haettu 4. heinäkuuta 2015. Arkistoitu alkuperäisestä 7. heinäkuuta 2015.
↑ Joyner, 2002 , s. 7.
↑ Moraalisia ja matemaattisia oppitunteja Rubikin kuutiosta // Uusi tutkija. – 1982.
↑ 1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. Kuutio: Lopullinen opas maailman myydyimpään palapeliin – salaisuuksia, tarinoita, ratkaisuja . - 2009. - S. 26. - 142 s.
↑ Jaap Scherphuis. Hyödyllinen matematiikka . Mittarit (englanniksi) (downlink) . Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 24. marraskuuta 2012.
↑ Jerry Bryan. Merkintäsopimus (27. toukokuuta 2006). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014. (määrätön)
↑ David Singmaster. Kuutio pyöreä . - 1982. - Iss. 5 & 6 . - s. 26 .
↑ Jaap Scherphuis. Palapelin tilastot . Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 21. kesäkuuta 2013.
↑ Schönert, Martin Analysoi Rubikin kuutiota GAP :n avulla . Käyttöpäivä: 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 20. tammikuuta 2013.
↑ Jaap Scherphuis. Rubikin kuutio 3x3x3 (englanniksi) (linkki ei saatavilla) . Haettu 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 28. heinäkuuta 2013.
↑ Joyner, 2008 , s. 93 , 108.
↑ 1 2 Herbert Kociemba. Kaksivaiheinen algoritmi ja Jumalan algoritmi: Jumalan luku on 20 (englanniksi) (linkki ei ole käytettävissä) . Käyttöpäivä: 23. heinäkuuta 2013. Arkistoitu alkuperäisestä 2. toukokuuta 2013.
↑ Tomas Rokicki, Herbert Kociemba, Morley Davidson ja John Dethridge. Rubikin kuutioryhmän halkaisija on kaksikymmentä // SIAM J. Discrete Math.. - 2013. - Vol. 27, nro. 2. - P. 1082-1105. - doi : 10.1137/120867366 .
↑ 1 2 3 4 Rik van Grol. Jumalan numeron etsintä . Math Horizons (marraskuu 2010). Haettu 26. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014.
↑ Stefan Edelkamp, Stefan Schrōdl. Heuristinen haku: teoria ja sovellukset. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
↑ SIAM J. Discrete Math., 27(2), 1082–1105 . Haettu 19. marraskuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2019. (määrätön)
↑ "Ratkaistava" kokoonpano on konfiguraatio, joka voidaan kääntää käännetyksi. Koska Rubikin kuution kuvaaja on suuntaamaton, tästä seuraa, että mikä tahansa alkuperäisestä mielivaltaisesta liikesarjasta saatu konfiguraatio on päätettävissä. Mutta on ratkaisemattomia kokoonpanoja. Esimerkiksi jos yhtä kuution kärkeä kierretään 120° kootussa tilassa, saadaan ratkaisematon konfiguraatio.
↑ 1 2 3 4 5 6 7 8 V. Dubrovsky, A. Kalinin. Kubologian uutisia // Kvant . - 1992. - Nro 11 . - S. 52-56 .
↑ Jaap Scherphuis. Hyödyllinen matematiikka . Jumalan algoritmi (englanniksi) (linkki ei saatavilla) . Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 24. marraskuuta 2012.
↑ Michael Reid. Michael Reidin Rubikin kuution sivu . M-symmetriset sijainnit (englanniksi) (24. toukokuuta 2005) . Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 6. heinäkuuta 2015.
↑ David Singmaster. Kuutio pyöreä . - 1982. - Iss. 5 & 6 . - s. 24 .
↑ Joyner, 2002 , s. 149.
↑ 1 2 3 4 Stefan Pochmann. Ihmisten ratkaisumenetelmien analysointi Rubikin kuutioon ja vastaaviin palapeliin (diplomityö ) . Arkistoitu alkuperäisestä 9. marraskuuta 2014.
↑ Dik T. Talvi. Kociemban algoritmi (englanniksi) (18. toukokuuta 1992). Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 15. heinäkuuta 2013.
↑ Michael Reid. superflip vaatii 20 kasvojen käännöstä ( 18. tammikuuta 1995). Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 8. heinäkuuta 2013.
↑ Michael Reid. superflip (englanniksi) (10. tammikuuta 1995). Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 19. kesäkuuta 2014.
↑ Jerry Bryan. Qturn Lengths of M-Symmetric Positions ( 19. helmikuuta 1995). Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 20. kesäkuuta 2014.
↑ 12 Michael Reid . neljällä pisteellä sävelletty superflip (englanniksi) (2. elokuuta 1998). Haettu 4. heinäkuuta 2015. Arkistoitu alkuperäisestä 4. lokakuuta 2015.
↑ L. A. Kalužnin, V. I. Sushchansky. Muunnokset ja permutaatiot. - M. , 1985. - S. 143. - 160 s.
↑ David Singmaster. Huomautuksia Rubikin taikakuutiosta (uus.) . — Enslow Publishers, 1981. - S. 30 .
↑ V. Dubrovsky. Magic Cube -algoritmi // Kvant . - 1982. - Nro 7 . - S. 22-25 .
↑ Tämän ja kolmen seuraavan ryhmän järjestys lasketaan kolmen tekijän tulona, jotka osoittavat vastaavasti selvitettävien kulmakonfiguraatioiden lukumäärän, selvitettävien reunakonfiguraatioiden lukumäärän ja ratkaistavan konfiguraation yleisen "pariteettirajoitteen".
↑ Jaap Scherphuis. Kuutioiden alaryhmät . Kasvojen liikkeiden luomat alaryhmät (eng.) (linkki ei käytettävissä) . Käyttöpäivä: 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 20. tammikuuta 2013.
↑ Mark Longridge. Progressiiviset parannukset algoritmien ratkaisuun . Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. lokakuuta 2013.
↑ V. Dubrovsky. Taikakuution matematiikka // Kvant . - 1982. - Nro 8 . - S. 22-27, 48 .
↑ Jaap Scherphuis. Thistlethwaiten 52 liikkeen algoritmi . Haettu 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 28. heinäkuuta 2013.
↑ 12 silviu . Rubik voidaan ratkaista 27f:ssä . Cube Forumin verkkotunnus (1. huhtikuuta 2006). Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 27. elokuuta 2013. (määrätön)
↑ 1 2 Kunkle, D.; Cooperman, C. (2007). "Kaksikymmentäkuusi liikettä riittää Rubikin kuutiolle" (PDF) . Kansainvälisen Symposiumin Symposium on Symbolic and Algebraic Computation (ISSAC '07) julkaisut . ACM Press. Arkistoitu (PDF) alkuperäisestä 2019-02-18 . Haettu 17.07.2013 . Käytöstä poistettu parametri |deadlink=( ohje )
↑ Michael Reid. jumalan luvun yläraja (englanniksi) (29. huhtikuuta 1992). Käyttöönottopäivä: 17. heinäkuuta 2013. Arkistoitu alkuperäisestä 24. elokuuta 2013.
↑ Michael Reid. uusi yläraja (englanniksi) (22. toukokuuta 1992). Haettu 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 24. elokuuta 2013.
↑ Dik T. Talvi. Korjatut laskelmat on nyt tehty. (englanniksi) (28. toukokuuta 1992). Haettu 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 20. kesäkuuta 2014.
↑ Ryan Heise. Human Thistlethwaite -algoritmi . Käyttöpäivä: 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 2. elokuuta 2016.
↑ 1 2 3 4 Herbert Kociemba. Kaksivaiheisen algoritmin tiedot . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 2. toukokuuta 2013.
↑ 1 2 3 4 Jaap Scherphuis. Tietokone hämmentävää . Kociemban algoritmi . Haettu 23. heinäkuuta 2013. Arkistoitu alkuperäisestä 25. kesäkuuta 2013.
↑ Herbert Kociemba. Alaryhmä H ja sen kosetit . Haettu 23. heinäkuuta 2013. Arkistoitu alkuperäisestä 22. toukokuuta 2013.
↑ 1 2 3 Herbert Kociemba. Kaksivaiheinen algoritmi . Käyttöpäivä: 23. heinäkuuta 2013. Arkistoitu alkuperäisestä 2. toukokuuta 2013.
↑ Bijektio konfiguraatioiden ja koordinaattien kolmoiskappaleiden välillä Wayback Machinen 2. toukokuuta 2013 arkistoitu kopio on asetettu siten, että ensimmäisen vaiheen kohdeasettelu (eli mikä tahansa kokoonpano ryhmästä G 1 ) vastaa kolmiota (0 , 0, 0).
↑ 1 2 3 Stuart Russell, Peter Norvig. Hyväksyttyjen heurististen funktioiden kokoaminen // Tekoäly: moderni lähestymistapa = Artificial Intelligence: A Modern Approach. - 2. painos - M. : Williams, 2006. - S. 170 - 173. - 1408 s. — ISBN 5-8459-0887-6 .
↑ Englanti. kuviotietokannat . Algoritmin kirjoittajan esityksessä Arkistokopio , joka on päivätty 2. toukokuuta 2013 Wayback Machinessa - "leikkaustaulukot".
↑ Alkioiden permutaatioiden pariteettirajoituksesta johtuen vain puolet kaikista koordinaattikolmoista esiintyy.
↑ Herbert Kociemba. Leikkaustaulukot . _ Käyttöpäivä: 23. heinäkuuta 2013. Arkistoitu alkuperäisestä 2. toukokuuta 2013.
↑ Herbert Kociemba. Lataa (englanniksi) . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 2. toukokuuta 2013.
↑ Eric Dietz. Ratkaise kuutiosi alle 25 liikkeellä . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. tammikuuta 2022.
↑ Michael Reid. uudet ylärajat (englanniksi) (7. tammikuuta 1995). Haettu 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 24. elokuuta 2013.
↑ 1 2 Richard E. Korf. Optimaalisten ratkaisujen löytäminen Rubikin kuutioon kuviotietokantojen avulla . – 1997.
↑ Arthur Fisher . Rubik's Reduced (englanti) , Popular Science (lokakuu 1997), s. 58.
↑ Michael Reid. Rubikin kuution sivu . Optimaalinen Rubikin kuution ratkaisija (28. lokakuuta 2006) . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 5. heinäkuuta 2015. (määrätön)
↑ Silviu Radu, Rubikin kuutioryhmän uusi yläraja, arΧiv : math/0512485 .
↑ silviu. Rubik voidaan ratkaista 35q:ssa . Cube Forumin verkkotunnus (22. maaliskuuta 2006). Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014. (määrätön)
↑ Koillisyliopiston tutkijat ratkaisevat Rubikin kuution 26 liikkeessä . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 23. lokakuuta 2019. (määrätön)
↑ Tom Rokicki, Kaksikymmentäviisi liikettä riittää Rubikin kuutiolle, arΧiv : 0803.3435 .
↑ kivinen. Kaksikymmentäkolme liikettä riittää . Cube Forumin verkkotunnus (29. huhtikuuta 2008). Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 27. elokuuta 2013. (määrätön)
↑ kivinen. Kaksikymmentäkaksi liikettä riittää (linkki ei käytettävissä) . Cube Forumin verkkotunnus (12. elokuuta 2008). Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 5. joulukuuta 2011. (määrätön)
↑ kivinen. Kaksikymmentäyhdeksän QTM-liikettä riittää . Cube Forumin verkkotunnus (15. kesäkuuta 2009). Käyttöpäivä: 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 26. heinäkuuta 2011. (määrätön)
↑ 1 2 Adam P. Goucher. Superflip sävelletty nelipisteellä . Complex Projective 4-Space (25.9.2015). Haettu 23. lokakuuta 2015. Arkistoitu alkuperäisestä 1. helmikuuta 2016. (määrätön)
↑ 1 2 Jaap Scherphuis. Cayley Graphs . Etäisyydet (englanniksi) . Haettu 4. heinäkuuta 2015. Arkistoitu alkuperäisestä 6. heinäkuuta 2015.
↑ 1 2 Tunnettu etäisyys-20 sijaintia puolikierrosmetriikassa. Tunnetut etäisyys-24 tai suuremmat sijainnit neljänneskierroksen metriikassa . Haettu 4. heinäkuuta 2015. Arkistoitu alkuperäisestä 29. kesäkuuta 2015. (määrätön)
↑ Kauniita kuvioita Rubikin kuutio | Edge Flip, Dot | Superflip, 4 pistettä . Haettu 4. heinäkuuta 2015. Arkistoitu alkuperäisestä 5. heinäkuuta 2015. (määrätön)
↑ Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Saara; Lubiw, Anna & Winslow, Andrew (2011), Algorithms for Solving Rubikin kuutiot, arΧiv : 1106.5736v1 [cs.DS].
↑ Larry Hardesty. Rubikin kuution matematiikka . Uusi tutkimus osoittaa suhteen Rubikin kuutiotyyppisen pulman neliöiden lukumäärän ja sen ratkaisemiseen vaadittavien liikkeiden enimmäismäärän välillä . MIT News Office (29. kesäkuuta 2011) . Haettu 23. heinäkuuta 2013. Arkistoitu alkuperäisestä 19. syyskuuta 2013.
↑ kivinen. Tyhjän kuution halkaisija vähintään 20 (pinnan kääntömetriikka) . Cube Forumin verkkotunnus (19. tammikuuta 2010). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014. (määrätön)
↑ kivinen. Tyhjän kuution halkaisija vähintään 20 (todennäköisesti 20) . Speedsolving.com (19. tammikuuta 2010). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014. (määrätön)
↑ Jaap Scherphuis. Rubikin kosto . Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 27. heinäkuuta 2013.
↑ 1 2 Bruce Norskog. Uudet ylärajat: 82 kierrekierrosta, 67 lohkokierrosta . Cube Forumin verkkotunnus (13. elokuuta 2007). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 29. toukokuuta 2014. (määrätön)
↑ Bruce Norskog. 4x4x4 voidaan ratkaista 77 yhden viipaleen kierroksella . Cube Forumin verkkotunnus (26. heinäkuuta 2007). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 29. toukokuuta 2014. (määrätön)
↑ Isompi rubikin kuutio sidottu (downlink) . Projekti Euler. Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 29. toukokuuta 2014. (määrätön)
↑ kivinen. Alarajat nxnxn Rubikin kuutioille (n=20 asti) kuudessa metriikassa . Cube Forumin verkkotunnus (18. heinäkuuta 2011). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014. (määrätön)
↑ CS. 4x4x4:n ratkaiseminen 57 liikkeessä (OBTM) . Cube Forumin verkkotunnus (30. syyskuuta 2013). Haettu 19. marraskuuta 2013. Arkistoitu alkuperäisestä 26. marraskuuta 2013. (määrätön)
↑ kivinen. 4x4x4 ylärajat: 57 OBTM vahvistettu; 56 SST ja 53 BT laskettu. . Cube Forumin verkkotunnus (3. maaliskuuta 2015). Haettu 1. heinäkuuta 2015. Arkistoitu alkuperäisestä 29. toukokuuta 2015. (määrätön)
↑ CS. 4x4x4 uusi yläraja: 55 OBTM . Cube Forumin verkkotunnus (3. heinäkuuta 2015). Haettu 1. heinäkuuta 2015. Arkistoitu alkuperäisestä 29. toukokuuta 2015. (määrätön)
↑ CS. 4x4x4 uusi yläraja: 53 SSTM . Cube Forumin verkkotunnus (3. syyskuuta 2015). Haettu 1. heinäkuuta 2015. Arkistoitu alkuperäisestä 29. toukokuuta 2015. (määrätön)
↑ Herbert Kociemba. Megaminx tarvitsee vähintään 45 liikettä . Cube Forumin verkkotunnus (28. helmikuuta 2012). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014. (määrätön)
↑ Herbert Kociemba. Megaminxin alaraja htm ja qtm . Speedsolving.com (3. tammikuuta 2012). Haettu 28. heinäkuuta 2013. Arkistoitu alkuperäisestä 9. marraskuuta 2014. (määrätön)
↑ Megaminxin alaraja htm ja qtm . Haettu 2. syyskuuta 2016. Arkistoitu alkuperäisestä 17. syyskuuta 2016. (määrätön)

Suositeltu lukema

V. Zalgaller, S. Zalgaller. Unkarilainen nivelkuutio // Kvant . - 1980. - Nro 12 . - S. 17 - 21 . (Venäjän kieli)
V. Dubrovsky. Magic Cube -algoritmi // Kvant . - 1982. - Nro 7 . - S. 22-25 . (Venäjän kieli)
V. Dubrovsky. Taikakuution matematiikka // Kvant . - 1982. - Nro 8 . - S. 22 - 27, 48 . (Venäjän kieli)
V. Dubrovsky, A. Kalinin. Kubologian uutisia // Kvant . - 1992. - Nro 11 . - S. 52 - 56 . (Venäjän kieli)
L. A. Kaluzhnin, V. I. Sushchansky. Muunnokset ja permutaatiot. - M. , 1985. - S. 143. - 160 s.
David Singmaster. Kuutio pyöreä . - 1981 - 1985.
David Singmaster, Alexander Frey. Cubik Math -käsikirja. – 1987.
David Joyner. Seikkailut ryhmäteoriassa: Rubikin kuutio, Merlinin kone ja muut matemaattiset lelut . - Baltimore: Johns Hopkins University Press, 2002. - ISBN 0-8018-6947-1 .
David Joyner. Seikkailut ryhmäteoriassa: Rubikin kuutio, Merlinin kone ja muut matemaattiset lelut . - Toinen painos. - 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. Algoritmit Rubikin kuutioiden ratkaisemiseksi // Tietojenkäsittelytieteen luentomuistiinpanot. - 2011. - T. 6942 . - S. 689-700 . - doi : 10.1007/978-3-642-23719-5_58 .

Linkit

Konstantin Knop. Rubikin kuutio: Assault on the Stronghold . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 20. lokakuuta 2009. (Venäjän kieli)
Rik van Grol. Jumalan numeron etsintä . Math Horizons (marraskuu 2010). Haettu: 26. heinäkuuta 2013.

Uusintapainos: Rik van Grol. The Quest for God's Number // Paras matematiikan kirjoitus 2011 / Mircea Pitici, Freeman Dyson . - Princeton University Press , 2011. - s. 27-34. — 416 s. - ISBN 1-400-83954-8 , 978-1-400-83954-4.

Jaap Scherphuis. Jaapin palapelisivu . - Valikoima tietoa erilaisista pulmapeleistä ja menetelmistä niiden ratkaisemiseksi. Haettu: 20. heinäkuuta 2013.
Herbert Kociemba. Cube Explorer 5.01 (englanniksi) . — Herbert Kotsemban kotisivu. Yksityiskohtainen kuvaus Cube Explorer -ohjelmassa käytetyistä algoritmeista. Haettu: 20. heinäkuuta 2013.
Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. Jumalan numero on 20 (englanniksi) . Haettu: 20. heinäkuuta 2013.
Martin Schönert. Cube Lovers - arkistot muutettu HTML - muotoon . — 1947 artikkelia heinäkuun 1980 ja kesäkuun 1996 välisenä aikana. Haettu 20. heinäkuuta 2013.
Mark Longridge. Kuutiofoorumin verkkotunnus . - Keskusteluja kuution matematiikasta. Haettu: 20. heinäkuuta 2013.
WD Joyner. Luentomuistiinpanot Rubikin kuution matematiikasta (englanniksi) (linkki ei saatavilla) . Haettu 22. heinäkuuta 2013. Arkistoitu alkuperäisestä 5. syyskuuta 2013.
Tomas Rokicki. Tietokoneet ja kuutio (diat) (englanniksi) (3. marraskuuta 2009). — MATH 78SI : Speedcubing: historia, teoria ja käytäntö . Opiskelijoiden aloittama kurssi Stanfordissa (syksy 2009). Haettu: 30. heinäkuuta 2013.