Matematika Rubikovy kostky

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. července 2021; kontroly vyžadují 17 úprav .

Matematika Rubikovy kostky

Mediální soubory na Wikimedia Commons

Matematika Rubikovy kostky je soubor matematických metod pro studium vlastností Rubikovy kostky z abstraktního matematického hlediska. Tento obor matematiky studuje algoritmy sestavování krychle a vyhodnocuje je. Založeno na teorii grafů , teorii grup , teorii vyčíslitelnosti a kombinatorice .

Existuje mnoho algoritmů navržených pro převod Rubikovy kostky z libovolné konfigurace do konečné konfigurace (složené kostky). V roce 2010 bylo důsledně prokázáno, že k převedení Rubikovy kostky z libovolné konfigurace do sestavené konfigurace (často nazývané „sestavení“ nebo „řešení“) nestačí více než 20 otočení čel [1] . Toto číslo je průměrem Cayleyho grafu skupiny Rubikovy kostky [2] . V roce 2014 bylo prokázáno, že k vyřešení Rubikovy kostky stačí vždy 26 tahů pouze pomocí 90° otočení ploch [3] .

Algoritmus, který řeší hádanku co nejmenším počtem tahů, se nazývá Boží algoritmus .

Notace

Tento článek používá "Singmaster notation" [4] [5] vyvinutý Davidem Singmasterem a publikovaný jím v roce 1981 k označení sledu rotace tváří 3×3×3 Rubikovy kostky .

Písmena představují otočení o 90° ve směru hodinových ručiček levého ( vlevo ), pravého ( pravého ), předního ( předního ), zadního ( zadního ), horního ( nahoru ) a spodního ( dolů ) čela. Otoky o 180° jsou označeny přidáním 2 vpravo od písmene nebo přidáním horního indexu 2 vpravo od písmene. Otočení o 90° proti směru hodinových ručiček je indikováno přidáním pomlčky ( ′ ) nebo přidáním horního indexu -1 napravo od písmene. Takže například položky a jsou ekvivalentní, stejně jako položky a . $L,R,F,B,U,D$ $L^{2}$ $L2$ $L'$ $L^{{-1}}$

Metriky konfiguračního grafu

Existují dva nejběžnější způsoby měření délky řešení ( metrický ). První způsob - jedno otočení řešení je považováno za otočení čela o 90° ( quarter turn metric , QTM ). Podle druhého způsobu je uvažováno i poloviční otočení plochy na 1 tah ( face turn metric , FTM , někdy se označuje HTM - half-turn metric ). F2 (otočení přední strany o 180°) by se tedy mělo počítat jako dva tahy v metrice QTM nebo 1 tah v metrice FTM [6] [7] .

Pro označení délky posloupnosti u použité metriky v textu slouží zápis [8] [9] [10] , složený z čísel počtu tahů a prvního malého písmene označení metriky. 14f znamená „14 tahů v metrice FTM“ a 10q znamená „10 tahů v metrice QTM“. K označení, že počet tahů je minimální v dané metrice, se používá hvězdička : 10f* označuje optimalitu řešení v 10 FTM tahech.

Skupina Rubikovy kostky

Rubikova kostka může být viděna jako příklad matematické grupy .

Každou ze šesti rotací ploch Rubikovy kostky lze považovat za prvek symetrické skupiny množiny 48 štítků Rubikovy kostky, které nejsou středy ploch. Přesněji řečeno, lze označit všech 48 štítků čísly od 1 do 48 a přiřadit každému z tahů prvek symetrické skupiny . $\{F,B,U,D,L,R\}$ $S_{{48}}$

Potom je skupina Rubikovy kostky definována jako podskupina generovaná šesti rotacemi ploch: $G$ $S_{{48}}$

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

