Kostkę Rubika zawsze da się rozwiązać w maksymalnie 20 ruchach

Dzięki wykorzystaniu komputerów Google'a międzynarodowemu zespołowi badaczy udało się rozwikłać zagadkę, której nie potrafiono rozwiązać przez 30 lat. Nie istnieje startowe ułożenie kostki, z którego nie dałoby się ułożyć sześciu jednokolorowych ścian w maksymalnie 20 ruchach.

Istnieje 100 000 możliwych pozycji startowych. Żadna z nich nie wymaga więcej niż 20 ruchów do skończenia układanki. W większości przypadków trzeba natomiast wykonać od 15 do 19 ruchów.

Teoretyczną odpowiedź na zagadkę węgierskiej kostki znaliśmy już w 1995 roku. Wtedy matematyk Michael Reid udowodnił, że wcześniejsze przewidywania (18 ruchów) nie są właściwe, a prawidłowa odpowiedź na zagadkę kostki to 20.

Dopiero teraz dzięki wykorzystaniu olbrzymiej mocy obliczeniowej wielu komputerów można było udowodnić tę teorie. Nigdy wcześniej bowiem nikt nie przebił się przez wszystkie możliwe kombinacje.

Dla zobrazowania ogromu wyzwania warto wspomnieć, że aby ułatwić i uporządkować badania, uczeni podzielili wszystkie możliwe rozwinięcia 100 000 startowych pozycji na 2,2 miliarda grup, z których każda mieściła 20 miliardów pozycji.

Następnie dzięki redukcji podwójnych i symetrycznych pozycji uczonym udało się uzyskać 56 milionów grup po 20 miliardów pozycji. Z tym komputery Google'a potrafiły już sobie poradzić.

Źródło: Geekologie • BBC