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ą.
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
