HTA (Human Thistlethwaite Algorithm)


Od TA k HTA

V roce 1980 vyvinul Morwen Bernard Thistlethwaite unikátní algoritmus (ve smyslu počítačového algoritmu) na skládání Rubikovy kostky 3x3x3. Thistlethwaitův algoritmus (TA) řeší hlavolam ve 4 krocích, přičemž jeho unikátnost spočívá v tom, že na rozdíl od tehdy známých metod není cílem každého kroku složení několika dílků, nýbrž redukce možných tahů (viz značení tahů Rubikovy kostky).

V prvním kroku jsou povoleny všechny možné tahy (kterých je celkem 18) vnějšími vrstvami. Ve druhém kroku již nejsou povoleny tahy F/F' a B/B', pouze F2/F2' a B2/B2'. Třetí krok zakazuje tahy R/R' a L/L'. Ve čtvrtém kroku je možné skládat pouze pomocí dvojitých tahů (kterých je celkem 6) jako je U2, B2 atd.

Zvolíme-li si množinu všech dovolených tahů T, pak pro první krok T1 můžeme psát T1 = {U,D,R,L,F,B} (protože U U = U2 = U2' a U2 U = U'). Pro další kroky poté dostáváme T2 = {U,D,R,L,F2,B2}, T3 = {U,D,R2,L2,F2,B2} a konečně T4 = {U2,D2,R2,L2,F2,B2}. Je vidět, že prvky/tahy v množině Tn+1 tvoří podmnožinu Tn pro n = 1,2,3. Tahy vnitřních vrstev jsou kombinacemi tahů vnějších vrstev s následnou rotací kostky, proto se jimi nebudeme dále zabývat. Schematicky si jednotlivé kroky TA můžeme znázornit následovně:

Slovní popis cíle každého kroku zní:

  • orientace hran
  • orientace rohů, vložení hran do E prstence
  • dostání rohů do tetrád, sudá permutace rohů, vložení hran do M a S prstenců
  • složení kostky

Zatímco před prvním krokem TA existuje více než 43·1018 kombinací/pozic hlavolamu, před čtvrtým krokem je to již méně než 1·106. Konkrétně existuje pro 1. krok 2 048 pozic, aby byla kostka dále složitelná v následujícím kroku. Pro druhý, třetí a čtvrtý krok existuje 1 082 565, 29 400 a 663 552 takových pozic/algoritmů (ve smyslu kostkařského algoritmu). Přestože takové počty algoritmů jsou nepraktické pro lidi, TA je velmi vhodný pro počítače.

Sám M. B. Thistlethwaite dokázal, že pro první krok je zapotřebí nejvýše 7 tahů, pro další kroky pak 13, 15 a 17 tahů. TA tedy řeší kostku 3x3x3 nejvýše pomocí 52 tahů. Později bylo nalezeno optimální řešení pro každý krok: 7, 10, 13, 15 - tudíž celkově 45 tahů. Průměrný počet tahů optimálního TA činí 31,3.

Co mj. dělá TA zajímavým, je fakt, že na každý krok můžeme nahlížet jako na specifický hlavolam, protože v dalších krocích již nemůžeme rozmíchat to, čeho jsme v dřívějších krocích dosáhli. V ostatních metodách obvykle musíme něco již složeného dočasně rozmíchat, abychom mohli poskládat další dílky.

V roce 2002 přemýšlel Ryan Heise nad tím, jak by mohli lidé skládat kostku metodou TA. V roce 2003 popsal HTA (Human Thistlethwaite Algorithm), což je verze TA vhodná pro lidi.

Protože se často budeme odkazovat na stěnu nebo vrstvu, rozdíl mezi těmito dvěma pojmy je znázorněn na následujících dvou simulátorech:

horní stěna horní vrstva

HTA: krok 1, množina tahů {U,D,R,L,F,B}

Tomuto kroku se také někdy říká orientování hran a pro začátečníky je patrně nejtěžší. Může být výhodné smýšlet ve dvou opozitních barvách, jako by to byla barva jen jedna. Opozitní barvy na simulátorech níže jsou červená a oranžová, modrá a zelená, žlutá a bílá.

