Királynőprobléma

A Wikipédiából, a szabad lexikonból.

A királynőprobléma egy fejtörő; akik ismerik a hagyományos sakkjáték szabályait, azok számára egyszerűen elmondható:

8 darab királynőt (vezért) kell elhelyezni egy sakktáblán úgy, hogy semelyik se üsse semelyik másikat.

Másképp mondva, egy 8×8-as táblázatba úgy kell 8 elemet (mondjuk pöttyöket vagy 1-eseket) elhelyezni, hogy minden (8 db.) sorban, minden (8 db.) oszlopban, és mindegyik (30 db.) átlóban legfeljebb egy elem legyen található.

A nyolc királynő problémának összesen 92 darab megoldása van. Ezek közül az egyik:

K K K K K K K K

A fejtörő egy általánosítása az n-királynőprobléma: egy n×n-es táblázatba kell n db. elemet(királynőt) úgy elhelyezni, hogy semelyik két elem ne kerüljön egy sorba, egy oszlopba, vagy egy átlóba.

A királynőprobléma a mesterséges intelligencia tankönyvek egyik „állatorvosi lova”: olyan feladat, amelyen sok algoritmus működése jól illusztrálható.