Åtta drottningar pussel

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Den enda symmetriska lösningen på pusslet med åtta drottningar ( upp till rotation och reflektion)

åtta damer är problemet med att placera åtta schackdamer på ett 8×8 schackbräde så att inga två damer hotar varandra; därför kräver en lösning att inga två damer delar samma rad, kolumn eller diagonal. Det finns 92 lösningar. Problemet uppstod först i mitten av 1800-talet. I modern tid används det ofta som ett exempel på problem för olika datorprogrammeringstekniker .

Pusslet med åtta drottningar är ett specialfall av det mer allmänna n- queens-problemet med att placera n icke-attackerande damer på ett n × n schackbräde. Lösningar finns för alla naturliga tal n med undantag för n = 2 och n = 3. Även om det exakta antalet lösningar endast är känt för n ≤ 27, är den asymptotiska tillväxthastigheten för antalet lösningar ungefär (0,143 n ) ⁿ .

Historia

Schackkompositören Max Bezzel publicerade pusslet med åtta drottningar 1848. Franz Nauck publicerade de första lösningarna 1850. Nauck utökade också pusslet till problemet med n drottningar, med n damer på ett schackbräde med n × n rutor.

Sedan dess har många matematiker , inklusive Carl Friedrich Gauss , arbetat med både åtta drottningar-pusslet och dess generaliserade version av n -drottningar. År 1874 föreslog S. Gunther en metod som använder determinanter för att hitta lösningar. JWL Glaisher förfinade Gunthers tillvägagångssätt.

1972 använde Edsger Dijkstra detta problem för att illustrera kraften i vad han kallade strukturerad programmering . Han publicerade en mycket detaljerad beskrivning av en djup-först backtracking-algoritm .

Konstruera och räkna lösningar när n = 8

Problemet med att hitta alla lösningar på 8-queens-problemet kan vara ganska beräkningsmässigt dyrt, eftersom det finns 4 426 165 368 möjliga arrangemang av åtta damer på ett 8×8-bräde, men bara 92 lösningar. Det är möjligt att använda genvägar som minskar beräkningskrav eller tumregler som undviker brute-force beräkningstekniker . Till exempel, genom att tillämpa en enkel regel som väljer en dam från varje kolumn, är det möjligt att minska antalet möjligheter till 16 777 216 (det vill säga 8 8 ) ^möjliga kombinationer. Att generera permutationer minskar möjligheterna ytterligare till bara 40 320 (det vill säga 8! ), som sedan kan kontrolleras för diagonala attacker.

Pusslet med åtta drottningar har 92 distinkta lösningar. Om lösningar som endast skiljer sig åt genom symmetrioperationerna rotation och reflektion av brädan räknas som en, har pusslet 12 lösningar. Dessa kallas grundläggande lösningar; representanter för var och en visas nedan.

En grundläggande lösning har vanligtvis åtta varianter (inklusive dess ursprungliga form) som erhålls genom att rotera 90, 180 eller 270° och sedan reflektera var och en av de fyra rotationsvarianterna i en spegel i ett fast läge. En av de 12 grundläggande lösningarna (lösning 12 nedan) är dock identisk med sin egen 180° rotation, så har bara fyra varianter (själv och dess reflektion, dess 90° rotation och reflektionen av det). Sådana lösningar har bara två varianter (själv och dess reflektion). Således är det totala antalet distinkta lösningar 11×8 + 1×4 = 92.

Alla grundläggande lösningar presenteras nedan:

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 1

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 2

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 3

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 4

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 5

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 6

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 7

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 9

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 10

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 11

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Lösning 12

Lösning 10 har den ytterligare egenskapen att inga tre damer är i en rak linje . Lösningar 1 och 8 har en linje med 4 damer.

Förekomsten av lösningar

