Puzzle-ul celor opt regine: Premiu de un milion de dolari pentru oricine poate rezolva o versiune complexă a acestei probleme clasice din şah

Un institut de matematică din Statele Unite oferă 1 milion de dolari oricui poate dezvolta un algoritm ce poate rezolva o versiune complexă a puzzle-ui celor opt regine.

Acest puzzle, publicat iniţial în anul 1848, implică amplasarea a opt regine pe o tablă clasică de şah astfel încât niciuna dintre piese să nu se ameninţe în mod direct. Soluţia la această versiune iniţială nu este una extrem de dificil de găsit, în fapt există 92 de soluţii, ce-i drept, din peste 4,5 miliarde de variante posibile.

Însă acest puzzle devine cu adevărat interesant în momentul în care trebuie găsite soluţii pentru amplasarea a n-regine (unde n este numărul de piese, rânduri şi coloane) pe o tablă: imaginaţi-vă acelaşi puzzle dar în care avem, să zicem, 1.000 de regine de amplasat pe o tablă cu 1.000 de pătrăţele pe o latură. În plus, problema poate deveni şi mai complexă prin introducerea unor poziţii fixe a unui număr dat de piese.

Deşi această problemă poate părea uşor de reprezentat mental, descoperirea unor modalităţi pentru rezolvarea într-un mod eficient a acestui puzzle – pentru orice valoare a lui n – este în fapt una dintre cele mai dificile probleme din domeniul informaticii. În fapt, pentru cazurile în care n ia valori ridicate, niciun calculator nu mai este capabil să rezolve această problemă.

Din acest motiv, o serie de cercetători de la Universitatea St. Andrews din Marea Britanie sunt de părere că un program de calculator capabil să rezolve această variantă impenetrabilă a acestui puzzle – şi care să nu necesite sute de ani pentru a calcula valori ridicate ale lui n – ar fi suficient de puternic pentru a rezolva multe alte probleme de matematică cu variabile înalte, şi pe care calculatoarele de astăzi nu le pot rezolva.

„Dacă cineva ar putea scrie un program de calculator care să poată rezolva această problemă foarte rapid, l-am putea adapta pentru a rezolva multe dintre cele mai importante probleme ce ne afectează zilnic”, a afirmat Ian Gent, cercetător la Universitatea St. Andrews.

„Acestea includ probleme triviale precum identificarea celui mai mare grup format din prietenii de pe Facebook ce nu se cunosc între ei, sau unele foarte importante precum spargerea codurilor ce fac posibile tranzacţiile financiare online”, a susţinut Gent.

Astfel, după ce echipa de cercetători a profesorului Ian Gent a demonstrat că Puzzle-ul cu n-Regine face parte din categoria problemelor P vs NP, Institutul Clay de Matematică din Statele Unite a anunţat că oferă 1 milion de dolari oricui poate rezolva această problemă.

„Ceea ce am reuşit să arătăm în articolul nostru, publicat în Journal of Artificial Intelligence Research, este că problema cu n-regine face parte din clasa problemelor denumite NP-Complete”, a explicat Gent.

„Dacă acest lucru este corect, atunci înseamnă că orice algoritm ce poate rezolva această problemă poate fi folosit indirect pentru a rezolva orice altă problemă din clasa NP-C”.

Conform cercetătorului britanic, premiul poate fi câştigat prin fie demonstrarea faptului că niciun algoritm nu poate rezolva acest puzzle într-un timp rezonabil, sau prin dezvoltarea unui astfel de algoritm capabil să-l rezolve rapid – în termeni matematici, într-o perioadă de timp polynomială.

„Toată această discuţie este pur teoretică. În practică, nimeni nu a reuşit nici măcar să se apropie de elaborarea unui astfel de algoritm. Deci, ceea ce am arătat în articolul nostru, dincolo de toate aceste scopuri practice, este că elaborarea unui astfel de algoritm este imposibilă”, a afirmat Peter Nightingale, unul dintre membrii echipei de la St. Andrews.