Rešenje Rubikove kocke u najviše 20 poteza
Već godinama zadaje glavobolje, stvara zavist i uzrokuje neprospavane noći, često nervozu i odustajanje. Na šta god ovaj opis ličio, mi pričamo o Rubikovoj kocki. E pa, zavisnici od ove zarazne igračkice, mogu da odahnu pošto je ona, (na sreću ili žalost), pomalo izgubila svoju draž. Naučnici (opet oni) su pronašli način da ovaj problem reše u svega 20 poteza.
Ipak, nije to uradila ljudska pamet, ili bar ne direktno. Zahvaljući Google-ovim superkompjuterima, tim istraživača je proverio svaku od 43.252.003.274.489.856.000 različitih pozicija (prvi ko nam napiše ovaj broj rečima, dobiće septembarski broj PC Press-a na kućnu adresu) kako bi utvrdili neophodni maksimalan broj poteza da bi se mozgalica razrešila. Utvrdili su da je 20 taj broj, ali do sada je bilo nemoguće to i izvesti. Postoji čak 300 miliona načina da se iz 20 poteza dobije rešenje.
Profesor Morley Davidson, matematičar sa Univerziteta u Ohaju, radio je zajedno sa Google-ovim inženjerom i kolegama iz Nemačke i Kalifornije. On kaže da bi bilo nemoguće ispitati sve kombinacije pojedinačno, pa su ih umesto toga podelili 2,21 milijardi grupa, od po 20 milijardi pozicija. Kasnije su koristili principe simetrije, kako bi smanjili ovaj broj mogućih kombinacija.
U nastavku je neophodan broj poteza za rešenje Rubikove kocke, a u zavisnosti od položaja u kojem se nalazi u trenutku pre rešavanja:
0
1
1
18
2
243
3
3.240
4
43.239
5
574.908
6
7.618.438
7
100.803.036
8
1.332.343.288
9
17.596.479.795
10
232.248.063.316
11
3.063.288.809.012
12
40.374.425.656.24
13
531.653.418.284.628
14
6.989.320.578.825.358
15
91.365.146.187.124.313
16
oko 1.100.000.000.000.000.000
17
oko 12.000.000.000.000.000.000
18
oko 29.000.000.000.000.000.000
19
oko 1.500.000.000.000.000.000
20
oko 300.000.000
Da bi došao do maksimalnog neophodnog broja poteza za rešavanje problema, standardnom PC-ju potrebno je oko 35 godina, dok je Google-ov superkompjuter to uradio za nekoliko nedelja. Do čarobnih 20 se došlo zato što se ovaj broj odnosi na najefikasniji algoritam za rešavanje mozgalice, koji uvek koristi najbrži put.
Inače, od samih početaka Rubikove kocke, naučnici su pokušavali da pronađu taj skriveni broj. Trenutni (živi) šampion u rešavanju Rubikove kocke je Škot Breandan Vallance, čije je prosečno vreme rešavanja 10,74 sekunde.
Izvor: Daily Mail