Božské čéslo

Božské číslo Rubikovy kostky

Rubikova kostka

Každá pozice Rubikovy Kostky lze vyřešit za dvacet tahů nebo méně. Dvacet je tedy takzvané božské číslo Rubikovy kostky, které hledali matematici již tři desítky let.

Co to je Božské číslo?

Božským číslem (algoritmem) je nazýváno takové řešení, které by zvolil bůh – tedy jako bytost všemocná a dokonalá by zvolil postup dokonalý – tedy absolutně nejkratší. Odtud tedy termín pro hledané řešení – Božské číslo.

Google věnoval v roce 2010 výzkumnému týmu 35 let počítačového času (CPU) a tak bylo možno v podstatě vyzkoušet všechny pozice a z nich hledat nejkratší možné řešení. Tím se definitivně prokázalo, že z těch nejvzdálenějších (nejvíce zamíchaných) pozic, kterých je přibližně 3 x 108, je řešení vzdálené přesně dvacet tahů.  Za jeden tah je považována jakákoli rotace kterékoli roviny o libovolný počet stran.

Každý řešitel kostky využívá některé naučené algorytmy (tedy sledy kroků), které vedou k postupnému řešení kostky. Těchto algoritmů existuje celá řada a je jen na luštitely, jaké a v jakém sledu tyto algoritmy pro řešení zvolí.

Mnoho různých algoritmů se liší ve složitosti a tedy počtu požadovaných tahů. Ty, které si může do hlavy uložit a reálně používat obyčejný člověk, obvykle vyžadují více než čtyřicet tahů.

Vývoj hledání Božského čísla

Patnáct let od uvedení kostky na trh bylo prokázáno, že kostka lze z některých pozic vyřešit za 20 tahů, což byla tedy spodní hranice nejvzdálenějších pozic. V té době byly známy důkazy, které určovaly horní mez nejvzdálenějších pozic na 29 kroků.

V roce 2010 (tedy za dalších patnáct let) bylo prokázáno, že kostka lze vyřešit za maximálně dvacet tahů z každé pozice. Tedy že neexistuje vzdálenější pozice, než 20 tahů. 

V podstatě se tedy hledaly nejvzdálenější pozice kostky a k nim pak nejkratší řešení. Vzhledem k množství existujících pozic bylo nemožné vyzkoušet každou pozici a k ní hledat všechna řešení a z nich vybírat to nejkratší. Postupovalo se tedy jen teoretickými výpočty.

V roce 1980 bylo jako nejnižší hranice pro božské číslo stanoveno číslo 18, a to tak, že se analyzovaly řešení pro  sekvence pro 17 nebo méně tahů, a prokázalo se, že těchto pozic je méně, než celkový počet všech pozic kostky. První horní mez byla odhadnuta na  80.

Tabulka vývoje důkazů

Následující tabulka ukazuje posun v důkazech na horní hranici božského čísla.

Datum

Dolní mez

Horní mez

Rozdíl

Poznámky a odkazy

Červenec, 1981

18

52

34

Morwen Thistlethwaite dokazuje, že 52 tahů s jistotou stačí k vyřešení každé pozice. Důkaz ZDE.

Prosinec, 1990

18

42

24

Hans Kloosterman zpřesňuje počet tahů na 42. Důkaz ZDE.

Květen, 1992

18

39

21

Michael Reid prokazuje, že stačí 39 tahů. Důkaz ZDE.

Květen, 1992

18

37

19

Dik Zimní snižuje důkaz na 37 tahů jen o jeden den později. Důkaz ZDE.

Leden, 1995

18

29

11

Michael Reid snižuje horní mez na 29 tahů na základě Kocimbova dvoufázového algoritmu. Důkaz ZDE.

Leden, 1995

20

29

9

Michael Reid dokazuje, že“ Superflip“ pozice (rohy správně, hrany uzavřené, ale zrcadlově) vyžaduje právě 20 tahů. Důkaz ZDE.

Prosinec, 2005

20

28

8

Silviu Radu prokazuje, že 28 tahů je vždy dostačující a posouvá tak horní hranici. Důkaz ZDE.

Duben, 2006

20

27

7

Silviu Radu zlepšuje své výpočty na 27 tahů . Důkaz ZDE.

Květen, 2007

20

26

6

Dan Kunkle a Gene Cooperman prokázli 26 tahů. Důkaz ZDE.

Březen, 2008

20

25

5

Tomas Rokicki snižuje horní mez na 25 tahů. Důkaz ZDE.

Duben, 2008

20

23

3

Tomas Rokicki a John Welborn snížil již jen na 23 tahů. Důkaz ZDE.

Srpen, 2008

20

22

2

Tomas Rokicki a John Welborn po 4 měsících předvádí důkaz pro 22 tahů. Důkaz ZDE.

Červenec, 2010

20

20

0

Tomáš Rokicki, Herbert Kociemba, Morley Davidson, a John Dethridge dokázali, že Boží číslo pro Cube je přesně 20.

 

Sdílejte
  • 1
    Share

Napsat komentář

Vaše emailová adresa nebude zveřejněna.