Abychom mohli hrany správně orientovat, musíme vědět, kdy má hrana špatnou orientaci a kdy naopak dobrou orientaci. Při uvažování fixní polohy kostky (tzn. nedělejte tahy x, y ani z) a pouze množiny tahů {U,D,R,L,F2,B2} je dobře orientovaná hrana ta, kterou lze umístit na svoji pozici, aniž by byla špatně orientovaná (což samozřejmě nemusíte fyzicky provádět, stačí si potřebné tahy v duchu představit). Jinými slovy řečeno dobře orientovaná hrana je ta, jejíž umístění na svoji pozici se správnou orientací vyžaduje sudý počet součtu tahů F/F' a B/B' (pokud je součet lichý, jedná se o špatně orientovanou hranu). Špatně orientovaných hran je na kostce vždy sudý počet.

Tento krok je jediným, ve kterém můžeme změnit orientaci hrany z dobré na špatnou a naopak. Pojďme si ukázat, co z hlediska orientace hran dělá tah F (příp. F' a B/B'), který je v dalším kroku HTA zakázán. Šedé dílky na simulátoru nejsou nyní podstatné.

Vidíme, že tah F mění orientaci 4 hran v otáčející se vrstvě, protože po tomto tahu není možné umístit ani jednu hranu na správnou pozici se správnou orientací jen s užitím množiny tahů {U,D,R,L,F2,B2}. Pokud ale z počáteční pozice simulátoru provedete místo tahu F tah F2, orientace hran zůstává zachována (zkuste si hrany zpátky složit jen pomocí množiny tahů {U,D,R,L,F2,B2} a zafixované orientace celé kostky; jedno takové řešení je U L2 D R2 B2 U L2 R2). Tah F' opět mění orientaci všech 4 hran. Tahy B/B2/B' si můžete nasimulovat tak, že nejprve provedete rotaci y2 a poté aplikujete daný tah - B a B' mění orientaci 4 hran v otáčené vrstvě, B2 = B2' nikoliv.

Na dalším simulátoru vidíme (bez potřeby dělat s kostkou jakoukoliv rotaci), že hrana na pozici UF je špatně orientovaná (protože si můžeme červený střed představit jako oranžový, a žlutý střed jako bílý - pak je hrana umístěna na své pozici, ale se špatnou orientací), hrana na pozici UB je správně orientovaná (protože barva hrany v horní stěně je stejná jako barva středu v horní stěně (při uvažování, že červený střed je oranžový střed)).

Existuje několik pouček o tom, kdy je hrana špatně orientovaná. Já znám jen jednu (kterou není nutné si pamatovat, ale rychleji tím zjistíte, jestli je hrana dobře nebo špatně orientovaná): pokud má hrana nacházející se v horní nebo v dolní vrstvě nálepku shodnou s barvou horního či dolního středu, a tato nálepka směřuje nahoru či dolů (tedy ne směrem ke mně, ode mě, doprava nebo doleva), pak se jedná o hranu se správnou orientací.

Protože zpočátku budou většinou špatně orientované minimálně 4 hrany, je dobré si 4 špatně orientované hrany ihned umístit do přední či zadní vrstvy a následně je správně orientovat. Výhodou takového postupu je to, že nemusíme najednou určovat a pamatovat si orientaci všech 12 hran, ale jen zbylých 8. Následuje příklad, na kterém si ukážeme orientování hran.

Z poučky uvedené výše je patrné, že hrana na pozici UR je špatně orientována (pokud si nechcete poučku pamatovat, stačí si pro tuto hranu v duchu představit tah U a červený střed jako oranžový střed - pak je hrana na své pozici, ale špatně orientovaná), tahem [1] ji vkládáme do přední vrstvy.

Hrana na pozici UR je špatně orientovaná, proto ji tahem [2] vkládáme do přední vrstvy. Tím však byla z oné vrstvy vystrčena špatně orientovaná hrana, jenž je nyní na pozici UL.

Špatně orientovanou hranu na pozici UL vkládáme tahem [3] do přední vrstvy.

Bez jakékoliv rotace s kostkou plyne z poučky, že hrana na pozici DR je také špatně orientovaná. Tahem [4] ji vkládáme do přední vrstvy.

Hrana na pozici DR je špatně orientovaná, proto ji tahem [5] vkládáme do přední vrstvy. Poté tahem [6] správně orientujeme hrany v přední vrstvě.