Brute-force-algoritmer för att räkna antalet lösningar är beräkningsmässigt hanterbara för n = 8 , men skulle vara svårlösta för problem med n ≥ 20 , som 20! = 2,433 × 10 ¹⁸ . Om målet är att hitta en enda lösning kan man visa att det finns lösningar för alla n ≥ 4 utan någon som helst sökning. Dessa lösningar uppvisar trappstegsmönster, som i följande exempel för n = 8, 9 och 10:

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Trapplösning för 8 drottningar

	a	b	c	d	e	f	g	h	i
9										9
8										8
7										7
6										6
5										5
4										4
3										3
2										2
1										1
	a	b	c	d	e	f	g	h	i

Trapplösning för 9 drottningar

	a	b	c	d	e	f	g	h	i	j
10											10
9											9
8											8
7											7
6											6
5											5
4											4
3											3
2											2
1											1
	a	b	c	d	e	f	g	h	i	j

Trapplösning för 10 drottningar

Exemplen ovan kan erhållas med följande formler. Låt ( i , j ) vara kvadraten i kolumn i och rad j på n × n schackbrädet, k ett heltal.

Ett tillvägagångssätt är

1. Om resten från att dividera n med 6 inte är 2 eller 3 så är listan helt enkelt alla jämna tal följt av alla udda tal som inte är större än n .
2. Skriv annars separata listor med jämna och udda tal (2, 4, 6, 8 – 1, 3, 5, 7).
3. Om resten är 2, byt 1 och 3 i udda lista och flytta 5 till slutet ( 3, 1 , 7, 5 ).
4. Om resten är 3, flytta 2 till slutet av jämn lista och 1,3 till slutet av udda lista (4, 6, 8, 2 – 5, 7, 9, 1, 3 ).
5. Lägg till udda lista till den jämna listan och placera damer i raderna som ges av dessa nummer, från vänster till höger (a2, b4, c6, d8, e3, f1, g7, h5).

För n = 8 resulterar detta i fundamental lösning 1 ovan. Några fler exempel följer.

