Nyolckirálynő-probléma

A nyolckirálynő-probléma egy sakkfeladvány, lényege a következő: hogyan lehet 8 királynőt ú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

A megoldás 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 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^8=16777216$ (16884-szer kevesebb). Ez n=8-ra kezelhető, de megengedhetetlenül nagy 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ő sorrentben, 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≤26)

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	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	n/a
25	2 207 893 435 808 352	n/a
26	22 317 699 616 364 044	n/a

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.

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

Lásd még

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

Külső hivatkozások

• 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 - C++ nyelven írt program
• http://www.research.att.com/~njas/sequences/A051223 - szuperkirálynő az OEIS-en
• Quens on the Board Java program ami szemléltetni a megoldásokat 1<=n<=20 esetén! (A program már nem letölthető.)