257 millió forintot kap, aki képes megfejte(t)ni ezt a feladványt

Egy 167 éves sakkfeladványról van szó, az úgynevezett nyolckirálynő-problémáról. Azt eredeti feladványnál azt kell(ene) kitalálni, hogy hányféleképpen lehet nyolc királynőt (vezért) elhelyezni a sakktáblán, hogy azok a sakk szabályai szerint ne üthessék egymást. A nyolckirálynő-probléma ma már ennél általánosabb, a kérdést úgy is fel lehet tenni, hogy hányféleképpen lehet n darab királynőz elhelyezni egy n x n-es „sakktáblán”.

Az amerikai Clay Mathematics Institute (CMI) sem az eredeti feladvány megoldásáért kínál díjat, hanem annak ezres változatáért, azaz ezer királynő elhelyezéséért egy 1000 x 1000 négyzetes táblán.

Alphr

Természetesen számítógépes programokat várnak, ám azt nem titkolják, hogy szerintük még egy komputernek is évekbe telne megoldani a feladványt. Kétféle megoldást is elfogadnak, vagy annak a bizonyítását, hogy egyetlen algoritmus sem tudná ésszerű időn belül megoldani a problémát, vagy olyan algoritmust találni, amelyik gyorsan megoldja azt. Amennyiben mégis születne gyors eredményt hozó program, azt már adaptálni lehetne napjaink legfontosabb problémáinak megoldására.

Makay Géza, a Szegedi Tudományegyetem docensének megkeresése nyomán pontosítjuk a kiírást: egészen pontosan úgy néz ki a feladvány, hogy táblán előre elhelyeznek királynőket, és olyan algoritmust kell találni, ami ezeket helyben hagyva polinomiális idő alatt oldja meg az n-kiralynő problémát, vagy egy bizonyítást, hogy ilyen algoritmus nem létezik.

Ha máskor is tudni szeretne hasonló dolgokról, lájkolja a HVG Tech rovatának Facebook-oldalát.