A nyolckirálynő-probléma egy sakkfeladvány, lényege a következő: hogyan, illetve hányféleképpen lehet 8 királynőt (vezért) ú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 Bár egy jó elrendezés megtalálása viszonylag egyszerű (még nagyobb táblán is, lásd például a lenti algoritmus), az összes megoldás már 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 a nyolckirá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 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ő sorrendben, 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 ≤ 27) 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 legnagyobb táblaméret, amelyhez kiszámolták az elhelyezések számát jelenleg 27. nkülönböző lényegesen különböző 111200300421510264174068921293524610724921126803411214 20017871373 712923314365 59645 752152 279 184285 0531614 772 5121 846 9551795 815 10411 977 93918666 090 62483 263 591194 968 057 848621 012 7542039 029 188 8844 878 666 80821314 666 222 71239 333 324 973222 691 008 701 644336 376 244 0422324 233 937 684 4403 029 242 658 21024227 514 171 973 73628 439 272 956 934252 207 893 435 808 352275 986 683 743 4342622 317 699 616 364 0442 789 712 466 510 28927234 907 967 154 122 52829 363 495 934 315 694
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:
Hasonló problémák n-szuperkirálynő-probléma Hasonló az n-királynő-problémához, csak itt úgynevezett „szuperkirálynőket” kell a táblára rakni. A szuperkirálynő léphet úgy, mint egy klasszikus sakkbeli királynő (vízszintes, függőleges, átlós), és tud ugrani, mint a huszár .
nszuperkirálynők lerakásainak száma112030405060708090104114412156131876145180151617181920212223242526
Példakód
A következőkben látható egy C++ nyelven írt, backtrackingre alapuló algoritmus. A program bekérdezi N értékét, majd egy N*N méretű táblára próbál meg N királynőt letenni. Alaphelyzetben kiírja az összes lehetséges lerakást, s a lehetőségek számát.
#include<iostream>
int n; // tábla mérete int *columns; // az adott oszlopban lévő királynő hányadik sorban található; indexelés a bal felső saroktól!
void print(); bool isBeaten(int, int); int put(int, bool, bool);
int main() { std::cin >> n;
columns = new int[n](); for (int i = 0; i < n; i++) { columns[i] = -1;
int sum = put(0, true, true); std::cout << sum << std::endl;
delete[] columns; return 0; }
/** * Kiírja a sakktáblát */ void print() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (columns[j] == i) { std::cout << "X "; } else { std::cout << "O ";
std::cout << std::endl;
std::cout << std::endl << std::endl; }
/** * Megállapítja, hogy a ('row', 'col') koordinátájú mező ütésben van-e. * * @param row a sor száma * @param col az oszlop száma * @return true ha a ('row', 'col') koordinátájú pont ütésben van valamelyik királynő által */ bool isBeaten(int row, int col) {
// sor ellenőrzése for (int i = 0; i < n; i++) { if (columns[i] == row) { return true;
// átló balra fel for (int i = 0; i <= col && i <= row; i++) { if (columns[col - i] == row - i) { return true;
// átló balra le for (int i = 0; i <= col && row + i < n; i++) { if (columns[col - i] == row + i) { return true;
return false; }
/** * Megpróbál lerakni egy királynőt a 'col' oszlopba. * * @param col az oszlop száma * @param searchAll keresse-e meg az összes lehetséges lerakást * @param printAll kiírja-e az összes talált lerakást * @return lehetséges lerakások száma */ int put(int col, bool searchAll, bool printAll) {
// Ha már túlmentünk a táblán, akkor találtunk egy jó lerakást, tehát if (col >= n) {
// ha ki kell írni, akkor kiírjuk, és if (printAll) { print();
// visszatérünk 1-gyel. return 1;
int r = 0;
// Végigmegyünk az összes soron, for (int i = 0; i < n; i++) {
// s ha le tudunk tenni egy királynőt, if (!isBeaten(i, col)) {
// akkor letesszük, columns[col] = i;
// majd az továbbmegyünk a következő oszlopra; r += put(col + 1, searchAll, printAll);
// ha nem keressük az összes lehetőséget és találtunk már, akkor visszatérünk, if (!searchAll && r > 0) { return r;
// különben folytatjuk a keresést, s kivesszük a letett királynőt; columns[col] = -1;
// végül visszatérünk a lerakások számával. return r; }
Jegyzetek
További információk NQueens@home BOINC projekt A nyolckirálynő-probléma megoldása „okos” táblával - egyetemi jegyzet nyolckirálynő-probléma megoldása „okos” táblával - C++ nyelven írt program Queens on the Board Java program, ami szemléltetni a megoldásokat 1<=n<=20 esetén. (A program már nem letölthető.)
Kapcsolódó szócikkek Domináns királynők problémája
Kategória:Sakk Kategória:Számítógép-tudomány Kategória:Kombinatorika Kategória:Szórakoztató matematika Kategória:Matematikai problémák