Předem upozorňuji, že nástroj pro animace využívá alg.cubing.net. Prohlížeč může vyžadovat znovunačítání rámů těchto simulací (v chrome používám pravý klik na obrázku kostičky).
Běžný smrtelník nevymyslí, jak kostku skládat, ale nemá problém osvojit si někým jiným vymyslený postup. Takové postupy většinou skládají kostku po vrstvách. Člověk dosahuje postupné cíle a k dosažení dalších cílů používá čím dál „opatrnější“ postupy, které pokračují v skládání, a zachovávají to, co už je složené. Při skládání po vrstvách pak v poslední vrstvě někdo nejprve kostičky orientuje a pak umísťuje na místa, někdo jiný nejprve umísťuje na místa a pak teprve orientuje. Otázkou je, zda nám jde o optimalizaci počtu tahů či o čas skládání, do kterého musíme započítat i čas nutný na zorientování se. První český mistr v rychloskládání kostky Jiří Fridrich (nyní Jessica) používal pro každou orientaci kostiček (kterou je snazší zjistit než permutaci) horní vrstvy specializovaný algoritmus. Na správně orientovaných kostičkách pak pro každou permutaci používal opět specializovaný algoritmus (při správné orientaci je snadné permutaci rychle poznat).
Co se týče skládání poslední vrstvy byl Fridrichův algoritmus dobře optimalizovaný. Co se týče skládání prvních dvou vrstev, většina smrtelníků složí kříž, doloží rohy a pak vkládá postupně hrany druhé vrstvy. Přitom algoritmus na vložení hrany druhé vrstvy nejprve odstraní roh z první vrstvy, aby jej pak s hranou vložil zpět. Přirozenou optimalizací je tedy složit jen 3 rohy první vrstvy a před vložením čtvrtého rohu nejprve efektivněji vložit tři hrany druhé vrstvy s využitím volného rohu. Ryan Heise zefektivnil skládání tak, že první dvě vrstvy bez jednoho rohu s hranou skládá najednou. Metodu nazývá metodou 4 čtverců. Vytvoří 4 jednobarevné čtverce velikosti 2x2x1 (s jednou společnou barvou) z nichž pak rychle kýžený výsledek (dvě vrstvy bez rohu s hranou) získá. Heise nepokračuje tak, jak je běžné dokončením dvou vrstev, ale složí nejprve všechny hrany a pak zbylých 5 rohů.
Obě výše uvedené ukázky byly z jedné konkrétní náhodné pozice, nejednalo se o optimální provedení, ale často jsme měli svým způsobem kliku.
Otázka, která trápila spoustu především matematiků či informatiků byla, kolik tahů by stačilo pokud bychom našli skutečně nejkratší možný postup jak kostku složit. Horní odhady je možno získat tak, že si vezmeme nějaký algoritmus rozdělený na postupné kroky a spočítáme, kolik nejvíc času nám může zabrat jeden krok. U dolních odhadů je to složitější, musíme vpodstatě pro každý postup dané délky zkontrolovat, že ke složení kostky nestačí. To je ale nadlidský úkol a přirozeným nápadem je svěřit jej počítači.
Naší výhodou je, že počet zajímavých pozic na kostce je konečný, protože nemusíme zkoumat pozice, kdy je otočena některá stěna například o 35 stupňů, protože jediné smysluplné pokračování je pohyb dokončit na celých 90 stupňů, když už jsme se jej rozhodli začít (něco jiného by bylo, kdybychom kostku chtěli rozebrat na součástky). Nevýhodou je, že tento počet je tak velký, že nemáme prostor na uchování všech možných pozic na kostce (na standardně obarvené kostce můžeme otáčením získat 12!*8!*3^8*2^12/(2*2*3)=43252003274489856000). Pokud bychom na reprezentaci každé pozice potřebovali byť jen jediný bit, potřebovali bychom cca 5.4*10^18 bytů, neboli pohybujeme se v řádu milionů terabytů.
Přeformulovat úlohu složení kostky do teorie grafů je jednoduché: Je potřeba v grafu všech možných pozic na kostce najít nejkratší cestu z dané pozice do pozice složené kostky. Potíž je ale výše zmíněná velikost grafu. Dobrá zpráva ale je, že vzhledem k jednoduchým pravidlům je jednoduché se po vrcholech daného grafu pohybovat aniž bychom graf měli explicitně reprezentován (snadno poznáme, zda z jedné pozice můžeme druhou získat otočením jediné stěny).
Běžné algoritmy prohledávání grafů na takto velkých grafech nefungují. Prohledávání do šířky končí velice rychle na přetečení paměti, jedině metody založené na prohledávání do hloubky mohou mít šanci. Pokud je ale naším cílem nalézt nejkratší cestu, zdá se nepřirozené použít prohledávání do hloubky. Nicméně varianta postupného prohlubování, kdy je maximální hloubka prohledávání omezena a vždy po neúspěšném prohledávání ji o jedno zvýšíme, má šanci na úspěch. Vzhledem k tomu, jak se postupně zvětšuje počet pozic dosažitelných v dané hloubce je čas strávený prohledáváním v neúspěšně dokončené hloubce h zanedbatelný proti času stráveném v neúspěšně dokončené hloubce h+1. Pro celkový čas je tedy důležité pouze kolik času algoritmus stráví v poslední neúspěšně dokončené hloubce a kolik v hloubce úspěšně dokončené. Ani pokud by prohledávání do šířky netrpělo problémem s pamětí, nebylo by řádově rychlejší než algoritmus iterativního prohlubování. Algoritmus postupného prohlubování (IDA) by ale neměl žádnou šanci pokud by měl prohledat všechny pozice v takovéto vzdálenosti. Jedním z možných řešení je používat kvalifikovaných dolních odhadů na nutný počet kroků ke složení kostky a ukončit prohledávání, pokud již není šance v dané hloubce kostku dosložit (algoritmy s použitím takových odhadů se značí s hvězdičkou, v našem případě tedy IDA*). Graf rubikovy kostky má spostu krátkých cyklů, proto je dalším velice užitečným trikem použití transpozičních tabulek (snažíme se v maximální míře vyhnout tomu, abychom stejnou pozici prohledávali vícekrát). V roce 1997 Richard Korf použil IDA* s použitím dolního odhadu získaného maximem z počtu tahů nutných ke složení rohů a počtu tahů nutných ke složení 6 hran, s tím, že pro 24 různých rotací kostky dostáváme odhady pomocí jiných šestic. Problém je v tom, jak velkou předpočítanou tabulku si můžeme dovolit. Výsledkem bylo, že pro náhodně zvolené pozice vycházel minimální počet tahů 18 (současné výsledky ukazují, že pozic, na které je potřeba 18 tahů je asi 2.5 krát více než pozic, na které stačí nejvýš 17 tahů, a více než 30 krát více než pozic, na které potřebujeme aspoň 19 tahů).
Takovýto algoritmus by ale v roce 1980 byl nepoužitelný. Přesto byl vymyšlen algoritmus, který byl realizovatelný na HW té doby.
Algoritmus si nekladl za cíl nalézt nejkratší cestu, ale výrazně se k ní přiblížil. Nejsem si jist, zda motivace byla počítačová či algebraická, každopádně v roce 1980 Morwen Thistlethwaite publikoval svůj algoritmus skládání rubikovy kostky založený na zcela jiném principu rozdělení algoritmu do fází.
Fáze si můžeme představovat jako různé hlavolamy.
V první fázi skládá klasickou rubikovu kostku.
V druhé fázi kostku, kde v jedné rovině (například horní a dolní) smí otáčet jedině o 180 stupňů.
Ve třetí fázi kostku, kde ve dvou rovinách včetně té předchozí smí otáčet jedině o 180 stupňů (až na hrany prostřední vrstvy totožný
s hlavolamem rubikovo domino).
Ve čtvrté fázi kostku, kde je možno otáčet všemi stěnami jedině o 180 stupňů.
V poslední fázi není možno stěnami otáčet vůbec.
Algoritmus si klade pro každou fázi pouze takový cíl, aby v dalších fázích bylo možno kostku složit. Čtvrtá fáze tedy nutně musí končit složenou kostkou. První lidmi navržené postupy tohoto čtyřfázového algoritmu dávaly horní odhad 85, postupným zlepšováním pravděpodobně pomocí počítače nakonec vyšel horní odhad 45, kde maximální počty tahů pro jednotlivé fáze jsou 7, 10, 13, 15 tahů. Hlavní výhodou algoritmu je naprosto přirozené rozdělení do fází takové, že v dalších fázích algoritmu se nemusíme bát o to, abychom nepřišli o mezivýsledky z předchozích fází.
První fáze je jediná fáze, kdy je možno orientovat hrany, proto jediný cíl, který si klade je zajištění jejich správné orientace. Pokud si ničeho jiného nevšímáme, máme tedy 2^12/2=2048 pozic, které je potřeba vyřešit. Tato úloha je jednoduchá a s dobrým řešením příjde člověk bez nutnosti zapojit počítač.
Druhá fáze je poslední fáze, kdy je možno orientovat rohy a zároveň poslední fáze, kdy hrany mohou cestovat mezi prostřední vrstvou a zbytkem krychle. Cílem této fáze tedy musí být zorientování rohů a umístění správných hran do prostřední vrstvy. Orientace hran si již nevšímáme, protože v hlavolamu této fáze jej již nedokážeme poškodit. Máme tedy (3^8/3)*(12!/(8!*4!)=1082565 možností které je potřeba vyřešit. Pro člověka prý není problém naučit se postup, jak tento hlavolam řešit na nejvýš 17 kroků. S použitím tabulky jejiž tištěná verze zabírá cca 4 A4 je možno postup redukovat na 13 kroků. Počítačově bylo ověřeno, že při optimálním postupu 10 tahů stačí (byly vygenerovány všechny nejvýše 10 tahové postupy a bylo zjištěno, že se mezi nimi vyskytují všechny pozice).
Ve čtvrté fázi již nedokáží hrany opustit své středové pásy, rohy nedokáží opustit své čtyřstěny, navíc parita permutací jak hran, tak rohů se ve čtvrté fázi nemůže změnit (parita celkové permutace byla neměnná, ale nyní toto platí odděleně pro rohy a pro hrany). Cílem třetí fáze je tedy umístit rohy do svých čtyřstěnů, s tím, že parity permutací v obou čtyřstěnech jsou stejné, kromě toho je potřeba umístit hrany do svých středových pásů (čtyry tam již byly na začátku fáze). Vyšlo mi, že máme (8!/(4!*4!)*2)^2 pozic k vyřešení ve třetí fázi, ale v článku z kterého čerpám tvrdí, že pozic k vyřešení je třikrát víc, že i celkový "twist" čtyřstěnů je neměnný. Třetí fázi Thistlethwite řešil tak, že nejprve dostal rohy do svých čtyřstěnů, pak je permutoval tak, aby dostal jednu z 96 permutací, přičemž složil zároveň hrany do svých pásů. Celkově to zvládl na 15 tahů, což později vylepšil na 13.
Ve čtvrté fázi máme pět čtveřic kostiček které mohou být téměř libovolně permutovány. Omezení je na sudost permutací hran a sudost permutací rohů. Vychází mi, že máme (4!)^5/(2*2) pozic k vyřešení, ale dle výše uvedené korekce je to (4!)^5/(2*2*3). Thistlethwaite tabuloval jak řešit permutace hran na nejvýš 10 tahů, pokud jsou rohy na svých místech. Rohy na místo je možno dostat na nejvýš 4 tahy.
Algoritmus není určen pro lidské rychloskládání. Sám autor používá v popisu věty jako s trochou praxe jsem schopen v tabulce nalézt požadovaný tah pro čtvrtou fázi do dvou minut. Nicméně pokud uvidíte robota skládat kostku, velice pravděpodobně bude používat algoritmy založené právě na Thistlethwaite metodě rozdělení úlohy na řešení hlavolamů s postupně omezovanými druhy pohybů. Protože robot po zorientování se na kostce nemá problémy s pamětí a nepotřebuje se znovu orientovat, naopak mechanické otáčení je oproti výpočtu či vyhledávání v tabulkách výrazně pomalejší, takže má stroj dost času postup naplánovat a ušetření každého tahu se vyplatí.
Dále již jen hesly
1992 Herbert Koicemba redukce pouze na G0 a G2 a G4 mezistupně
(2 fázový algoritmus, kde ve druhé fázi je podle dvou os možno otáčet jen o násobky 180 stupňů)
Již je dost prostředků na to aby počítač dokázal upočítat dva Thistlethwaitovy stupně najednou.
Na G2\G0 stačí 12 tahů a na G2\G4 stačí 18 tahů.
1995 2 fázový algoritmus, první fáze nejvýš 12 tahů, druhá nejvýš 18, ale vždy je možno zvolit takový přechod z fáze 1 do fáze 2, aby fáze 2 trvala nejvýš 17. (dokazuje 29).
Dvoufázový algoritmus kde na každou fázi je volena IDA* s vhodným dolním odhadem, kde první fáze musí končit tahem zakázaným v druhé fázi a je používána
společná maximální hloubka pro obě fáze algoritmu, efektivně řeší každou pozici, na níž byl spouštěn (všechny pokusy na nejvýš 20 tahů).
V lednu 1995 Michael Reid publikoval výsledek 210 hodinového výpočtu, že superflip (otočeny všechny hrany, jinak složená kostka), 20 tahů vyžaduje.
Otázkou bylo, zda existuje pozice, která vyžaduje aspoň 21 tahů.
2007 Gene Cooperman a Dan Kunkle tvrdí, že mají důkaz 26 tahů, ale důkaz nebyl úplný.
2007 Silviu Radu dokázal, že 27 tahů stačí.
2008(5) Tomas Rokicki dokázal, že 23 tahů stačí ... analýza 200000 cosets z 2. fáze dvoufázového algoritmu.
2008(8) Tomas Rokicki snížil odhad na 22 tahů studiem 1280000 cosets s využitím 50 let CPU času.
2010(7) Morley Davidson, John Dethridge s Tomasem Rokickim a Herbert Koicemba dokázali že 20 tahů stačí.
Při důkazu rozdělili množinu všech pozic tak, že brali v jedné skupině všechny počáteční pozice lišící se právě o to, co dokáže vyřešit druhá fáze dvoufázového algoritmu.
Tím zajistili, že celá množina pozic se vešla do paměti najednou a podařilo se jim efektivně pro každou z těchto pozic najednou zkontrolovat, že 20 tahů stačí.
Nezjišťovali přitom, pro které pozice stačí tahů méně. Jejich program dokázal jednu takovou skupinu zpracovat za zhruba 20 sekund.
Z cca 2 miliard těchto skupin jich použitím symetrií stačilo ověřit pouze cca 56 milionů a na to jim google věnoval dostatek výpočetního času.
Kromě těchto čtyř úvodních tahů vedoucích k optimálnímu řešení, všechny ostatní tahy vedou do pozice vyžadující právě 18 tahů.
Odkazy:
Koicemba
Morwen Thistlethwaite
Řešič
Boží algoritmus
Koicembův Cube Explorer
Přehled metod rychloskládání