MEĐU IZMEĐU

MILION ZA OSAM KRALJICA

1.298 pregleda
Nerešena zagonetka (Stok)

Sama zagonetka je rešena, ali su svi kompjuterski programi neslavno propali kad se poveća šahovska tabla.

Ko reši ovu zagonetku, dobiće milion dolara. Naučnik, profesor Ijan Gent, i njegov tim sa Univerziteta Sent Endrjus nude nagradu od milion dolara osobi koja uspe da smisli program koji će rešiti „Kraljičinu zagonetku”.

Zadatak koji se postavlja pred igrače
jeste da na standardnu šahovsku tablu
postave osam kraljica, tako da nijedna
ne može da napadne neku drugu.

Pre nego što se ponadate, iako je to takmičenje otvoreno za sve, nemojte misliti da je jednostavno, osim ako niste stručnjak za programiranje, piše „Unilad”.

„Kraljičina zagonetka” nastala 1850. godine, uključuje osam figura sa šahovske table. Štaviše, osam kraljica. Zadatak koji se postavlja pred igrače jeste da na standardnu šahovsku tablu postave osam kraljica, tako da nijedna ne može da napadne neku drugu.

To znači postavljanje kraljica u različite redove tako da dve kraljice nisu u istoj koloni niti se mogu sresti dijagonalno. Sama zagonetka je rešena, ali su svi kompjuterski programi neslavno propali kad se poveća šahovska tabla.

Gent i njegove kolege veruju da bi računarski program, koji može da reši taj zadatak, mogao da bude dovoljno sofisticiran da reši većinu zadataka, poput dekriptovanja najtežih sigurnosnih softvera.

„Ako možete da napišete program koji može da reši taj zadatak brzo, onda možete da ga prilagodite da rešava većinu bitnih problema koji nas danas muče”, rekao je Ijan Gent. „To uključuje trivijalne zadatke poput toga da nađete najveću grupu vaših prijatelja na ,Fejsbuku` koji se međusobno ne poznaju, ali i važne zadatke poput provaljivanja kodova koji osiguravaju naše onlajn transakcije.”

Razlog zbog kojeg je teško napisati taj program jeste velik broj varijabli koje su uključene u njega. Zbog toga bi moglo da potraje i nekoliko godina dok se program konačno ne ostvari.

„U praksi, niko nije bio ni blizu uspešnom pisanju programa”, rekao je jedan od naučnika. Ako vas zanima ovaj izazov i mislite da možete da napišete svoj program i da dobijete milion dolara, onda se javite Klej institutu za matematiku u SAD.

(Izvor B92)

O autoru

Stanko Stojiljković

1 komentar

  • Pisem ovaj komentar sa jedinom svrhom da ustedim vreme i trud programerima. Pratim rezultate u vezi ovog izazovnog problema bar 30 godina kao matematicar i programer. Medjutim, problem nema resenje ako se pod „resenjem“ podrazumeva nalazenje broja B(N) razlicitih rasporeda nenapadajucih kraljica na „sahovskoj“ tabli NxN za proizvoljno N. Ne postoji formula u zatvorenom obliku za B(N), ne postoji ni rekurenta relacija kao ni funkcija generatrise. Do partikularnog resenja (za konkretno N>10) moze se doci iskljucivo pomocu racunarskih programa. Napisan je veliki broj programa na razlicitim programskim jezicima; programi postaju sve sofisticiraniji i skracuju vreme nalazenja svih pozicija B(N), ali problem se javlja kada je N veliko. Naprimer, na tabli 27×27 broj razlicitih rasporeda kraljica pise se sa 18 decimalnih cifara. Ukoliko je N veliko program, ma kako superioran, moze raditi godinama cak i na super-kompjuterima. To je poznato i onima koji su raspisali veoma vrednu nagradu, zato su i ponudili milionsku sumu. Moj savet programerima je da na drugi nacin utrose svoje vreme (i mozda zaista dodju do izvesne zarade), jer se u svetu vodi velika trka programerskih timova uz pomoc mocnih racunara i to ne zbog (nedostizne) nagrade, vec usavrsavanja programa i postavljanja rekorda u pogledu broja B(N), nesto slicno kao pri izracunavanju sto veceg broja decimala broja pi. Uzgred, da napomenem da se ovim problemom na standardnoj tabli 8×8 bavio i jedan od najvecih svetskih matematicara Fridrih Gaus. Ko voli ovu vrstu problema, moze da pokusa (rucno ili pomocu racunara), ali na standardnoj tabli 8×8 (postoje 92 resenja).

Ostavite komentar