Rubikova kocka se može rešiti u ne više od 20 poteza

Do ovog rezultata nedavno je došla mala grupa istraživača među kojima su bili i jedan univerzitetski matematičar i jedan Google-ov inženjer. Oni su zajednički pronašli da se svaki od 43.252.003.274.489.856.000 mogućih početnih položaja može rešiti za 20 ili manje poteza, a ne 22 koliko je iznosio poslednji rezultat istraživanja dobijen u avgustu 2008.

Ovaj izuzetno mali broj poteza pokazao se tačan zahvaljujući računanju izvedenom na Google-ovim računarima u trenucima kad su bili besposleni, za koje bi dobrom stonom računaru s jakim procesorom (na primer Nehalem sa četiri jezgra na 2,8 GHz) bilo potrebno 35 godina.

Problem je rešen tako što je razložen na 2.217.093.120 manjih problema (skupova) od kojih je svaki sadržao po 19.508.428.800 različitih pozicija. Broj tih skupova je potom redukovan na 55.882.296 korišćenjem simetrija. Svaki od njih bio je dovoljno mali da stane u memoriju modernog personalnog računara, a način na koji je bio razložen omogućavao je da se svaki skup reši brzo.

Ovim istraživanjem okončano je tridesetogodišnje traganje za najefikasnijim načinom da se ispravno poređa 26 obojenih kockica spojenih u veću kocku koju je 1974. izumeo mađarski profesor arhitekture Erne Rubik a 1980. počela da prodaje širom sveta kompanija Ideal Toys.

Tim koji je rešio problem saopštio je de je trebalo da prođe 15 godina od pojave kocke da se nađe prva pozicija koja dokazano zahteva 20 poteza da se reši i da je stoga bilo sasvim primereno da se posle isto toliko godina dokaže da je 20 poteza dovoljno i za svaku drugu poziciju.

Ni tim ni Gugl nisu saopštili koliko je računara korišćeno ni koliko su bili jaki, ali su zato otkrili da je problem rešen za svega nekoliko nedelja.

Njihov rad se oslanjao na rezultate brojnih istraživača, počev od Morvina Tistletvajta koji je 1981. pokazao da su 52 poteza dovoljni da se dođe do rešenja bilo koje pozicije. Do 1992. je Majkl Rejd pokazao da je uvek dovoljno 39 poteza, ali je dan kasnije Dik Vinter pokazao da je dovoljno 37. Broj se potom i dalje postepeno smanjivao da bi se najzad u julu ove godine stiglo do konačnog rešenja.

Entuzijazam koji prati Rubikovu kocku ne završava se samo na pronalaženju ovog broja već i takmičenju ko će brže da je složi. Aktuelni svetski rekorder je Holanđanin Erik Akersdijk kome je za to bilo potrebno svega 7,08 sekundi. U stopu ga prate, a na momente i prestižu u brzini, roboti sklopljeni od Lego kocki.

Detaljnije objašnjenje i dodatne informacije o tome kako se došlo do ovog broja nalaze se ovde.

Dodajmo još za kraj da oni koji nikada nisu uspeli da reše Rubikovu kocku mogu da iskoriste neki od brojnih vodiča za njeno rešavanje i okanu se jednog od ranije dobro poznatog i relati