Kostka Rubika rozwiązana!

9 sierpnia tego roku ostatecznie ustalono - dowolnie pomieszaną kostkę Rubika można ułożyć wykonując tylko 20 (lub mniej) ruchów.

Jest to zaskakujące, jeżeli weźmie się pod uwagę liczbę możliwych ustawień oryginalnej kostki Rubika. Składa się ona z 8 narożników (kosteczek narożnych) i 12 krawędzi (kosteczek na krawędziach). Narożniki można ustawić na 8! (40 320) sposobów. Dodatkowo kosteczki te mogą różnić się orientacją (sposobem obrócenia) - to daje nam 3⁷ możliwości (przyjmujemy, że np. jedna z kosteczek jest ustawiona białą powierzchnią do góry, to każdą z pozostałych 7 kosteczek można obrócić na 3 sposoby).

Krawędzie można ustawić na 12!/2 sposobów (239 500 800) - dzielimy przez 2, bo permutacja krawędzi zależy od permutacji narożników - muszą one mieć tą samą parzystość (http://en.wikipedia.org/wiki/Parity_of_a_permutation). A każdą z 12 kosteczek na krawędziach można zorientować na 2 sposoby, co przy przyjęciu jednej z nich za "orientującą" całą kostkę daje nam 2¹¹ (2 048) możliwości.

Razem:

8! * 3⁷ * 12!/2 * 2¹¹ = 43,25 * 10¹⁸

Zadziwiające, że tylko w 20 ruchów można z każdej z tych pozycji dojść do pozycji wyjściowej.

Algorytm, który umożliwia rozwiązanie podobnego do kostki Rubika problemu (wieży Hanoi lub osiągnięcie mata w końcówce szachowej) w jak najmniejszej liczbie ruchów/posunięć nazywa się "boskim algorytmem". W szachach takimi "algorytmami" są bazy danych końcówek szachowych, dla wieży Hanoi też istnieje taki algorytm (http://web.archive.org/web/20040605074124/http://yupana.autonoma.edu.co/publicaciones/yupana/003/hanoi/hanoi_eng.html).

Maksymalna wymagana liczba ruchów w takim "boskim algorytmie" nazywana jest "boską liczbą". Dla kostki Rubika liczba ta była oszacowywana z rosnącą dokładnością, ale dopiero w tym roku dzięki obliczeniom komputerowym udowodniono, iż jest ona równa 20 - jest to wcześniejsze dolne ograniczenie na tą liczbę. Jeszcze 15 lat temu miano nadzieję, że można rozwiązać kostkę Rubika w 18 lub 19 ruchach (przedział wynosił wtedy 18-29), ale w 1995 znaleziono ułożenie kostki Rubika wymagające minimum 20 ruchów.

Obliczenie tego wyniku zajęłoby pojedynczemu procesorowi ok. 35 lat. Jednak dzięki mocy obliczeniowej udostępnionej przez Google stało się to możliwe o wiele szybciej. Cóż, problem został rozwiązany metodą "brute-force":

1. Podzielono wszystkie możliwe ułożenia na ponad 2 miliardy zbiorów - każdy zawierał trochę ponad 19,5 miliarda pozycji. Podział ten odbył się specjalnie na tyle sprytnie, że...

2. Liczba zbiorów do rozwiązania została zredukowana do "tylko" niecałych 56 milionów - pozbyto się pozycji powstałych przez obroty, symetrie, odbicia lustrzane itd.

3. Nie szukano optymalnego rozwiązania dla każdej pozycji, a tylko rozwiązania z 20 lub mniej ruchami. Jest to ważne, bo pozwoliło przyspieszyć poszukiwania ok. 11 tys. razy, do blisko 4 tysięcy losowych pozycji na sekundę.

4. Napisano program, który rozwiązywał każdy zbiór w 20 sekund. Cały zbiór, czyli 19.5 miliarda pozycji. Wynik ten uzyskano sprytnie układając pozycje w zbiorach - tak, aby nie trzeba było powtarzać obliczeń od początku dla każdej kolejnej pozycji.

5. Uruchomiono powyższy program na kilka tygodni na komputerach należących do Google (ich inżynier był zaangażowany w projekt).

6. Pokazano, że nie ma pozycji, która by wymagała więcej niż 20 ruchów.

Więcej:
http://www.cube20.org/
http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube
http://en.wikipedia.org/wiki/God%27s_algorithm