Skupinové pořadí je [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.

Každou z konfigurací lze vyřešit nanejvýš 20 tahy (pokud za tah počítáme jakékoli otočení obličeje) [1] . $4{,}325\cdot 10^{19}$

Nejvyšší řád prvku v je 1260. Například sekvence tahů se musí opakovat 1260krát, než se Rubikova kostka vrátí do původního stavu [13] . $G$ $(R\ U^{2}\ D^{{\prima }}\ B\ D^{{\prima }})$

Boží algoritmus

Hledání Božího algoritmu začalo nejpozději v roce 1980, kdy byl otevřen mailing list pro fanoušky Rubikovy kostky [6] . Od té doby se matematici, programátoři a amatéři snažili najít Boží algoritmus tak, aby v praxi s minimálním počtem tahů vyřešili Rubikovu kostku. S tímto problémem souvisel problém určení čísla Boha – počtu tahů, který je vždy dostatečný k dokončení hádanky.

V roce 2010 programátor Palo Alto Thomas Rokiki, učitel matematiky v Darmstadtu Herbert Kotsemba, matematik Morley Davidson z University of Kent a inženýr společnosti Google Inc. John Dethridge dokázal, že Rubikovu kostku z jakéhokoli rozloženého stavu lze sestavit na 20 tahů. V tomto případě bylo jakékoli otočení obličeje považováno za jeden pohyb. Množství výpočtů bylo 35 let CPU času darovaného společností Google [1] [14] [15] . Technické údaje o výkonu a počtu počítačů nebyly zveřejněny. Doba výpočtů byla několik týdnů [16] [17] [18] .

V roce 2014 Thomas Rockicki a Morley Davidson dokázali, že Rubikovu kostku lze vyřešit nanejvýš 26 tahy bez použití otočení o 180°. Objem výpočtů byl 29 let procesorového času v superpočítačovém centru Ohio [3] .

Dolní hranice pro číslo Boha

Je snadné ukázat, že existují řešitelné konfigurace [19] , které nelze vyřešit za méně než 17 tahů v metrice FTM nebo 19 tahů v metrice QTM.

Tento odhad lze vylepšit zohledněním dalších identit: komutativnosti rotací dvou protilehlých ploch (LR = RL, L2 R = R L2 atd.) Tento přístup umožňuje získat spodní hranici pro číslo Boha v 18f nebo 21q [20] [21] .

Tento odhad je dlouhodobě nejznámější. Vyplývá to z nekonstruktivního důkazu, protože neuvádí konkrétní příklad konfigurace, která vyžaduje k sestavení 18f nebo 21q.

Jednou z konfigurací, pro kterou nebylo možné nalézt žádné krátké řešení, byl takzvaný „ superflip “ nebo „12-flip“. V "Superflip" jsou všechny rohové a hranové kostky na svých místech, ale každá hranová kostka je orientována opačně [22] . Vrchol odpovídající superflipu v grafu Rubikovy kostky je lokální maximum: jakýkoli pohyb z této konfigurace snižuje vzdálenost k počáteční konfiguraci. To naznačuje, že superflip je v maximální vzdálenosti od počáteční konfigurace. To znamená, že superflip je globální maximum [23] [24] [25] .

V roce 1992 našel Dick T. Winter řešení superflipu v 20f [26] . V roce 1995 Michael Reed prokázal optimálnost tohoto řešení [27] , v důsledku čehož se dolní mez pro číslo Boha stala 20 FTM. V roce 1995 objevil Michael Reid řešení „superflipu“ v 24q [28] . Optimálnost tohoto řešení dokázal Jerry Bryan [29] . V roce 1998 našel Michael Reed konfiguraci, jejíž optimální řešení bylo 26q* [30] .

Horní hranice pro Boží číslo

Chcete-li získat horní hranici pro Boží číslo, stačí zadat jakýkoli algoritmus sestavení puzzle skládající se z konečného počtu tahů.

První horní hranice pro číslo Boha byly založeny na „lidských“ algoritmech skládajících se z několika stupňů. Sečtením odhadů shora pro každou z fází bylo možné získat konečný odhad v řádu několika desítek či stovek tahů.

Pravděpodobně první konkrétní odhad shora uvedl David Singmaster v roce 1979. Jeho montážní algoritmus umožňoval sestavení hlavolamu na více než 277 tahů [16] [31] . Singmaster později uvedl, že Alvin Berlekamp , John Conway a Richard Guy vyvinuli algoritmus sestavování, který nevyžaduje více než 160 pohybů. Brzy skupina „Conwayových cambridgeských kubistů“, kteří sestavovali seznam kombinací pro jednu tvář, našla 94směrný algoritmus [16] [32] . V roce 1982 časopis Kvant zveřejnil seznam kombinací, které umožňují vyřešit Rubikovu kostku v 79 tazích [33] .

Thistlethwaiteho algoritmus

Na začátku 80. let anglický matematik Morvin Thistlethwaite vyvinul algoritmus, který výrazně zlepšil horní hranici. Podrobnosti o algoritmu publikoval Douglas Hofstadter v roce 1981 ve Scientific American . Algoritmus byl založen na teorii grup a zahrnoval čtyři fáze.

Popis

Thistlethwaite použil řadu podskupin délky 4

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

kde

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

Tato skupina je stejná jako skupina Rubikova kostka . Jeho pořadí je [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 .$

Tato podskupina zahrnuje všechny konfigurace, které lze řešit bez použití rotace levé nebo pravé strany o ±90°. Jeho pořadí je

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

Tato podskupina zahrnuje všechny konfigurace, které lze vyřešit za předpokladu, že je zakázáno otáčení čtyř svislých ploch o ±90°. Jeho pořadí je

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

Tato podskupina zahrnuje všechny konfigurace, které lze řešit pouze pomocí otočení o 180° (půlotáček). Říkalo se tomu „skupina čtverců“ (skupina čtverců). Jeho pořadí je

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

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

Tato podskupina obsahuje jedinou počáteční konfiguraci.

V první fázi je libovolně daná konfigurace ze skupiny redukována na konfiguraci ležící v podskupině . Cílem druhé fáze je uvést krychli do konfigurace v podskupině bez použití rotace levé a pravé plochy o ±90°. Ve třetí fázi je Rubikova kostka redukována na konfiguraci patřící do skupiny , přičemž otáčení svislých ploch o ±90° je zakázáno. V poslední, čtvrté fázi je Rubikova kostka kompletně sestavena otočením čel o 180°. $G$ $G_{1}$ $G_{2}$ $G_{3}$

Indexy podskupin jsou 2048, 1082565, 29400 a 663552, v tomto pořadí. $[G_{i}:G_{{i+1}}]$ $i=0,1,2,3$

Pro každou ze čtyř rodin pravých coset je vytvořena vyhledávací tabulka , jejíž velikost odpovídá indexu podskupiny ve skupině . Pro každou třídu sousedství podskupiny obsahuje vyhledávací tabulka sekvenci pohybů, které převádějí jakoukoli konfiguraci z této třídy sousedství do konfigurace, která leží v samotné podskupině . $G_{i}/G_{{i+1}}$ $T_{i}$ $G_{{i+1}}$ $G_{i}$ $G_{{i}}$ $T_{i}$ $G_{i}$

Aby se snížil počet záznamů ve vyhledávacích tabulkách, Thistlethwaite použil zjednodušené předběžné tahy. Původně obdržel skóre 85 tahů. Během roku 1980 bylo toto skóre sníženo na 80 tahů, poté na 63 a 52 [16] [36] . Thistlethwaiteovi studenti provedli úplnou analýzu každé z fází. Maximální hodnoty v tabulkách jsou 7, 10, 13 a 15 FTM zdvihů. Protože 7 + 10 + 13 + 15 = 45, lze Rubikovu kostku vždy vyřešit tahy 45 FTM [25] [37] [38] .

Hrabě Schreier

Schreierův graf je grafspojený se skupinou, generující množinou a podskupinou. Každý vrchol Schreierova grafu jepro některé. Hrany hraběte Schreiera jsou dvojice. $S(G,X,H)$ $G$ $X=\{x_{i}|i\v I\}$ $H\subseteq G$ $Hg=\{hg|h\in H\}$ $g\in G$ $(Hg,Hgx_{i})$

Každá ze čtyř fází Thistlethwaitova algoritmu je procházením Schreierova grafu v první šířce , kde je generující množina grupy . $S_{i}(G_{i},X_{i},G_{{i+1}})$ $X_{i}$ $G_{i}$

Horní odhad je tedy 45 tahů

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

kde

\epsilon(v_{i})

je excentricita vrcholu odpovídající jednotkové coset .

v_{i}\in S_{i}

G_{{i+1}}

Pojem Schreierův graf byl použit v pracích Radu [39] , Kunkleho a Coopermana [40] .

Modifikace thistlethwaiteho algoritmu

V prosinci 1990 Hans Kloosterman použil upravenou verzi Thistlethwaiteovy metody k prokázání dostatečnosti 42 tahů [1] [20] [41] .

V květnu 1992 Michael Reid ukázal, že 39f nebo 56q je dostačující [42] . V jeho modifikaci byl použit následující řetězec podskupin:

$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\}$

O několik dní později Dick T. Winter snížil své skóre FTM na 37 tahů [43] .

V prosinci 2002 Ryan Hayes vyvinul verzi Thistlethwaiteova algoritmu navrženou k rychlému vyřešení Rubikovy kostky [44] .

Dvoufázový algoritmus Kotsemba

Thistlethwaiteův algoritmus byl vylepšen v roce 1992 Herbertem Kotsembou, učitelem matematiky z Darmstadtu.

Popis

Kotsemba snížil počet kroků algoritmu na dva [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\}$

Vizuální popis skupiny lze získat, pokud je provedeno následující označení [20] [47] : $G_{1}$

Označte všechny štítky U a D znaménkem „+“.
Štítky F a B na okrajových prvcích FR , FL , BL a BR jsou označeny „-“.
Všechny ostatní štítky ponechte neoznačené.

Pak budou mít všechny konfigurace skupiny stejné označení (shodné s označením na sestavené krychli). $G_{1}$

Řešení se skládá ze dvou fází. V první fázi je daná konfigurace převedena sekvencí pohybů do nějaké konfigurace . Jinými slovy, úkolem první fáze je obnovit označení odpovídající počáteční konfiguraci, přičemž se ignorují barvy štítků. $x\v G_{0}$ $s_{1}$ $x^{{\prime }}\in G_{1}$

Ve druhé fázi je konfigurace převedena sekvencí pohybů do výchozí konfigurace. V tomto případě není použito otočení bočních ploch o ±90°, díky čemuž se označení automaticky uloží. $x^{{\prime }}\in G_{1}$ $s_{2}$

Lepení sekvencí tahů je neoptimální řešení původní konfigurace [20] [46] [48] . $s_{1}$ $s_{2}$

Alternativní suboptimální řešení

Kotsembův algoritmus se po nalezení prvního řešení nezastaví. Alternativní optimální řešení v první fázi mohou vést ke kratším řešením ve druhé fázi, což zkrátí celkovou délku řešení. Algoritmus pokračuje v hledání i neoptimálních řešení v první fázi, aby se zvětšila jejich délka [20] [46] [48] .

Funkce implementace

Pro hledání řešení v každé ze dvou fází se používá algoritmus IDA* s heuristickými funkcemi založenými na nákladech na řešení odpovídajících dílčích úloh [48] .

Úkol první fáze je redukován na nalezení cesty v prostoru se třemi souřadnicemi od označení souřadnicemi ( x 1 , y 1 , z 1 ) po označení (0, 0, 0) [49] :

Orientace x 1 z osmi rohových prvků (2187 hodnot)
Orientace y 1 dvanácti okrajových prvků (2048 hodnot)
Uspořádání z 1 čtyř okrajových prvků FR , FL , BL a BR (495 hodnot)

Zvažte tři dílčí problémy hledání cesty od označení ( x 1 , y 1 , z 1 ) ke značce ( x 1 ', y 1 ', 0), ( x 1 ', 0, z 1 '), (0, y 1 ', z 1 '). Hodnota heuristické funkce h 1 použitá v první fázi je rovna maximálním nákladům na řešení těchto dílčích problémů. Náklady na řešení dílčích úkolů jsou předkalkulovány a uloženy ve formě databází se šablonami [50] [51] .

Úkol druhého stupně je redukován na nalezení cesty v prostoru se třemi souřadnicemi z konfigurace ( x 2 , y 2 , z 2 ) do konfigurace (0, 0, 0) [52] :

Permutace x 2 osm rohových prvků (40320 hodnot)
Permutace y 2 osmi hranových prvků horní a spodní plochy (hodnoty 40320)
Permutace z 2 čtyř okrajových prvků střední vrstvy (24 hodnot)

Zvažte tři dílčí problémy hledání cesty od konfigurace ( x 2 , y 2 , z 2 ) ke konfiguraci ( x 2 ', y 2 ', 0), ( x 2 ', 0, z 2 '), (0, y 2 ', z2 ') . Hodnota heuristické funkce h 2 použitá ve druhé fázi je rovna maximálním nákladům na řešení těchto dílčích problémů.

Algoritmus využívá další optimalizace zaměřené na zvýšení výkonu a snížení paměti zabrané tabulkami [20] [45] [46] [53] .

Softwarové implementace

Cube Explorer je softwarová implementace algoritmu pro OS Windows. Odkazy ke stažení jsou na webu Herberta Kotsemby [54] . V roce 1992 na počítači Atari ST s pamětí 1 MB a frekvencí 8 MHz umožnil algoritmus najít řešení ne delší než 22 tahů během 1-2 minut [20] [45] . Na moderním počítači Cube Explorer umožňuje během několika sekund najít řešení ne delším než 20 tahů pro libovolně danou konfiguraci [45] .

Existuje online verze algoritmu [55] .

Analýza

V roce 1995 Michael Reed ukázal, že první a druhá fáze Kotsembova algoritmu může vyžadovat maximálně 12 a 18 tahů (FTM). Z toho vyplývá, že Rubikovu kostku lze vždy vyřešit za 30 tahů. Dodatečná analýza ukázala, že 29f nebo 42q [25] [56] je vždy dostačující .

Korffův algoritmus

Kotsembův algoritmus vám umožňuje rychle najít krátká, neoptimální řešení. Prokázání optimálnosti nalezeného řešení však může trvat značnou dobu. Bylo zapotřebí specializovaného algoritmu pro nalezení optimálních řešení.

V roce 1997 publikoval algoritmus, který mu umožnil optimálně řešit libovolné konfigurace Rubikovy kostky. Deset náhodně vybraných konfigurací bylo vyřešeno ne více než 18 FTM tahy [57] [58] .

Samotný Korffův algoritmus funguje následovně. Nejprve jsou určeny podproblémy, které jsou dostatečně jednoduché na provedení úplného výčtu. Byly použity následující tři dílčí úkoly [25] :

Stav skládačky je určen pouze osmi rohovými kostkami, pozice a orientace hran jsou ignorovány.
Stav hádanky je určen šesti z 12 okrajových kostek, ostatní kostky jsou ignorovány.
Stav skládačky určuje dalších šest hracích kostek.

Počet tahů potřebných k vyřešení každého z těchto dílčích problémů je spodní hranicí počtu tahů potřebných k dokončení řešení. Libovolně daná konfigurace Rubikovy kostky je řešena pomocí algoritmu IDA* , který tento odhad využívá jako heuristiku. Náklady na řešení dílčích úkolů jsou uloženy ve formě databází se šablonami [50] [57] .

Přestože tento algoritmus vždy najde optimální řešení, přímo neurčuje, kolik tahů může být zapotřebí v nejhorším případě.

Implementaci algoritmu v C lze nalézt v [59] .

Další vylepšení

V roce 2005 skóre QTM Michaela Reida zlepšilo Silviu Radu na 40q [60] . V roce 2006 Silviu Radu dokázal, že Rubikovu kostku lze vyřešit v 27f [39] nebo 35q [61] .

V roce 2007 Daniel Kunkle a Gene Cooperman použili superpočítač, aby dokázali, že všechny nevyřešené konfigurace lze vyřešit maximálně 26 pohyby FTM. Cílem bylo přenést Rubikovu kostku do jedné z 15 752 podmnožin čtvercových konfigurací , z nichž každou lze nakonec vyřešit několika tahy navíc. Většina konfigurací byla takto vyřešena maximálně na 26 tahů. Zbývající konfigurace byly podrobeny dodatečné analýze, která ukázala, že je lze také vyřešit 26 tahy [40] [62] .

V roce 2008 Thomas Rokicki publikoval výpočetní důkaz řešitelnosti FTM 25-tahové hádanky [63] . V srpnu 2008 Rokiki oznámila důkaz řešitelnosti v 23f [64] . Později se tento odhad zlepšil na 22f [65] . V roce 2009 se mu také podařilo prokázat řešitelnost ve 29 tazích QTM [66] .

V roce 2010 Thomas Rokicki, Herbert Kotsemba, Morley Davidson a John Dethridge oznámili důkaz, že jakoukoli konfiguraci Rubikovy kostky lze vyřešit nanejvýš 20 tahy v metrice FTM [1] [14] . Spolu s dříve známým nižším odhadem 20f* to dokázalo, že číslo boha Rubikovy kostky v metrice FTM je 20.

V srpnu 2014 Rockiki a Davidson oznámili, že Boží číslo pro Rubikovu kostku v metrice QTM je 26 [3] [67] .

Hledat antipody

Konfigurace Rubikovy kostky, která se nachází v maximální vzdálenosti od výchozí konfigurace, se nazývá antipod. Jakýkoli antipod v metrice FTM má optimální řešení v 20f* a jakýkoli antipod v metrice QTM má optimální řešení v 26q* [3] [68] .

Je známo, že v metrice FTM jsou miliony antipodů [69] . Jednou z takových konfigurací je „superflip“. Naopak v metrice QTM je v současnosti známá pouze jedna antipodální konfigurace (nepočítáme-li konfigurace z ní získané rotacemi) - tzv. superflip složený se čtyřmi spoty [30] [67] [68] [70] . Jsou známy pouze dvě konfigurace ve vzdálenosti 25q* od výchozí konfigurace a asi 80 tisíc konfigurací ve vzdálenosti 24q* [3] [69] .

Asymptotické odhady

V roce 2011 se ukázalo, že Boží číslo n × n × n krychle je Θ( n 2 / log( n )) [71] [72] .

Další hádanky

Void Cube

Void Cube je Rubikova kostka 3x3x3 bez centrálních dílků.

Délka optimálního řešení pro "void- superflip " v metrice FTM je 20 [73] [74] , což je důkaz, že je potřeba 20 tahů. Protože Prázdná kostka je oslabeným problémem [50] Rubikovy kostky, platí pro Prázdnou kostku existující důkaz dostatku 20 tahů pro Rubikovu kostku [1] . Proto je Boží číslo prázdné kostky v metrice FTM 20.

Kostka 4×4×4

Počet konfigurací puzzle 4×4×4 ( Eng. Rubik's Revenge ) je [75]

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

Metriky 4×4×4

Existuje několik způsobů, jak určit metriku pro krychli 4x4x4. Tato část používá následující metriky:

qs (čtvrtinový díl): jedno otočení se považuje za otočení kterékoli z 12 vrstev puzzle o ±90°;
qw (quarter twist): za jedno otočení se považuje otočení jakéhokoli vnějšího bloku (tj. pouze ploch nebo ploch s několika sousedními vrstvami v řadě ) o ±90°;
qb (čtvrtblok): za jedno otočení se považuje otočení jakéhokoli vnějšího nebo vnitřního bloku (tj. jakékoli sekvence po sobě jdoucích paralelních vrstev) o ±90° vzhledem ke zbytku puzzle;
hs , hw , hb : Stejné jako předchozí 3 metriky, kromě toho, že jsou povoleny také rotace o 180°.

Délka optimálního řešení libovolné konfigurace v metrice qb není větší než v metrice qw nebo qs , protože v metrice qb jsou povoleny všechny pohyby dalších dvou q-metrik . Totéž platí pro h-metriky.

Odhady počtu kostek Boha 4×4×4

V letech 2006-2007 Bruce Norskog provedl 5-krokovou analýzu kostky 4x4x4, podobnou čtyřkrokové analýze, kterou provedl Thistlethwaite pro Rubikovu kostku 3x3x3. Analýza poskytla horní hranici 82 pohybů v metrice hw [76] , 77 pohybů v metrice hs [77] [78] a 67 pohybů v metrice hb [76] .

V roce 2011 Thomas Rokiki na základě několika existujících myšlenek určil dolní hranice pro číslo Boha v šesti metrikách pro kubické puzzle o velikostech od 2×2×2 do 20×20×20 [79] .

V roce 2013 Shuang Chen (陈霜) snížil své hw skóre z 82 na 57 otáček [80] .

V roce 2015 Thomas Rokicki potvrdil nejvyšší skóre 57 hw a získal nové nejvyšší skóre 56 hs a 53 hb [81] . O několik dní později se Shuang Chen (陈霜) podařilo získat horní hranici 55 hw a 53 hs předefinováním kroků důkazu [82] [83] .

Aktuální známá horní a dolní skóre pro kostku 4×4×4 v různých metrikách jsou uvedeny v tabulce:

4x4x4 Odhad počtu boha kostek

metriky	hs	hw	hb	qs	Q w	qb
nižší odhad	32	35	29	37	41	33
nejvyšší odhad	53	55	53	?	?	?

Megaminx

Megaminx je nejjednodušší obdoba Rubikovy kostky ve formě dvanáctistěnu. Počet konfigurací 12barevného Megaminxu je 1,01· 1068 .

V roce 2012 Herbert Kotsemba určil dolní hranici pro Boží číslo Megaminx na 45 otočení obličeje pod libovolným úhlem nebo 55 otočení pod úhlem ±72° [84] [85] .
V roce 2016 Herbert Kotsemba zlepšil spodní odhad Božího čísla pro Megaminx a zvýšil jej na 48 otočení obličeje o jakýkoli úhel [86] .

Viz také

Poznámky

↑ 1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; a Dethridge, J. Boží číslo je 20 . Získáno 19. července 2013. Archivováno z originálu dne 21. července 2013.
↑ Podle soustavy generátorů, skládající se z natočení čel o ±90° a 180°.
↑ 1 2 3 4 5 Rokicki, T. a Davidson, M. Boží číslo je 26 ve čtvrtotáčkové metrice . Získáno 4. července 2015. Archivováno z originálu dne 7. července 2015.
↑ Joyner, 2002 , str. 7.
↑ Morální a matematické lekce z Rubikovy kostky // New Scientist. — 1982.
↑ 1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. The Cube: The Ultimate Guide to the World's Bestseller Puzzle - Tajemství, příběhy, řešení . - 2009. - S. 26. - 142 s.
↑ Jaap Scherphuis. Užitečná matematika . Metriky (anglicky) (downlink) . Získáno 17. července 2013. Archivováno z originálu dne 24. listopadu 2012.
↑ Jerry Bryan. Notační konvence (27. května 2006). Získáno 28. července 2013. Archivováno z originálu 9. listopadu 2014. (neurčitý)
↑ David Singmaster. Kubický kruhový . - 1982. - Iss. 5 a 6 . — S. 26 .
↑ Jaap Scherphuis. Statistiky hádanek . Získáno 17. července 2013. Archivováno z originálu dne 21. června 2013.
↑ Schönert, Martin Analýza Rubikovy kostky pomocí GAP . Datum přístupu: 19. července 2013. Archivováno z originálu 20. ledna 2013.
↑ Jaap Scherphuis. Rubikova kostka 3x3x3 (anglicky) (nedostupný odkaz) . Získáno 19. července 2013. Archivováno z originálu dne 28. července 2013.
↑ Joyner, 2008 , str. 93 , 108.
↑ 1 2 Herbert Kociemba. Dvoufázový algoritmus a Boží algoritmus: Boží číslo je 20 (anglicky) (odkaz není k dispozici) . Datum přístupu: 23. července 2013. Archivováno z originálu 2. května 2013.
↑ Tomáš Rokicki, Herbert Kociemba, Morley Davidson a John Dethridge. Průměr skupiny Rubikovy kostky je dvacet // SIAM J. Diskrétní matematika.. - 2013. - Sv. 27, č. 2. - S. 1082-1105. - doi : 10.1137/120867366 .
↑ 1 2 3 4 Rik van Grol. Hledání Božího čísla . Matematické obzory (listopad 2010). Získáno 26. července 2013. Archivováno z originálu 9. listopadu 2014.
↑ Stefan Edelkamp, Stefan Schrōdl. Heuristické vyhledávání: teorie a aplikace. - Morgan Kaufmann Publishers , 2012. - 712 s. — ISBN 978-0-12-372512-7 .
↑ SIAM J. Discrete Math., 27(2), 1082–1105 . Získáno 19. listopadu 2013. Archivováno z originálu 3. prosince 2019. (neurčitý)
↑ „Vyřešitelná“ konfigurace je konfigurace, kterou lze přeložit do zkompilované. Protože graf Rubikovy kostky je neorientovaný, vyplývá z toho, že jakákoliv konfigurace získaná z původní libovolné sekvence tahů je rozhodnoutelná. Existují ale neřešitelné konfigurace. Pokud se například jeden z vrcholů krychle ve složeném stavu otočí o 120°, získá se neřešitelná konfigurace.
↑ 1 2 3 4 5 6 7 8 V. Dubrovský, A. Kalinin. Novinky z kubologie // Kvant . - 1992. - č. 11 . - S. 52-56 .
↑ Jaap Scherphuis. Užitečná matematika . God's Algorithm (anglicky) (nedostupný odkaz) . Získáno 17. července 2013. Archivováno z originálu dne 24. listopadu 2012.
↑ Michael Reid. Stránka Rubikova kostka Michaela Reida . M-symetrické pozice (anglicky) (24. května 2005) . Získáno 17. července 2013. Archivováno z originálu dne 6. července 2015.
↑ David Singmaster. Kubický kruhový . - 1982. - Iss. 5 a 6 . — S. 24 .
↑ Joyner, 2002 , str. 149.
↑ 1 2 3 4 Stefan Pochmann. Analýza lidských způsobů řešení Rubikovy kostky a podobných hlavolamů (Diplomová práce ) . Archivováno z originálu 9. listopadu 2014.
↑ Dik T. Zima. Kociembův algoritmus (anglicky) (18. května 1992). Získáno 17. července 2013. Archivováno z originálu 15. července 2013.
↑ Michael Reid. superflip vyžaduje 20 otočení obličeje ( 18. ledna 1995). Získáno 17. července 2013. Archivováno z originálu dne 8. července 2013.
↑ Michael Reid. superflip (anglicky) (10. ledna 1995). Získáno 17. července 2013. Archivováno z originálu 19. června 2014.
↑ Jerry Bryan. Qturn Délky M-symetrických pozic ( 19. února 1995). Získáno 17. července 2013. Archivováno z originálu dne 20. června 2014.
↑ 12 Michael Reid . superflip složený se čtyřmi spoty (anglicky) (2. srpna 1998). Získáno 4. července 2015. Archivováno z originálu dne 4. října 2015.
↑ L. A. Kalužnin, V. I. Suščanskij. Transformace a permutace. - M. , 1985. - S. 143. - 160 s.
↑ David Singmaster. Poznámky k Rubikově kouzelné kostce (neopr.) . — Enslow Publishers, 1981. - S. 30 .
↑ V. Dubrovský. Algoritmus magické kostky // Kvant . - 1982. - č. 7 . - S. 22-25 .
↑ Pořadí této a následujících tří skupin je vypočítáno jako součin tří faktorů udávajících počet rozlišitelných rohových konfigurací, počet řešitelných konfigurací hran a celkové „paritní“ omezení rozlišitelné konfigurace.
↑ Jaap Scherphuis. Podskupiny krychle . Podskupiny generované pohyby obličeje (angl.) (nedostupný odkaz) . Datum přístupu: 19. července 2013. Archivováno z originálu 20. ledna 2013.
↑ Mark Longridge. Progresivní vylepšování algoritmů řešení . Získáno 28. července 2013. Archivováno z originálu 9. října 2013.
↑ V. Dubrovský. Matematika kouzelné kostky // Kvant . - 1982. - č. 8 . - S. 22-27, 48 .
↑ Jaap Scherphuis. Thistlethwaiteův 52- tahový algoritmus . Získáno 17. července 2013. Archivováno z originálu dne 28. července 2013.
↑ 12 silviu . Rubik lze vyřešit v 27f . Doména fóra Cube (1. dubna 2006). Získáno 20. července 2013. Archivováno z originálu dne 27. srpna 2013. (neurčitý)
↑ 1 2 Kunkle, D.; Cooperman, C. (2007). „Pro Rubikovu kostku stačí dvacet šest tahů“ (PDF) . Sborník příspěvků z Mezinárodního sympozia o symbolickém a algebraickém počítání (ISSAC '07) . ACM Press. Archivováno (PDF) z originálu dne 2019-02-18 . Staženo 2013-07-17 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Michael Reid. horní hranice božího čísla (anglicky) (29. dubna 1992). Datum přístupu: 17. července 2013. Archivováno z originálu 24. srpna 2013.
↑ Michael Reid. nová horní vazba (anglicky) (22. května 1992). Získáno 19. července 2013. Archivováno z originálu dne 24. srpna 2013.
↑ Dik T. Zima. Opravené výpočty jsou nyní provedeny. (anglicky) (28. května 1992). Získáno 19. července 2013. Archivováno z originálu dne 20. června 2014.
↑ Ryan Heise. Algoritmus lidského Thistlethwaitea . Datum přístupu: 19. července 2013. Archivováno z originálu 2. srpna 2016.
↑ 1 2 3 4 Herbert Kociemba. Podrobnosti dvoufázového algoritmu . Získáno 20. července 2013. Archivováno z originálu 2. května 2013.
↑ 1 2 3 4 Jaap Scherphuis. Počítačové záhady . Kociembův algoritmus . Získáno 23. července 2013. Archivováno z originálu 25. června 2013.
↑ Herbert Kociemba. Podskupina H a její množiny . Získáno 23. července 2013. Archivováno z originálu dne 22. května 2013.
↑ 1 2 3 Herbert Kociemba. Dvoufázový algoritmus . Datum přístupu: 23. července 2013. Archivováno z originálu 2. května 2013.
↑ Bijekce mezi konfiguracemi a trojice souřadnic Archivovaná kopie z 2. května 2013 na Wayback Machine je nastavena tak, že cílové rozložení prvního stupně (tj. jakákoli konfigurace ze skupiny G 1 ) odpovídá trojici (0 , 0, 0).
↑ 1 2 3 Stuart Russell, Peter Norvig. Kompilace přípustných heuristických funkcí // Umělá inteligence: moderní přístup = Artificial Intelligence: A Modern Approach. - 2. vyd. - M. : Williams, 2006. - S. 170 - 173. - 1408 s. — ISBN 5-8459-0887-6 .
↑ anglicky. databáze vzorů . V prezentaci autora algoritmu Archival copy ze dne 2. května 2013 na Wayback Machine - „prořezávací tabulky“.
↑ Kvůli paritnímu omezení permutace prvků se vyskytuje pouze polovina všech trojic souřadnic.
↑ Herbert Kociemba. Prořezávací stoly . Datum přístupu: 23. července 2013. Archivováno z originálu 2. května 2013.
↑ Herbert Kociemba. Stáhnout (anglicky) . Získáno 20. července 2013. Archivováno z originálu 2. května 2013.
↑ Eric Dietz. Vyřešte svou kostku za méně než 25 tahů . Získáno 20. července 2013. Archivováno z originálu 9. ledna 2022.
↑ Michael Reid. nové horní hranice (anglicky) (7. ledna 1995). Získáno 19. července 2013. Archivováno z originálu dne 24. srpna 2013.
↑ 1 2 Richard E. Korf. Nalezení optimálních řešení pro Rubikovu kostku pomocí databází vzorů . — 1997.
↑ Arthur Fisher . Rubik's Reduced (anglicky) , Popular Science (říjen 1997), s. 58.
↑ Michael Reid. Stránka Rubikova kostka . Optimální řešitel Rubikovy kostky (28. října 2006) . Získáno 20. července 2013. Archivováno z originálu 5. července 2015. (neurčitý)
↑ Silviu Radu, Nová horní hranice skupiny Rubikovy kostky, arΧiv : math/0512485 .
↑ Silviu. Rubik lze vyřešit v 35q . Doména fóra Cube (22. března 2006). Získáno 20. července 2013. Archivováno z originálu 9. listopadu 2014. (neurčitý)
↑ Výzkumníci z Northeastern University vyřeší Rubikovu kostku ve 26 tahech . Získáno 20. července 2013. Archivováno z originálu dne 23. října 2019. (neurčitý)
↑ Tom Rokicki, Dvacet pět tahů stačí pro Rubikovu kostku, arΧiv : 0803.3435 .
↑ rockově. Stačí dvacet tři tahů . Doména fóra Cube (29. dubna 2008). Získáno 20. července 2013. Archivováno z originálu dne 27. srpna 2013. (neurčitý)
↑ rockově. Dvacet dva tahů stačí (nedostupný odkaz) . Doména fóra Cube (12. srpna 2008). Získáno 20. července 2013. Archivováno z originálu 5. prosince 2011. (neurčitý)
↑ rockově. Stačí dvacet devět pohybů QTM . Doména fóra Cube (15. června 2009). Datum přístupu: 20. července 2013. Archivováno z originálu 26. července 2011. (neurčitý)
↑ 1 2 Adam P. Goucher. Superflip složený se čtyřbodovým . Komplexní projektivní 4-prostor (25. září 2015). Získáno 23. října 2015. Archivováno z originálu 1. února 2016. (neurčitý)
↑ 1 2 Jaap Scherphuis. Cayley Graphs . Vzdálenosti (anglicky) . Získáno 4. července 2015. Archivováno z originálu dne 6. července 2015.
↑ 1 2 Známá vzdálenost – 20 pozic v metrice půlotáčku. Známá vzdálenost-24 nebo větší pozice ve čtvrtotáčkové metrice . Získáno 4. července 2015. Archivováno z originálu dne 29. června 2015. (neurčitý)
↑ Pěkné vzory Rubikova kostka | Hrana Flip, tečka | Superflip, se 4 tečkami . Získáno 4. července 2015. Archivováno z originálu 5. července 2015. (neurčitý)
↑ Demaine, Erik D.; Demaine, Martin L.; Eisenštát, Sára; Lubiw, Anna & Winslow, Andrew (2011), Algorithms for Solving Rubik's Cubes, arΧiv : 1106.5736v1 [cs.DS].
↑ Larry Hardesty. Matematika Rubikovy kostky . Nový výzkum stanoví vztah mezi počtem čtverců v hádance typu Rubikova kostka a maximálním počtem tahů potřebných k jejímu vyřešení . News Office MIT (29. června 2011) . Získáno 23. července 2013. Archivováno z originálu 19. září 2013.
↑ rockově. Prázdný průměr krychle alespoň 20 (metrická hodnota otočení lícem) . Doména fóra Cube (19. ledna 2010). Získáno 28. července 2013. Archivováno z originálu 9. listopadu 2014. (neurčitý)
↑ rockově. Průměr prázdné kostky alespoň 20 (pravděpodobně 20) . Speedsolving.com (19. ledna 2010). Získáno 28. července 2013. Archivováno z originálu 9. listopadu 2014. (neurčitý)
↑ Jaap Scherphuis. Rubikova pomsta . Získáno 28. července 2013. Archivováno z originálu dne 27. července 2013.
↑ 1 2 Bruce Norskog. Nové horní hranice: 82 otočení otočením, 67 otočení bloku . Doména fóra Cube (13. srpna 2007). Získáno 28. července 2013. Archivováno z originálu 29. května 2014. (neurčitý)
↑ Bruce Norskog. 4x4x4 lze vyřešit v 77 jednodílných otáčkách . Doména fóra Cube (26. července 2007). Získáno 28. července 2013. Archivováno z originálu 29. května 2014. (neurčitý)
↑ Větší vazba na rubikovou kostku (downlink) . Projekt Euler. Získáno 28. července 2013. Archivováno z originálu 29. května 2014. (neurčitý)
↑ rockově. Dolní hranice pro nxnxn Rubikovy kostky (až n=20) v šesti metrikách . Doména fóra Cube (18. července 2011). Získáno 28. července 2013. Archivováno z originálu 9. listopadu 2014. (neurčitý)
↑ CS. Řešení 4x4x4 v 57 tazích (OBTM) . Doména fóra Cube (30. září 2013). Získáno 19. listopadu 2013. Archivováno z originálu 26. listopadu 2013. (neurčitý)
↑ rockově. 4x4x4 horní hranice: 57 OBTM potvrzeno; Vypočteno 56 SST a 53 BT. . Doména fóra Cube (3. března 2015). Získáno 1. července 2015. Archivováno z originálu 29. května 2015. (neurčitý)
↑ CS. 4x4x4 nová horní hranice: 55 OBTM . Doména fóra Cube (3. července 2015). Získáno 1. července 2015. Archivováno z originálu 29. května 2015. (neurčitý)
↑ CS. 4x4x4 nová horní hranice: 53 SSTM . Doména fóra Cube (3. září 2015). Získáno 1. července 2015. Archivováno z originálu 29. května 2015. (neurčitý)
↑ Herbert Kociemba. Megaminx potřebuje alespoň 45 tahů . Doména fóra Cube (28. února 2012). Získáno 28. července 2013. Archivováno z originálu 9. listopadu 2014. (neurčitý)
↑ Herbert Kociemba. Dolní mez pro Megaminx v htm a qtm . Speedsolving.com (3. ledna 2012). Získáno 28. července 2013. Archivováno z originálu 9. listopadu 2014. (neurčitý)
↑ Dolní mez pro Megaminx v htm a qtm . Získáno 2. září 2016. Archivováno z originálu 17. září 2016. (neurčitý)

Doporučená četba

V. Zalgaller, S. Zalgaller. Maďarská kloubová kostka // Kvant . - 1980. - č. 12 . - S. 17 - 21 . (Ruština)
V. Dubrovský. Algoritmus magické kostky // Kvant . - 1982. - č. 7 . - S. 22-25 . (Ruština)
V. Dubrovský. Matematika kouzelné kostky // Kvant . - 1982. - č. 8 . - S. 22 - 27, 48 . (Ruština)
V. Dubrovský, A. Kalinin. Novinky z kubologie // Kvant . - 1992. - č. 11 . - S. 52 - 56 . (Ruština)
L. A. Kalužnin, V. I. Suščanskij. Transformace a permutace. - M. , 1985. - S. 143. - 160 s.
David Singmaster. Kubický kruhový . - 1981 - 1985.
David Singmaster, Alexander Frey. Příručka Cubik Math. — 1987.
David Joyner. Dobrodružství v teorii grup: Rubikova kostka, Merlinův stroj a další matematické hračky . - Baltimore: Johns Hopkins University Press, 2002. - ISBN 0-8018-6947-1 .
David Joyner. Dobrodružství v teorii skupin: Rubikova kostka, Merlinův stroj a další matematické hračky . - Druhé vydání. - 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. Algoritmy pro řešení Rubikovy kostky // Poznámky k přednášce z informatiky. - 2011. - T. 6942 . - S. 689-700 . - doi : 10.1007/978-3-642-23719-5_58 .

Odkazy

Konstantin Knop. Rubikova kostka: Útok na pevnost . Získáno 20. července 2013. Archivováno z originálu dne 20. října 2009. (Ruština)
Rik van Grol. Hledání Božího čísla . Matematické obzory (listopad 2010). Staženo: 26. července 2013.

Přetištěno v: Rik van Grol. Hledání Božího čísla // Nejlepší psaní o matematice 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. Jaapova stránka s hádankami . - Výběr informací o různých hádankách a metodách jejich řešení. Staženo: 20. července 2013.
Herbert Kociemba. Cube Explorer 5.01 (anglicky) . — Domovská stránka Herberta Kotsemby. Podrobný popis algoritmů používaných v programu Cube Explorer. Staženo: 20. července 2013.
Tomáš Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. Boží číslo je 20 (anglicky) . Staženo: 20. července 2013.
Martin Schönert. Archivy Cube Lovers převedené do HTML . — 1947 článků mezi červencem 1980 a červnem 1996. Staženo 20. července 2013.
Mark Longridge. Doména fóra Cube . — Diskuse o matematice krychle. Staženo: 20. července 2013.
WD Joyner. Poznámky z přednášky o matematice Rubikovy kostky (anglicky) (nedostupný odkaz) . Získáno 22. července 2013. Archivováno z originálu 5. září 2013.
Tomáš Rokicki. Computers and the Cube (slides) (anglicky) (3. listopadu 2009). — MATH 78SI : Speedcubing: Historie, teorie a praxe . Studentský kurz na Stanfordu (podzim 2009). Staženo: 30. července 2013.