V tuto chvíli je dobré zjistit orientaci všech zbývajících hran (tj. v zadní vrstvě a v prostřední vrstvě). Další špatně orientované hrany se nacházejí na pozicích UR, UL, DR (pro prostřední vrstvu), BR, BD, BL (pro zadní vrstvu).

Tahem [7] umísťujeme špatně orientovanou hranu na pozici BU, zároveň ale i další špatně orientovanou hranu na pozici FU.

Tahem [8] správně orientujeme hrany v zadní vrstvě. Nyní se na kostce nachází jen 2 špatně orientované hrany na pozicích FU a DR.

V případě jen 2 špatně orientovaných hran umístíme jednu z nich do přední či zadní vrstvy (splněno zásluhou hrany na pozici FU). Poté v oné vrstvě změníme orientaci hran v ní umístěných, viz tah [9] - znamená to, že ze 3 dobře orientovaných a 1 špatně orientované hrany se stanou 3 špatně orientované a 1 dobře orientovaná hrana.

Tahem [10] vkládáme do přední vrstvy poslední špatně orientovanou hranu z pozice DR, načež tahem [11] dochází ke správné orientaci všech hran.

HTA: krok 2, množina tahů {U,D,R,L,F2,B2}

Tento krok je rovněž znám pod názvem redukce na domino díky podobnosti s Rubikovým dominem. Zatímco v TA se krok řeší jednofázově, v HTA ho budeme řešit dvoufázově: nejprve vložíme hrany patřící do horní a dolní vrstvy do těchto vrstev, poté budeme v těchto vrstvách orientovat rohy. Horní a dolní stěna tak bude tvořena jen 2 opozitními barvami.

Hrany

Stejně jako v předešlém kroku, i nyní nemusíme rozlišovat mezi opozitními barvami. Intuitivně vložíme hrany nejdříve do horní, poté do dolní vrstvy. Rotace x2, y2 a z2 nepřináší z pohledu dovolených tahů žádnou změnu.

Do horní vrstvy se budou vkládat hrany na pozicích RF a LF, to se děje v tazích [1-3].

Tah [4] otáčí s kostkou, abychom mohli začít vkládat hrany do nynější horní vrstvy.

Tahy [5-7] vložíme hranu z pozice LF do horní vrstvy bez toho, aby došlo ke změně hran v dolní vrstvě.

Následuje vložení poslední hrany z pozice RF (tahy [8-10]).

Rohy

Podobně jako u hran, ani u rohů nemusíme v této fázi rozlišovat mezi opozitními barvami. Rotace s kostkou zmíněné výše platí i pro rohy.

Pro první dva uvedené příklady: tah [1] orientuje neorientovaný roh z dolní vrstvy. Tah [2] je nastavovací a slouží k přesunu onoho rohu do stejné vrstvy (tj. pravá nebo levá), v jaké je zbylý zpočátku neorientovaný roh. Tahem [3] dochází k výměně 2 zpočátku neorientovaných rohů. Zbylé dva tahy jsou inverzní k tahům [1-2] a slouží k orientaci neorientovaného rohu původně se nacházejícího v horní vrstvě.

Ve třetím příkladu tahem [1] vkládáme libovolný špatně orientovaný roh do dolní vrstvy. Nemůžeme sice docílit počáteční pozice z předchozích dvou případů, ale po tahu [2] můžeme alespoň orientovat roh na pozici DRF - viz tahy [3-7], které najdeme i v prvním příkladu. Po sedmém tahu bychom mohli pokračovat např. tahy L2 D' U', a situace by se převedla na druhý případ.

Jak je z příkladů patrné, snažíme se naráz orientovat dva rohy - jeden z dolní a druhý z horní vrstvy. Pokud nemůžeme orientovat oba dva rohy současně (tzn. když jsou na počátku špatně orientované jen 3 rohy, příp. někdy i 6 rohů), orientujeme alespoň 1 roh, přičemž druhý zůstává pořád špatně orientovaný, avšak můžeme již aplikovat postup z prvních dvou příkladů výše.

HTA: krok 3, množina tahů {U,D,R2,L2,F2,B2}

