A nyolckirálynő-probléma egy sakkfeladvány, lényege a következő: hogyan lehet 8 királynőt úgy elhelyezni egy 8×8-as sakktáblán, hogy a sakk szabályai szerint ne üssék egymást. Ehhez a királynő/vezér lépési lehetőségeinek ismeretében az kell, hogy ne legyen két bábu azonos sorban, oszlopban vagy átlóban.

A nyolckirálynő-probléma egy példa az ennél általánosabb „n királynő problémára”, ami azt a kérdést veti fel, hányféleképpen lehet lerakni n darab királynőt egy n×n-es táblán.

Történet:

A kérdést először Max Bezzel vetette fel 1848-ban. Az évek során sok matematikus – többek között Gauss és Georg Cantor – foglalkozott vele, és az általánosított n-királynő-problémával.

Az első megoldást Franz Nauck adta 1850-ben.

1874-ben S. Gunther determinánsok használatával adott egy eljárást, amivel lerakhatóak a bábuk. Később ezt J. W. L. Glaisher finomította.

Edsger Dijkstra 1972-ben arra használta ezt a problémát, hogy bemutassa a strukturált programozás előnyeit, erejét. Publikált egy részletes leírást a backtrack algoritmusról.

Megoldás:

A megoldás nehezen számítható ki, mivel a bábuknak összesen különböző lerakása létezik, de ebből csak 92 felel meg az n-királynő probléma szabályainak. Ez igen nagy számítási időt jelent. Az összes lehetséges lerakások száma, és ezáltal a számításhoz szükséges idő csökkenthető azáltal, hogy bevezetünk egy olyan szabályt, miszerint minden sorban (vagy oszlopban) csak egy-egy bábu állhat. Így a vizsgálandó lerakások száma csupán (16884-szer kevesebb). Ez n=8-ra kezelhető, de megengedhetetlenül nagy például n=1 000 000-ra már nem.

Algoritmizálási szempontból a bábuk helyét érdemes tömbként kezelni: mivel minden sorban csak egyetlen bábu állhat, ezért elég a sorokat megszámozni (1-től n-ig), majd n darab számot lejegyezni aszerint, hogy az n-edik sorban hányadik helyen áll bábu.

Itt egy algoritmus, ami egy – a probléma szabályainak megfelelő – tömböt ad eredményül (n≥4 és n=1 esetekre):

• Osszuk el n-et 12-vel. Jegyezzük le a maradékot.
• Írjuk le egy listába 2-től n-ig a páros számokat növekvő sorrendben.
• Ha a maradék 3 vagy 9, akkor a 2-es számot vigyük át a lista végére.
• Írjuk a lista végére 1-től n-ig a páratlan számokat növekvő sorrentben, de ha a maradék 8, akkor páronként cseréljük fel őket (például 3, 1, 7, 5, 11, 9, …).
• Ha a maradék 2, akkor cseréljük ki az 1-et és 3-at, valamint tegyük az 5-öt a lista végére.
• Ha a maradék 3 vagy 9, akkor tegyük az 1-et és 3-at a lista végére (ebben a sorrendben).

Végül tegyük le a bábukat a sakktáblára: az első sorba oda, ahova a lista első száma mutatja; a második sorba oda, ahová a lista második száma mutatja…

Néhány példa:

• 14 királynő: 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5
• 15 királynő: 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3
• 20 királynő: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17

A probléma megoldásainak száma (n≤26)

Az alábbi táblázat tartalmazza a lerakások számát. A lényegesen különböző oszlopban jegyzett értékeket úgy kaptuk, hogy az elforgatással vagy tükrözéssel egymásba vihető lerakásokat csak egyszer számoltuk meg.

A probléma megoldásai n=8 esetben

Mint a fenti táblázat mutatja, egy szabványos, 8×8-as táblán 92 olyan lerakási mód van, amikor a királynők nem ütik egymást. Az elforgatással nem egymásba vihetőek alább láthatóak: