Każdy układ kostki Rubika można rozwiązać w 20 ruchach

Kostka Rubika przestała mieć tajemnice - wiadomo, że każdy układ da się rozwiązać w nie więcej niż 20 ruchach. Szkoda tylko, że uzasadnienie nie jest matematycznym majstersztykiem, tylko policzeniem wszystkich kombinacji metodą siłową.

marcindmjqtx
SKOMENTUJ

Od 1980 roku wielu ludzi zastanawiało się, ile ruchów wystarczy do rozwiązania tej łamigłówki. Już od początku wskazano układy, które wymagały co najmniej 18 ruchów. Gorzej było z górnym oszacowaniem - w 1981 roku nadal było to 52 posunięcia, w połowie lat 90 poniżej 30, a potem powolne urywanie kolejnych. W 1995 roku było już wiadomo, że istnieją układy wymagające 20 ruchów, choć jest ich bardzo mało (rzędu 3*108, czyli znacznie mniej niż układów 18-ruchowych, których jest około 2,9*1019). A teraz wiemy już, że 20 ruchów wystarczy do rozwiązania każdej kombinacji.

Autorzy rozwiązania wybrali prostą metodę - podzielili problem na mniejsze klasy układów identycznych ze względu na liczbę ruchów rozwiązania i... kazali po prostu policzyć je po kolei komputerom. Pomogło Google, które udostępniło swoje maszyny - w kilka tygodni wykonały one pracę, które nowoczesnemu desktopowi z czterordzeniowym procesorem Intel Nehalem 2,8 GHz zajęłoby 35 lat obliczeń.

Tomasz Andruszkiewicz

Wybrane dla Ciebie

Rebel Wolves potwierdza. Dawnwalker to ich debiutancka gra
Rebel Wolves potwierdza. Dawnwalker to ich debiutancka gra
Assassin's Creed Red to potężna inwestycja Ubisoftu. Jest przeciek
Assassin's Creed Red to potężna inwestycja Ubisoftu. Jest przeciek
DualSense V2 wycieka. Czyżby mocniejsza bateria?
DualSense V2 wycieka. Czyżby mocniejsza bateria?
Horizon Forbidden West na PC coraz bliżej. Nvidia wkracza do akcji
Horizon Forbidden West na PC coraz bliżej. Nvidia wkracza do akcji
Imponująca sprzedaż Cyberpunk 2077: Phantom Liberty. Liczby mówią wszystko
Imponująca sprzedaż Cyberpunk 2077: Phantom Liberty. Liczby mówią wszystko
Xbox Game Pass z mocnymi grami w styczniu. Potężne otwarcie roku
Xbox Game Pass z mocnymi grami w styczniu. Potężne otwarcie roku
Star Wars Outlaws: wycieka termin premiery. Ubisoft dementuje
Star Wars Outlaws: wycieka termin premiery. Ubisoft dementuje
PS5 rozbija bank. Imponujące wyniki sprzedaży
PS5 rozbija bank. Imponujące wyniki sprzedaży
The Day Before za niespełna tysiąc złotych. Nie, to nie żart
The Day Before za niespełna tysiąc złotych. Nie, to nie żart
Hakerzy ujawnili plany Insomniac Games. Sześć gier na liście
Hakerzy ujawnili plany Insomniac Games. Sześć gier na liście
PS5 Pro z własnym DLSS. Nieoficjalne doniesienia o planach Sony
PS5 Pro z własnym DLSS. Nieoficjalne doniesienia o planach Sony
Nie będzie The Last of Us Multiplayer. To już pewne
Nie będzie The Last of Us Multiplayer. To już pewne