God’s algorithm (traducere libera: algoritmul lui Dumnezeu) a luat nastere odata cu discutiile despre rezolvarea cubului Rubik. God’s numer (Numarul lui Dumnezeu) este numarul cel mai mic de miscari prin care in oricare dintre combinatiile puzzle-ului se poate rezolva. Folosind supercomputere de la Google raspunsul a iesit la iveala: numarul lui Dumnezeu e 20.
Pentru inceput trebuie precizat ca algoritmul lui Dumnezeu se poate aplica pentru orice puzzle. Doar ca a luat nastere din discutiile pentru rezolvarea cubului Rubik. Incercarile au inceput prin 1981 cand s-a reusit rezolvarea cubului in minim 18 miscari si maxim 52, ceea ce era mult.
S-a ajuns incet incet la o diferenta mai mica intre numarul maxim si numarul minim. In 2008 numarul maxim a ajuns la 22 si cel minim la 20. Acum, in Iulie 2010, misterul a fost spulberat. Numarul maxim este 20. In 20 sau mai putine miscari poti rezolva oricare din cele 43.252.003.274.489.856.000 combinatii.
Rezolvarea a fost posibila cu ajutorul Google care a pus la dispozitia cercetatorilor o serie de calculatoare. Nu a fost dezvaluita configuratia acestora insa daca ar fi sa rezolvati algoritmul cu ajutorul unui procesor Intel Nehalem cu patru nuclee ce ruleaza la 2.8GHz ati avea nevoie de 35 de ani la dispozitie. Deci calculatoarele Google erau performante. 🙂
Mai multe informatii gasiti pe pagina dedicata: Cube20.
Parerea mea e ca era mult mai interesant de cautat si descoperit o demonstratie matematica a acestui numar decat simulari infinite pe calculator. Dar e totusi un un pas inainte, de ce sa nu recunoastem.