Oproti TA budeme v HTA řešit krok opět dvoufázově. V první fázi dojde k permutování rohů, ve druhé fázi pak k orientování hran. Orientací hran v tomto kroku se myslí tzv. orientování hran podle 3 os, neboť doposud byly hrany tzv. orientovány podle 2 os (v kroku 1 byly hrany orientovány podle 1 osy, v kroku 2 byly hrany orientovány podle 2 os). Nutným, nikoliv však nezbytně postačujícím, cílem je získání opozitních barev nejenom v horní a dolní stěně, ale i ve přední a zadní, jakož i v pravé a levé stěně. Můžeme se setkat s označením kroku "redukce na dvojité tahy" (v angličtině Half Turn Reduction (HTR), příp. double moves reduction nebo také 180 degree turns reduction).

Permutace rohů

Začneme intuitivní separací rohů - rohy patřící do horní vrstvy vložíme do oné vrstvy (pro tuto fázi budeme rozlišovat mezi opozitními barvami, takže např. červená a oranžová jsou dvě odlišné barvy). To znamená, že rohy patřící do dolní vrstvy se budou vyskytovat pouze v dolní vrstvě. Existuje několik případů, jak mohou být rohy vzájemně permutovány. V jednom z nich je zapotřebí diagonální výměna dvou rohů jak v horní, tak v dolní vrstvě.

Pro všechny ostatní případy permutace rohů můžeme využít maximálně dvojí aplikování následujícího algoritmu (a nastavovacích tahů). Řekněme, že u složených rohů chceme prohodit jen rohy na pozicích URF a URB (simulátor nabízí pohled zdola).

Prvním tahem oba zmíněné rohy vkládáme do dolní vrstvy.

Tahy [2-3] vkládáme daný roh na požadovanou pozici URB, avšak nynější rohy na pozicích URB a DLF nejdou jednoduše spárovat a vložit zpět do horní vrstvy tak, aby v konečném důsledku byly rohy na horních pravých pozicích prohozeny.

Proto tahy [4-6] pozice obou uvedených rohů vyměňují.

Tahem [7] dochází k opětovnému párování daných rohů.

Tahy [8-9] vkládají dané rohy zpět do horní vrstvy.

Můžeme si všimnout, že kromě sousedních rohů na pozicích URF a URB se jako vedlejší efekt vyměnily i protilehlé rohy na pozicích DRF a DLB. Níže jsou pro úplnost uvedeny zbývající případy permutace rohů a jejich řešení (pokud váš případ uveden není, proveďte rotaci x2, případně tahy U/D).


Rohy není nutné ve vztahu ke středům v této fázi skládat. Postačí, pokud všechny 3 barvy na každém rohu korespondují s barvou středu nebo barvou opozitního středu (vyjma případu, kdy je zapotřebí v pouze jedné vrstvě diagonální záměna 2 rohů). Od teď jsou rohy složitelné pomocí množiny tahů {U2,D2,R2,L2,F2,B2}.

Orientace hran

Hrana je takzvaně orientovaná podle 3 os, pokud její obě barvy korespondují s barvou středu nebo barvou opozitního středu. To má za následek, že takové hrany budou složitelné jen pomocí množiny tahů {U2,D2,R2,L2,F2,B2} v dalším kroku.

V horní a dolní vrstvě existuje sudý počet špatně orientovaných hran podle 3 os. Na simulátoru níže se jedná o hrany na pozicích UF, UR, UB, UL, DF a DR.

Tah M2' poslouží k orientaci všech 4 hran, které se v této prostřední vrstvě (mezi levou a pravou vrstvou) nachází.

Tahy [1-2] umísťujeme špatně orientované hrany na pozice DF a DB.

Tahy [3-4] správně orientujeme 4 hrany, které se po tahu [2] nacházely v prostřední vrstvě.

Nyní jsou špatně orientovány hrany na pozicích UR a DF. Podobně jako v prvním kroku HTA můžeme situaci ze 2 špatně orientovaných hran převést na 4 špatně orientované hrany.

To uděláme tak, že obě špatně orientované hrany umístíme buď do dolní nebo do horní vrstvy (tah [5]) a to tak, aby tahem [6] bylo možné otočit horní nebo dolní (v našem případě dolní) vrstvou za účelem vložení dvou dobře orientovaných hran na pozice DF a DB (nebo UF a UB v případě otáčení horní vrstvou), které po M2' budou špatně orientovány.

