8 királynő probléma

A Wikipédiából, a szabad enciklopédiából.

A probléma lényege a következő: helyezzünk el 8 királynőt egy 8×8-as sakktáblán úgy, hogy a sakk szabályai szerint ne üssék egymást. Ehhez az kell, hogy ne legyen két bábu azonos sorban, oszlopban vagy átlóban.

A 8 kirá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, hogy hányféleképpen lehet lerakni n darab királynőt egy n×n-es táblán.

Tartalomjegyzék 1 Történet 2 Megoldás 3 A probléma megoldásainak száma (n≤25) 4 A probléma megoldásai n=8 esetben 5 Hasonló problémák 5.1 n-szuperkirálynő probléma 6 Lásd még 7 Külső hivatkozások

[szerkesztés] 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án.

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.

[szerkesztés] Megoldás

A probléma nehezen kiszámítható, mivel a bábuknak összesen különböző lerakása létezik, de ebből csak 92 felel meg az n-kirá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⁸ = 16.777.216 (16884-szer kevesebb). Ez n=8-ra kezelhető, de megengedhetetlenül nagy például n=1.000.000-ra.

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ábú. 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ő sorrentben, de ha a maradék 8, akkor páronként cseréljük fel őket (pl. 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

[szerkesztés] A probléma megoldásainak száma (n≤25)

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.

n	különböző	lényegesen különböző
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	2.680	341
12	14.200	1.787
13	73.712	9.233
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	n/a
25	2.207.893.435.808.352	n/a

[szerkesztés] 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:

[szerkesztés] Hasonló problémák

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

Hasonló az n-királynő problémához, csak itt ún. 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.

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	1
11	44
12	156
13	1.876
14	5.180
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

[szerkesztés] Lásd még

• Domináns királynők problémája

[szerkesztés] Külső hivatkozások

• n-királynő projekt - eddig még ki nem számolt méretű sakktáblákat dolgoz fel (bárki csatlakozhat)
• 8 királynő probléma megoldása "okos" táblával - egyetemi jegyzet
• 8 királynő probléma megoldása "okos" táblával - C++ nyelven írt program
• http://www.research.att.com/~njas/sequences/A051223 - szuperkirálynő az OEIS-en