Рубикова коцка се може решити у не више од 20 потеза

До овог резултата недавно је дошла мала група истраживача међу којима су били и један универзитетски математичар и један Google-ов инжењер. Они су заједнички пронашли да се сваки од 43.252.003.274.489.856.000 могућих почетних положаја може решити за 20 или мање потеза, а не 22 колико је износио последњи резултат истраживања добијен у августу 2008.

Овај изузетно мали број потеза показао се тачан захваљујући рачунању изведеном на Google-овим рачунарима у тренуцима кад су били беспослени, за које би добром стоном рачунару с јаким процесором (на пример Нехалем са четири језгра на 2,8 GHz) било потребно 35 година.

Проблем је решен тако што је разложен на 2.217.093.120 мањих проблема (скупова) од којих је сваки садржао по 19.508.428.800 различитих позиција. Број тих скупова је потом редукован на 55.882.296 коришћењем симетрија. Сваки од њих био је довољно мали да стане у меморију модерног персоналног рачунара, а начин на који је био разложен омогућавао је да се сваки скуп реши брзо.

Овим истраживањем окончано је тридесетогодишње трагање за најефикаснијим начином да се исправно поређа 26 обојених коцкица спојених у већу коцку коју је 1974. изумео мађарски професор архитектуре Ерне Рубик а 1980. почела да продаје широм света компанија Ideal Toys.

Тим који је решио проблем саопштио је де је требало да прође 15 година од појаве коцке да се нађе прва позиција која доказано захтева 20 потеза да се реши и да је стога било сасвим примерено да се после исто толико година докаже да је 20 потеза довољно и за сваку другу позицију.

Ни тим ни Гугл нису саопштили колико је рачунара коришћено ни колико су били јаки, али су зато открили да је проблем решен за свега неколико недеља.

Њихов рад се ослањао на резултате бројних истраживача, почев од Морвина Тистлетвајта који је 1981. показао да су 52 потеза довољни да се дође до решења било које позиције. До 1992. је Мајкл Рејд показао да је увек довољно 39 потеза, али је дан касније Дик Винтер показао да је довољно 37. Број се потом и даље постепено смањивао да би се најзад у јулу ове године стигло до коначног решења.

Ентузијазам који прати Рубикову коцку не завршава се само на проналажењу овог броја већ и такмичењу ко ће брже да је сложи. Актуелни светски рекордер је Холанђанин Ерик Акерсдијк коме је за то било потребно свега 7,08 секунди. У стопу га прате, а на моменте и престижу у брзини, роботи склопљени од Лего коцки.

Детаљније објашњење и додатне информације о томе како се дошло до овог броја налазе се овде.

Додајмо још за крај да они који никада нису успели да реше Рубикову коцку могу да искористе неки од бројних водича за њено решавање и окану се једног од раније добро познатог и релати