• 14 damer (återstoden 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
• 15 damer (resten 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
• 20 damer (återstoden 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

Räknelösningar för andra storlekar n

Exakt uppräkning

Det finns ingen känd formel för det exakta antalet lösningar för att placera n drottningar på ett n × n bräde, dvs antalet oberoende uppsättningar av storlek n i en n × n drottningsgraf . 27×27-brädan är den högsta ordningen som har räknats upp fullständigt. Följande tabeller ger antalet lösningar på n queens-problemet, både grundläggande (sekvens A002562 i OEIS ) och alla (sekvens A000170 i OEIS ), för alla kända fall.

n	grundläggande	Allt
1	1	1
2	0	0
3	0	0
4	1	2
5	2	10
6	1	4
7	6	40
8	12	92
9	46	352
10	92	724
11	341	2,680
12	1,787	14 200
13	9,233	73,712
14	45,752	365,596
15	285 053	2,279,184
16	1,846,955	14,772,512
17	11,977,939	95,815,104
18	83,263,591	666,090,624
19	621 012 754	4,968,057,848
20	4,878,666,808	39,029,188,884
21	39,333,324,973	314,666,222,712
22	336,376,244,042	2,691,008,701,644
23	3,029,242,658,210	24,233,937,684,440
24	28,439,272,956,934	227,514,171,973,736
25	275,986,683,743,434	2,207,893,435,808,352
26	2,789,712,466,510,289	22,317,699,616,364,044
27	29,363,495,934,315,694	234,907,967,154,122,528

Asymptotisk uppräkning

År 2021 bevisade Michael Simkin att för stora antal n är antalet lösningar för n queens-problemet ungefär $(0,143n)^{n}$ . Mer exakt, antalet ${\mathcal {Q}}(n)$ av lösningar har asymptotisk tillväxt

$${\mathcal {Q}}(n)=((1\pm o(1))ne^{-\alpha })^{n}$$

där $\alpha$ är en konstant som ligger mellan 1,939 och 1,945. (Här representerar o (1) lite o notation .)

Om man istället betraktar ett ringformigt schackbräde (där diagonaler "lindar runt" från överkant till botten och från vänsterkant till höger) är det bara möjligt att placera n damer på en $n\ gånger n$ board om $n\equiv 1,5\mod 6.$ I detta fall är det asymptotiska antalet lösningar

$$T(n)=((1+o(1))ne^{-3})^{n}.$$

Relaterade problem

Högre dimensioner

Hitta antalet icke-attackerande damer som kan placeras i ett d - dimensionellt schackutrymme av storlek n . Fler än n damer kan placeras i vissa högre dimensioner (det minsta exemplet är fyra icke-attackerande damer i ett 3×3×3 schackutrymme), och det är faktiskt känt att för varje k finns det högre dimensioner där n ^k damer räcker inte för att attackera alla utrymmen.

Använd andra pjäser än damer

På en 8×8-bräda kan man placera 32 riddare , eller 14 biskopar , 16 kungar eller åtta torn , så att inga två pjäser attackerar varandra. När det gäller riddare är en enkel lösning att placera en på varje ruta av en given färg, eftersom de bara flyttar till motsatt färg. Lösningen är också enkel för torn och kungar. Sexton kungar kan placeras på brädet genom att dela upp det i 2-av-2 rutor och placera kungarna på motsvarande punkter på varje ruta. Placeringar av n torn på en n × n bräda är i direkt överensstämmelse med ordnings- n permutationsmatriser .

Schackvarianter

Relaterade problem kan ställas för schackvarianter som shogi . Till exempel, n + k drakungar kräver att placera k shogi-bönder och n + k ömsesidigt icke-attackerande drakungar på ett n × n shogibräde.

Icke-standardiserade brädor

Pólya studerade n queens-problemet på en ringformad ("munkformad") bräda och visade att det finns en lösning på en n × n -bräda om och bara om n inte är delbart med 2 eller 3. År 2009 fyllde Pearson och Pearson algoritmiskt tredimensionella brädor ( n × n × n ) med n ² damer, och föreslog att multiplar av dessa kan ge lösningar för en fyrdimensionell version av pusslet.

Herravälde

Givet ett n × n bräde är dominansnumret det minsta antal damer (eller andra pjäser) som behövs för att attackera eller ockupera varje ruta. För n = 8 är drottningens dominansnummer 5.

Drottningar och andra pjäser

Varianter inkluderar att blanda drottningar med andra bitar; till exempel att placera m damer och m riddare på ett n × n bräde så att ingen pjäs attackerar en annan eller att placera damer och bönder så att inga två damer attackerar varandra.

Magiska rutor

1992 publicerade Demirörs, Rafraf och Tanik en metod för att omvandla några magiska rutor till n -queens-lösningar och vice versa.

latinska rutor

I en n × n matris, placera varje siffra 1 till n på n platser i matrisen så att inte två instanser av samma siffra finns i samma rad eller kolumn.

Exakt omslag

Betrakta en matris med en primär kolumn för var och en av brädets n rader, en primär kolumn för var och en av de n filerna och en sekundär kolumn för var och en av de 4 n − 6 icke-triviala diagonalerna på brädet. Matrisen har n ² rader: en för varje möjlig drottningplacering, och varje rad har en 1 i kolumnerna som motsvarar den kvadratens rangordning, fil och diagonaler och en 0 i alla andra kolumner. Då n queens likvärdigt med att välja en delmängd av raderna i denna matris så att varje primär kolumn har en 1 i exakt en av de valda raderna och varje sekundär kolumn har en 1 i högst en av de valda raderna; detta är ett exempel på ett generaliserat exakt omslagsproblem , vilket sudoku är ett annat exempel på.

n -queens avslutning

Kompletteringsproblemet frågar om det, givet ett n × n schackbräde där några damer redan är placerade, är möjligt att placera en dam i varje återstående rad så att inga två damer attackerar varandra. Denna och relaterade frågor är NP-komplett och #P-komplett . Alla placeringar av högst n /60 damer kan slutföras, medan det finns partiella konfigurationer av ungefär n /4 damer som inte kan slutföras.

Övning i algoritmdesign

Att hitta alla lösningar på pusslet med åtta drottningar är ett bra exempel på ett enkelt men icke-trivialt problem. Av denna anledning används det ofta som ett exempel på problem för olika programmeringstekniker, inklusive otraditionella metoder som begränsningsprogrammering , logisk programmering eller genetiska algoritmer . Oftast används det som ett exempel på ett problem som kan lösas med en rekursiv algoritm , genom att formulera n- queens-problemet induktivt i termer av att lägga till en enda dam till valfri lösning på problemet med att placera n −1-queens på ett n × n schackbräde. Induktionen bottnar med lösningen på "problemet" med att placera 0 damer på schackbrädet, vilket är det tomma schackbrädet .

Denna teknik kan användas på ett sätt som är mycket effektivare än den naiva brute-force sökalgoritmen , som tar hänsyn till alla 64 ⁸ = 2 ⁴⁸ = 281 474 976 710 656 möjliga blinda placeringar av åtta drottningar, och sedan filtrerar dessa för att ta bort alla placeringar som placerar två damer antingen på samma ruta (lämnar endast 64!/56! = 178.462.987.637.760 möjliga placeringar) eller i ömsesidigt attackerande positioner. Denna mycket dåliga algoritm kommer bland annat att ge samma resultat om och om igen i alla olika permutationer av de åtta drottningarnas tilldelningar, samt att upprepa samma beräkningar om och om igen för de olika delmängderna av varje lösning. En bättre brute-force-algoritm placerar en enda dam på varje rad, vilket leder till endast 8 ⁸ = 2 ²⁴ = 16 777 216 blinda placeringar.

Det går att göra mycket bättre än så här. En algoritm löser pusslet med åtta torn genom att generera permutationerna av siffrorna 1 till 8 (av vilka det finns 8! = 40 320), och använder elementen i varje permutation som index för att placera en dam på varje rad. Sedan avvisar den de brädor med diagonala anfallspositioner.

Denna animation illustrerar bakåtspårning för att lösa problemet. En drottning placeras i en kolumn som är känd för att inte orsaka konflikt. Om en kolumn inte hittas återgår programmet till det senaste bra tillståndet och försöker sedan med en annan kolumn.

Det bakåtspårande djupet-först-sökprogrammet , en liten förbättring av permutationsmetoden, konstruerar sökträdet genom att överväga en rad av tavlan åt gången, vilket eliminerar de flesta icke-lösningskortpositioner i ett mycket tidigt skede av deras konstruktion. Eftersom den avvisar torn- och diagonalattacker även på ofullständiga brädor, undersöker den endast 15 720 möjliga damplaceringar. En ytterligare förbättring, som endast undersöker 5 508 möjliga drottningplaceringar, är att kombinera den permutationsbaserade metoden med den tidiga beskärningsmetoden: permutationerna genereras med djupet först, och sökutrymmet beskärs om den partiella permutationen ger en diagonal attack . Begränsningsprogrammering kan också vara mycket effektiv på detta problem.

min-konflikt lösning till 8 drottningar

Ett alternativ till uttömmande sökning är en 'iterativ reparation'-algoritm, som vanligtvis börjar med alla damer på brädet, till exempel med en dam per kolumn. Den räknar sedan antalet konflikter (attacker) och använder en heuristik för att avgöra hur man kan förbättra placeringen av damerna. Heuristiken ' minimum-konflikter ' – att flytta pjäsen med det största antalet konflikter till den ruta i samma kolumn där antalet konflikter är minst – är särskilt effektiv: den hittar lätt en lösning på även problemet med 1 000 000 drottningar.

Till skillnad från backtracking-sökningen som beskrivs ovan, garanterar inte iterativ reparation en lösning: som alla giriga procedurer kan den fastna på ett lokalt optimum. (I ett sådant fall kan algoritmen startas om med en annan initial konfiguration.) Å andra sidan kan den lösa problemstorlekar som är flera storleksordningar utanför räckvidden för en djup-först-sökning.

Som ett alternativ till backtracking kan lösningar räknas genom att rekursivt räkna upp giltiga dellösningar, en rad i taget. Istället för att konstruera hela brädpositioner spåras blockerade diagonaler och kolumner med bitvisa operationer. Detta tillåter inte återhämtning av individuella lösningar.

Exempel på program

Följande program är en översättning av Niklaus Wirths lösning till programmeringsspråket Python , men klarar sig utan indexaritmetiken som finns i originalet och använder istället listor för att hålla programkoden så enkel som möjligt. Genom att använda en koroutin i form av en generatorfunktion kan båda versionerna av originalet förenas för att beräkna antingen en eller alla lösningar. Endast 15 720 möjliga drottningplaceringar undersöks.

     
       
           
                          
                     
    
         

    0   
     def  queens  (  n  ,  i  ,  a  ,  b  ,  c  ):  om  i  <  n  :  för  j  i  intervallet  (  n  ):  om  j  inte  i  a  och  i  +  j  inte  i  b  och  i  -  j  inte  i  c  :  avkastning från  damer  (  n  ,  i  +  1  ,  a  +  [  j  ],  b  +  [  i  +  j  ],  c  +  [  i  -  j  ])  annars  :  ge  a  för  lösning  i  drottningar  (  8  ,  ,  [],  [],  []) :  print  (  lösning  ) 

I populärkulturen

• I spelet Den 7:e gästen är det 8:e pusslet: "Drottningens dilemma" i spelrummet på Staufs herrgård är de facto åtta drottningar-pusslet.
• I spelet Professor Layton and the Curious Village är det 130:e pusslet: "Too Many Queens 5"( クイーンの問題5 ) ett åtta drottningarpussel.

Se även

• Matematiskt spel
• Matematisk pussel
• Inget problem med tre i rad
• Rökpolynom
• Costas array

Vidare läsning

• Bell, Jordan; Stevens, Brett (2009). "En kartläggning av kända resultat och forskningsområden för n -queens" . Diskret matematik . 309 (1): 1–31. doi : 10.1016/j.disc.2007.12.043 .
•   Watkins, John J. (2004). Över hela linjen: The Mathematics of Chess Problems . Princeton: Princeton University Press. ISBN 978-0-691-11503-0 .
• Allison, L.; Yee, CN; McGaughey, M. (1988). "Tredimensionella NxN-Queens-problem" . Institutionen för datavetenskap, Monash University, Australien.
• Nudelman, S. (1995). "Det modulära N-Queens-problemet i högre dimensioner" . Diskret matematik . 146 (1–3): 159–167. doi : 10.1016/0012-365X(94)00161-5 .
• Engelhardt, M. (augusti 2010). "Der Stammbaum der Lösungen des Damenproblems (på tyska betyder stamtavlan över lösningar på 8-drottningsproblemet" Spektrum der Wissenschaft : 68–71.
• Om The Modular N-Queen Problem in Higher Dimensions , Ricardo Gomez, Juan Jose Montellano och Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexiko.
•   Budd, Timothy (2002). "A Case Study: The Eight Queens Puzzle" (PDF) . En introduktion till objektorienterad programmering (3:e upplagan). Addison Wesley Longman. s. 125–145. ISBN 0-201-76031-2 .
• Wirth, Niklaus (2004) [uppdaterad 2012]. "The Eight Queens Problem". Algoritmer och datastrukturer (PDF) . Oberon version med korrigeringar och auktoriserade modifieringar. s. 114–118.

externa länkar

• Weisstein, Eric W. "Queens Problem" . MathWorld .
• queens-cpm på GitHub Eight Queens Puzzle i Turbo Pascal för CP/M
• eight-queens.py på GitHub Eight Queens Puzzle en rad lösning i Python
• Lösningar i mer än 100 olika programmeringsspråk (på Rosetta Code )