Nyolckirálynő-probléma
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.[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 |
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 (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 |
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
- ↑ The Q27 Project. (Hozzáférés: 2016. szeptember 20.)
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 Archiválva 2008. április 22-i dátummal a Wayback Machine-ben - C++ nyelven írt program
- Queens on the Board[halott link] Java program, ami szemléltetni a megoldásokat 1<=n<=20 esetén. (A program már nem letölthető.)
Kapcsolódó szócikkek
- Informatikai portál • összefoglaló, színes tartalomajánló lap