Algoritem za rešitev Rubikovih kock vseh velikosti

Reševanje Rubikove kocke je priljubljeno opravilo, ki ni primerno le za kratkočasenje, ampak ima tudi povsem resne matematično-računalniške implikacije. O klasičnih Rubikovi kocki 3 x 3 x 3 je znano domala vse, saj obstoji tudi algoritem, ki za vsako legalno postavitev izračuna najhitrejše zaporedje korakov za rešitev kocke. Lani je bilo celo dokazano, da je vsako kocko mogoče rešiti v največ 20 potezah. Dokaz je bil zanimiv tudi zato, ker je šlo za surovo preverjanje vseh možnih permutacij (brute-force).

Pri kockah večjih razsežnosti to odpove, zato je treba problem reševati pametneje. Erik Demaine z MIT-a je poiskal splošni algoritem za reševanje Rubikove kocke s stranico n. Ugotovil je, da število korakov iskanja proporcionalno z n² / ln n. Dosedanji rezultat O(n²) je temeljil na zaporednem premikanju skupin štirih polj (2 x 2), Demaine pa je ugotovil, da je mogoče hkrati premikati več takih skupin.

Tovrstne raziskave imajo poleg akademske zanimivosti tudi povsem uporabno vrednost, saj se temu problemu sorodni pojavljajo tudi pri sortiranju, razvrščanju ali iskanju nekaterih setov podatkov v računalništvu.