Tahem [7] dochází ke změně orientací hran v prostřední vrstvě - z 1 špatné a 3 dobrých před tahem [6] na 3 špatné a 1 dobrou.

Tah [8] je inverzní k tahu [6] a orientuje některé hrany v dolní vrstvě. Nyní jsou špatně orientované hrany na pozicích UF, UR, UB a DL.

Tahem [9] přesouváme špatně orientovanou hranu z pozice UR na pozici DR.

Tah [10] slouží k umístění 2 špatně orientovaných hran na pozice DF a DB.

Tahem [11] orientujeme všechny hrany v horní vrstvě, tahem [12] orientujeme všechny hrany v dolní vrstvě.

Od teď jsou hrany (a tím pádem i celá kostka) složitelné pomocí množiny tahů {U2,D2,R2,L2,F2,B2}.

HTA: krok 4, množina tahů {U2,D2,R2,L2,F2,B2}

Poslední krok HTA řešíme opět dvoufázově (oproti TA, kde si vystačíme jen s jednou fází) - nejdříve složíme rohy a poté permutujeme/složíme hrany.

Skládání rohů je intuitivní. Pakliže složíte rohy v jedné vrstvě, dojde k automatickému složení rohů v druhé vrstvě. Pro hrany je dobré znát následující 2 algoritmy.

Jejich uplatnění najdeme v případech, kdy chceme prohodit 4 hrany, viz následující 2 simulátory.

Vidíme, že prvním tahem dosahujeme stavu, kdy jsou 3 nesložené hrany na pozicích UF, UR a UB, zatímco 4. nesložená hrana je na pozici DL. Tahy [2-4] se poté docílí stav, kdy je potřeba vyměnit hrany na pozicích UF s UB, a RF s RB.

Využití nalezneme rovněž v případě, kdy potřebujeme složit 3 hrany v prostřední vrstvě.

Vzniklou pozici již řešit umíme. V rámci posledního komentovaného simulátoru složíme Rubikovu kostku.

Začneme rohy v přední vrstvě, viz tahy [1-3]. Tahem [4] skládáme rohy vůči středům.

Pokud se na 3 sousedících stěnách objeví více než 6 nesložených nálepek (podmínka je mj. splněna pro přední, horní a pravou stěnu), je výhodné provést M2 E2 S2 (viz tahy [5-7]) za účelem složení několika hran. Tuto poučku si není třeba pamatovat - pokračovat se dá i bez ní, ale v daném případě urychluje skládání.

Tah [8] je nastavovací. Nyní lze vyměnit hrany na pozicích UF s UB, a RF s RB (tahy [9-14]). Poté je proveden (tahem [15]) inverzní tah k tahu [8].

Tah [16] je nastavovací. Nyní je možné prohodit hrany na pozicích DF s DB, a RF s RB (případně udělat rotaci s kostkou, aby bylo možné prohodit hrany na pozicích UF s UB, a RF s RB jako v minulém případě). Hrany se prohazují v tazích [17-22].

Tah [23] je nastavovací. V tazích [24-27] poskládáme zbytek hlavolamu.

Podobné metody

V roce 1992 přišel Herbert Kociemba s novým počítačovým algoritmem. Kociembův algoritmus zjednodušeně řečeno kombinuje první dva kroky Thistlethwaitova algoritmu do jednoho kroku (nazývaného fáze 1) a zbylé dva kroky TA do fáze 2. Kociembův dvoufázový algoritmus, založený na Thistlethwaitově algoritmu, je do jisté míry výsledkem rozmachu hardwarového vybavení výpočetní techniky, protože kvůli nedostatečné paměti a málo výkonným procesorům tehdejších počítačů nemohlo dojít ke sloučení 4 kroků na 2 fáze již v roce 1980. Fáze 1 Kociembova algoritmu vyžaduje maximálně 12 tahů, fáze 2 maximálně 18 tahů.

Co se týče lidského skládání, nejvíce podobná metoda (o které vím) s metodou Human Thistlethwaite Algorithm je 3-Color Method (viz též stručný popis metody), kterou Michael Feather vyvinul a používal již v roce 1980. 3-Color Method je tak o více než 20 let mladší než HTA.



Graficky stránku obohatil Michael Feather.