Nyolckirálynő-probléma

sakkfeladvány

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 szerkesztés

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 szerkeszté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) szerkesztés

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 szerkesztés

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 szerkesztés

n-szuperkirálynő-probléma szerkesztés

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 szerkesztés

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

Jegyzetek szerkesztés

  1. The Q27 Project. (Hozzáférés: 2016. szeptember 20.)

További információk szerkesztés

Kapcsolódó szócikkek szerkesztés