Každý, kdo řešil kostku ji obvykle umí na více jak 40 tahů a někteří z nás nad ní stráví i třebas celou minutu. Velmi dobře zpracované jsou stránky českých autorů, jež vždy používají odlišné (ne nutně nejméně tahové) metody.
Kdybyste byli „bůh“, tak byste vždy znali optimální řešení a netrávili čas zbytečným otáčením „naprázdno“. Ale lidé jsou omylní a tady je shrnutá poslední historie od původních 80 tahů před 30 lety.
|
Datum |
Dolní hranice |
Horní hranice |
Rozdíl |
Poznámky |
|
Květen, 2007 |
20 |
26 |
6 |
Dan Kunkle a Gene Cooperman dokázali, že 26 tahů stačí. |
|
Březen, 2008 |
20 |
25 |
5 |
Tomas Rokicki snížil hranici na o 25 tahů. |
|
Duben, 2008 |
20 |
23 |
3 |
Tomas Rokicki a John Welborn snížili na 23 tahů. |
|
Srpen, 2008 |
20 |
22 |
2 |
Tomas Rokicki a John Welborn pokračovali na 22 moves. |
|
Červenec, 2010 |
20 |
20 |
0 |
Tomas Rokicki, Herbert Kociemba, Morley Davidson, a John Dethridge dokázali, že 20 je dost. |
Jak vyřešit 43,252,003,274,489,856,000 pozic Kostky?
• Rozdělit na 2 217 093120 množin po 19,508,428,800 pozicích.
• Na základě symetrií a rotací pak řešit jen 55,882,296 pozic.
• Nehledali optimální řešení pro danou pozici, ale vždycky řešení do maximálně 20 tahů.
Co už víme o optimálních řešeních?
|
Počet tahů |
Počet pozic |
|
0 |
1 |
|
1 |
18 |
|
2 |
243 |
|
3 |
3 240 |
|
4 |
43 239 |
|
5 |
574 908 |
|
6 |
7 618 438 |
|
7 |
100 803 036 |
|
8 |
1 332 343 288 |
|
9 |
17 596 479 795 |
|
10 |
232 248 063 316 |
|
11 |
3 063 288 809 012 |
|
12 |
40 374 425 656 248 |
|
13 |
531 653 418 284 628 |
|
14 |
6 989 320 578 825 358 |
|
15 |
91 365 146 187 124 313 |
|
16 |
Okolo 1 100 000 000 000 000 000 |
|
17 |
Okolo 12 000 000 000 000 000 000 |
|
18 |
Okolo 29 000 000 000 000 000 000 |
|
19 |
Okolo 1 500 000 000 000 000 000 |
|
20 |
Okolo 300 000 000 |
Do patnácti tahů jsme si jisti každým řešením že je optimální a je přesně spočítán počet pozic. Na druhé straně už víme, že existuje více jak 20 milionů „nejtěžších“ 20 tahových pozic. Ale kolik pozic se dá vyřešit na přesně 16,17,18,19 či 20 tahů ještě nevíme a v tabulce je jen dosti přesný odhad.
Další informace získáte na www.cube20.org včetně ukázky té „nejsložitější“ kombinace.
