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 ${\binom {64}{8}}=4426165368$ 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 $8^{8}=16777216$ (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.

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.

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;
}

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 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