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.
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.
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
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.[1]
| n | különböző (A000170 sorozat az OEIS-ben) | lényegesen különböző (A002562 sorozat az OEIS-ben) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 0 | 0 |
| 3 | 0 | 0 |
| 4 | 2 | 1 |
| 5 | 10 | 2 |
| 6 | 4 | 1 |
| 7 | 40 | 6 |
| 8 | 92 | 12 |
| 9 | 352 | 46 |
| 10 | 724 | 92 |
| 11 | 2680 | 341 |
| 12 | 14 200 | 1787 |
| 13 | 73 712 | 9233 |
| 14 | 365 596 | 45 752 |
| 15 | 2 279 184 | 285 053 |
| 16 | 14 772 512 | 1 846 955 |
| 17 | 95 815 104 | 11 977 939 |
| 18 | 666 090 624 | 83 263 591 |
| 19 | 4 968 057 848 | 621 012 754 |
| 20 | 39 029 188 884 | 4 878 666 808 |
| 21 | 314 666 222 712 | 39 333 324 973 |
| 22 | 2 691 008 701 644 | 336 376 244 042 |
| 23 | 24 233 937 684 440 | 3 029 242 658 210 |
| 24 | 227 514 171 973 736 | 28 439 272 956 934 |
| 25 | 2 207 893 435 808 352 | 275 986 683 743 434 |
| 26 | 22 317 699 616 364 044 | 2 789 712 466 510 289 |
| 27 | 234 907 967 154 122 528 | 29 363 495 934 315 694 |
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:
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 (A051223 sorozat az OEIS-ben).
| n | szuperkirálynők lerakásainak száma |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 0 |
| 6 | 0 |
| 7 | 0 |
| 8 | 0 |
| 9 | 0 |
| 10 | 4 |
| 11 | 44 |
| 12 | 156 |
| 13 | 1876 |
| 14 | 5180 |
| 15 | 32 516 |
| 16 | 202 900 |
| 17 | 1 330 622 |
| 18 | 8 924 976 |
| 19 | 64 492 432 |
| 20 | 495 864 256 |
| 21 | 3 977 841 852 |
| 22 | 34 092 182 276 |
| 23 | 306 819 842 212 |
| 24 | 2 883 202 816 808 |
| 25 | 28 144 109 776 812 |
| 26 | 286 022 102 245 804 |
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.
Példakód
#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;
}
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
