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ą.
11.08.2010 | aktual.: 07.01.2016 13:00
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ń.
[via cube20.org]
Tomasz Andruszkiewicz
