Souboj algoritmů a čísel: Bůh vs. Ďábel
Ne, nebude řeč o filozoficko-psychologických kreaturách. Vzhledem k mým chabým znalostem v oblasti teorie grup si na své nepřijdou ani vyznavači matematiky. Tento článek má za cíl objasnit následující pojmy: Božský a Ďábelský algoritmus; Božské a Ďábelské číslo.
Jako Božský algoritmus se u kombinatorických hlavolamů označuje taková sekvence tahů, která je stejně dlouhá, jako v případě, že by rozmíchaný hlavolam skládal Bůh. Předpokládejme, že Bůh je všemohoucí a vševědoucí. Tudíž vždy zná, např. pro Rubikovu kostku 3x3x3, nejmenší počet tahů, který je třeba na rozmíchanou kostku aplikovat, aby byla složená. Tento počet tahů v Božském algoritmu se nazývá Božské číslo (a pro Rubikovu kostku je rovno 20 – jinými slovy je kostka 3x3x3 vždy složitelná do 20 tahů, bez ohledu na počáteční rozmíchání. Pakliže je použita metrika čtvrtinového otáčení (tj. např. B2 je počítáno jako dva tahy), Božské číslo pro Rubikovu kostku 3x3x3 je 26).
Zatímco u některých hlavolamů je Božské číslo známé, pro další zůstává jeho nalezení stále tajemstvím. Obvykle se nejedná o jednoduchou matematickou úlohu. K prohledání všech možných stavů hlavolamu a zjištění jejich vyřešení nejmenším počten tahů jsou zapotřebí superpočítače a sofistikované analytické i numerické metody.
V kontrastu s Božským algoritmem existuje i Ďábelský algoritmus, který ale naneštěstí není dobře definován. Nejedná se však o sekvenci tahů, která by skládala rozmíchaný hlavolam "co nejdelším způsobem" (v analogii s Božským algoritmem, který řeší rozmíchanou pozici optimálně z hlediska počtu tahů). Někteří autoři udávají za Ďábelský algoritmus takovou sekvenci, která navštíví všechny stavy hlavolamu. Jako optimální Ďábelský algoritmus bývá někdy označována taková sekvence tahů, která navštíví všechny možné stavy hlavolamu, a to právě jednou.
Je tak možné říci, že kdyby Ďábelský algoritmus prováděl na hlavolamu slepý člověk, v jednu chvíli by se nacházel hlavolam složený. Podobně jako v případě Božského algoritmu, i nalezení Ďábelského algoritmu nebývá triviální záležitost.
Pro kombinatorické hlavolamy bývá občas zmiňován i pojem Ďábelské číslo. Stejně tak jako v případě Božského čísla, Ďábelské číslo označuje nejmenší počet tahů v Ďábelském algoritmu. Na rozdíl od "věřícího světa" tak nutně nemusí jít o číslo 666, 616 nebo jiné číslo hojně udávané v souvislosti s Ďábelským číslem (číslem šelmy, satanovým číslem atd.).
Doporučená literatura pro zájemce (odkazy platné k 20. 2. 2013):
http://anttila.ca/michael/devilsalgorithm
http://www.jaapsch.net/puzzles/hamilton.htm
http://www.cube20.org
http://en.wikipedia.org/wiki/God%27s_algorithm
http://www.jaapsch.net/puzzles/groups.htm
klíčová slova pro google: God's algorithm; Devil's algorithm; God's number; Devil's number