Åtte dronninger problem

Åtte dronninger-problemet er et tidsfordriv som går ut på å sette åtte dronninger på sjakkbrettet uten å true hverandre. Det ble foreslått av den tyske sjakkspilleren Max Bezzel i 1848 . [ 1 ] [ 2 ] I sjakkspillet truer dronningen brikkene som er i samme rad, kolonne eller diagonal. Spillet med 8 damer består av å plassere åtte damer på et sjakkbrett uten at de truer hverandre. For å løse dette problemet kan et tilbakesporingsskjema brukes .

Historikk

Problemet ble opprinnelig foreslått i 1848 av sjakkspilleren Max Bezzel . [ 1 ] [ 2 ] [ 3 ] I årevis har mange matematikere , inkludert Carl Friedich Gauss , jobbet med det og generalisert det til n-dronninger. De første løsningene ble tilbudt av Franz Nauck i 1850. [ 1 ] [ 2 ] [ 4 ] Nauck henvendte seg også til n-queens (på et nxn-brett av vilkårlig størrelse). I 1874 foreslo S. Günther en metode for å finne løsningene ved å bruke determinanter , og JWL Glaisher redefinerte sin tilnærming. [ 3 ] [ 5 ]

Edsger Dijkstra brukte dette problemet i 1972 for å illustrere kraften til såkalt strukturert programmering . Han publiserte en svært detaljert beskrivelse av utviklingen av tilbakesporingsalgoritmen , " depth-first ". [ 6 ] [ 7 ]

Dette puslespillet dukket opp i det populære 90-tallets dataspill kalt " The 7th Guest ".

Problemerklæring

Siden hver dronning kan true alle dronninger i samme rad, må hver dronning plasseres i en annen rad. Vi kan representere de 8 dronningene med en vektor[1-8], med tanke på at hver indeks av vektoren representerer en rad og verdien en kolonne. Dermed ville hver dronning være i posisjon (i, v[i]) for i = 1-8.

Vektoren betyr at dronning 1 er i rad 1, kolonne 3; dronning 2 i rad 2, kolonne 1; dronning 3 i rad 3, kolonne 6; dronning 4 i rad 4, kolonne 2; osv... Som du kan se er denne løsningen feil siden dronning 3 og dronning 6 ville vært i samme kolonne. Derfor vil vektoren tilsvare en permutasjon av de første åtte heltallene . $(3,1,6,2,8,6,4,7)$

Vi har løst problemet med radene og kolonnene, men hva med diagonalene? For posisjoner på samme synkende diagonal, er det sant at de har samme verdi ; mens for posisjoner på samme stigende diagonal, er det sant at de har samme verdi . Således, hvis vi har to dronninger plassert i posisjoner og så er de på samme diagonal hvis og bare hvis : $rad-kolonne$ $rad+kolonne$ $(i, j)$ $(k,l)$

$ij=kl$ enten $i+j=k+l$

$jl=ik$ enten $jl=ki$

Med alle disse hensynene i betraktning kan vi bruke ordningen med tilbakevirkende kraft for å plassere alle åtte dronninger på en virkelig effektiv måte. For å gjøre dette omformulerer vi problemet som et søkeproblem i et tre. Vi sier at en vektor med heltall mellom 1 og 8 er -lovende, for , hvis ingen av dronningene plassert i posisjonene truer noen av de andre. Løsningene på problemet vårt tilsvarer de vektorene som er 8-lovende. $V_{1\dots k}$ $k$ $0\leq k\leq 8$ $k$ $(1,V_{1}),(2,V_{2}),\dots ,(k,V_{k})$

Algoritmeetablering

La være settet med -lovende vektorer, , være den rettede grafen slik at hvis og bare hvis det finnes et heltall , forutsatt at $N$ $k$ $0\leq k\leq 8$ $G=(N,A)\,$ $(U,V)\in A$ $k$ $0\leq k\leq 8$

$ELLER$ er -lovende $k$
$v$ er -lovende $(k+1)$
$U_{i}=V_{i}$ for alle $i\in \{1,\dots ,k\}$

Denne grafen er et tre . Roten er den tomme vektoren som tilsvarer . bladene er enten løsninger ( ), eller blindveier ( ). Løsninger på problemet med åtte dronninger kan fås ved å utforske dette treet. Vi genererer imidlertid ikke eksplisitt treet for å utforske senere. Nodene genereres og forlates i løpet av utforskningen ved hjelp av en kryssing i dybden. $k=0$ $k=8$ $k<8$

Du må bestemme om en vektor er -lovende, vel vitende om at den er en forlengelse av en -lovende vektor. Vi trenger bare å sjekke den siste dronningen som skal legges til. Dette kan akselereres hvis vi til hver lovende node knytter kolonnesettet, den med positive diagonaler (ved 45 grader) og den med negative diagonaler (ved 135 grader) kontrollert av dronningene som allerede er plassert. $k$ $(k-1)$

Algoritmebeskrivelse

Nedenfor er algoritmen som løser problemet vårt, som er en global vektor. For å skrive ut alle løsninger er den første samtalen . $g_{1\dots 8}$ $\mathrm {queens} (0,\emptyset ,\emptyset ,\emptyset )$

prosess $\mathrm {queens} (k,col,diag45,diag135)\,$

// er -lovende//

g_{1\dots k}

k

// //

col=\{g_{i}\mid 1\leq i\leq k\}

// //

diag45=\{g_{i}-i+1\midt 1\leq i\leq k\}

// //

diag135=\{g_{i}+i-1\midt 1\leq i\leq k\}

hvis da //en vektor -lovende er en løsning//

k=8\,

8

å skrive

sun\,

hvis ikke //utforsk sun -lovende utvidelser //

(k+1)

å selv gjøre

j\leftarrow 1

8\,

ja og og da

j\notin col

jk\notin diag45

j+k\notin diag135

g_{k+1}\leftarrow j

// er -lovende//

g_{1\dots k+1}

(k+1)

\mathrm {queens} \left(k+1,col\cup \{j\},diag45\cup \{jk\},diag135\cup \{j+k\}\right)

Algoritmen sjekker først om , hvis dette er sant, viser det seg at vi har foran oss en 8-lovende vektor, som indikerer at den tilfredsstiller alle begrensningene, og gir opphav til en løsning. Hvis den er forskjellig fra 8, utforsker algoritmen de -lovende utvidelsene, for den lager en løkke, som går fra 1 til 8, på grunn av antall dronninger. Denne løkken sjekker om dronningene plassert på brettet er i sjakk. Hvis de ikke kommer i kontroll, utføres en rekursjon der vi øker (se etter -lovende) og legger til den nye raden, kolonnen og diagonalene til begrensningssettet. Når vi utfører gjentakelsen, har vi lagt til en ny dronning til solvektoren, som ikke er i sjakk med noen av de forrige. I tillegg har vi økt settet med restriksjoner ved å legge til en ny forbudt rad, kolonne og diagonaler (en positiv og en negativ). $k=8$ $k$ $(k+1)$ $k$ $(k+1)$

Implementering

Nedenfor er en mulig implementering av algoritmen ovenfor i C++.

#include <iostream> #include <sstream> #include <cstdio> #inkluder <vektor> #include <algoritme> #define NREINS 8 // brettdimensjoner og antall damer som bruker navneområde std ; vektor < int > sol ; int solnummer = 1 ; inline bool inneholder ( const vektor < int >& v , const int val ) { return finn ( v . begynne (), v . slutt (), val ) != v . slutt (); } void queens ( int k , vektor < int > col , vektor < int > diag45 , vektor < int > diag135 ) { if ( k == NREINS ) { printf ( "%3d:" , sun_number ++ ); for ( int j = 0 ; j < NREINS ; j ++ ) cout << " (" << j + 1 << "," << sun [ j ] << ")" ; cout << endl ; } ellers { for ( int j = 1 ; j <= NREINS ; j ++ ) hvis ( ! inneholder ( col , j ) && ! inneholder ( diag45 , j - k ) && ! inneholder ( diag135 , j + k ) ) { g [ k ] = j ; col . push_back ( j ); diag45 . push_back ( j - k ); diag135 . push_back ( j + k ); dronninger ( k + 1 , col , diag45 , diag135 ); col . pop_back (); diag45 . pop_back (); diag135 . pop_back (); } } } int main () { cout << "LØSNINGER PÅ PROBLEMET MED " << NREINS << " QUEENS" << endl ; sol . endre størrelse ( NREINS ); queens ( 0 , vektor < int > (), vektor < int > (), vektor < int > ()); returner 0 ; }

The n queens problem

Problemet med de åtte dronningene kan på en generell måte angis som et problem for dronningene. Problemet ville være å plassere dronninger på et sjakkbrett på en slik måte at ingen av dronningene angriper andre. $n$ $n$ $n\ ganger n$

Hans analyse og løsning er isomorf i forhold til de åtte dronningene.

27x27 brettet er det største som noen gang er nummerert. [ 8 ]

Antall løsninger

n	forskjellig	alle løsninger:
1	1	1
to	0	0
3	0	0
4	1	to
5	to	10
6	1	4
7	6	40
8	12	92
9	46	352
10	92	724
elleve	341	2.680
12	1.787	14.200
1. 3	9.233	73.712
14	45.752	365.596
femten	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
tjue	4.878.666.808	39.029.188.884
tjueen	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

Skjulte symmetrier

I tillegg til symmetriene knyttet til plasseringen av dronningene og deres refleksjon eller rotasjon, er det en annen ikke så åpenbar en som forbinder løsningene mellom et sidebrett (n) og det neste sidebrettet (n+1). Med utgangspunkt i det komplette settet med løsninger for n sideceller, teller gangene hver celle vises i dem, resulterer det:

for n:6

for n:7

for n:8

for n:9

0	1	1	1	1	0
1	0	1	1	0	1
1	1	0	0	1	1
1	1	0	0	1	1
1	0	1	1	0	1
0	1	1	1	1	0

4	7	6	6	6	7	4
7	4	6	6	6	4	7
6	6	6	4	6	6	6
6	6	4	8	4	6	6
6	6	6	4	6	6	6
7	4	6	6	6	4	7
4	7	6	6	6	7	4

4	8	16	18	18	16	8	4
8	16	14	8	8	14	16	8
16	14	4	12	12	4	14	16
18	8	12	8	8	12	8	18
18	8	12	8	8	12	8	18
16	14	4	12	12	4	14	16
8	16	14	8	8	14	16	8
4	8	16	18	18	16	8	4

28	30	47	44	54	44	47	30	28
30	32	44	48	44	48	44	32	30
47	44	28	38	38	38	28	44	47
44	48	38	36	tjue	36	38	48	44
54	44	38	tjue	40	tjue	38	44	54
44	48	38	36	tjue	36	38	48	44
47	44	28	38	38	38	28	44	47
30	32	44	48	44	48	44	32	30
28	30	47	44	54	44	47	30	28

Når løsningssettet er riktig for n, holder fullstendig symmetri, både vertikalt og horisontalt. Denne symmetrien kan oppstå med et ufullstendig sett med løsninger. Summen av hver rad og hver kolonne, hvis løsningssettet er komplett, gir imidlertid det totale antallet mulige løsninger:

for n:6

for n:7

for n:8

for n:9

0	1	1	1	1	0	:4
1	0	1	1	0	1	:4
1	1	0	0	1	1	:4
1	1	0	0	1	1	:4
1	0	1	1	0	1	:4
0	1	1	1	1	0	:4
:4	:4	:4	:4	:4	:4	:0

s = Løsninger = 4

d = Diagonal sum = 0

s - d. = [ 4]

4	7	6	6	6	7	4	:40
7	4	6	6	6	4	7	:40
6	6	6	4	6	6	6	:40
6	6	4	8	4	6	6	:40
6	6	6	4	6	6	6	:40
7	4	6	6	6	4	7	:40
[4]	7	6	6	6	7	4	:40
:40	:40	:40	:40	:40	:40	:40	:36

s = Løsninger = 40

d = diagonal sum = 36

s - d = [4]

4	8	16	18	18	16	8	4	:92
8	16	14	8	8	14	16	8	:92
16	14	4	12	12	4	14	16	:92
18	8	12	8	8	12	8	18	:92
18	8	12	8	8	12	8	18	:92
16	14	4	12	12	4	14	16	:92
8	16	14	8	8	14	16	8	:92
[4]	8	16	18	18	16	8	4	:92
:92	:92	:92	:92	:92	:92	:92	:92	:64

s = Løsninger = 92

d = Diagonal sum = 64

s - d = [28]

28	30	47	44	54	44	47	30	28	:352
30	32	44	48	44	48	44	32	30	:352
47	44	28	38	38	38	28	44	47	:352
44	48	38	36	tjue	36	38	48	44	:352
54	44	38	tjue	40	tjue	38	44	54	:352
44	48	38	36	tjue	36	38	48	44	:352
47	44	28	38	38	38	28	44	47	:352
30	32	44	48	44	48	44	32	30	:352
[28]	30	47	44	54	44	47	30	28	:352
:352	:352	:352	:352	:352	:352	:352	:352	:352	:288

s = Løsninger = 352

d = Diagonal sum = 288

s - d = [64]

Til slutt faller subtraksjonen mellom løsningene til et brett og summen av den tilsvarende diagonalen sammen med verdien som vises i hjørnene på neste brett. Resulterer i en forbindelse mellom brettet av n ruter og en av n+1 ruter. For komplett løsningssett:

borde:	Sumlinje og mulige løsninger	diagonal sum	tavlehjørner n+1 x n+1 trekke fra legg til linje - legg til diagonal
6x6	4	0	Bretthjørner 7 x 7 = 4
7x7	40	36	Bretthjørner 8 x 8 = 4
8x8	92	64	Bretthjørner 9 x 9 = 28
9x9	352	288	Bretthjørner 10 x 10 = 64
10x10	724	628	Bretthjørner 11 x 11 = 96
11x11	2680	2180	Bretthjørner 12 x 12 = 500
12x12	14200	11440	Bretthjørner 13 x 13 = 2760
13x13	73712	61820	Bretthjørner 14 x 14 = 11892
14x14	365596	296080	Bretthjørner 15 x 15 = 69516
15x15	...

Ved å finne forholdet mellom verdiene som resulterer i hjørnene og det totale antallet løsninger på hvert brett eller dets størrelse, kan de riktige resultatene bli funnet for en hvilken som helst verdi på n.

Løsninger på problemet med åtte dronninger

Problemet med de åtte dronningene har 92 løsninger, hvorav 12 er vesentlig forskjellige , det vil si at de 92 eksisterende løsningene kan oppnås fra rotasjons- og refleksjonssymmetrioperasjoner av de 12 unike løsningene, som er vist nedenfor:

Problemet med å finne alle løsningene på 8-dronninger-problemet kan være ganske beregningsmessig dyrt, siden det er 4.426.165.368 (dvs. 64 C 8 ) mulige arrangementer av åtte damer på et 8x8-brett, men bare 92 løsninger. Det er mulig å bruke snarveier som reduserer beregningskrav eller tommelfingerregler som unngår brute force beregningsteknikker . For eksempel, ved å bruke en enkel regel som begrenser hver dronning til en enkelt kolonne (eller rad), selv om den fortsatt anses som brute force, er det mulig å redusere antall muligheter til 16 777 216 (dvs. 8 8 ) mulige kombinasjoner. Permutasjonsgenerering reduserer mulighetene ytterligere til bare 40 320 (dvs. 8! ), som deretter sjekkes for diagonale angrep.

Det er mange beregningsmessige løsninger på problemet med de 8 dronningene, som benytter seg av rekursive anrop, på et hvilket som helst programmeringsspråk, noe som viser den høye populariteten til dette problemet i verden av dataprogrammering.

Det nysgjerrige nummeret Š

Hvis vi nummererer kvadratene på et sjakkbrett av en hvilken som helst størrelse (nxn) med de naturlige tallene, fra venstre til høyre og fra topp til bunn, finner vi det merkelige tilfellet med tallet Š , som alltid er en konstant for et gitt brett på nxn sider og forteller oss hvor mye som vil være summen av rutene der de n dronningene kan plasseres for alle løsningene til nevnte brettet. Tallet Š er gitt av formelen:

Š =

(n^{3}+n)/2

Nedenfor er eksemplet på de to løsningene av et 4 x 4 brett (merket i de svarte rutene), det vil si n = 4

Š(4) =

(4^{3}+4)/2

Beregner for den første løsningen Š1 = 2+8+9+15 = 34

Beregner for den andre løsningen Š2 = 3+5+12+14 = 34

Nedenfor er eksemplet på de ti løsningene av et 5 x 5 brett (merket i de svarte rutene), det vil si n = 5

Š(5) = = 65

(5^{3}+5)/2

Beregner for den første løsningen Š1 = 1+8+15+17+24 = 65

Beregner for den andre løsningen Š2 = 1+9+12+20+23 = 65

Beregner for den tredje løsningen Š3 = 2+9+11+18+25 = 65

Beregner for den fjerde løsningen Š4 = 2+10+13+16+24 = 65

Beregner for den femte løsningen Š5 = 3+6+14+17+25 = 65

Beregner for den sjette løsningen Š6 = 3+10+12+19+21 = 65

Beregner for den syvende løsningen Š7 = 4+6+13+20+22 = 65

Beregner for den åttende løsningen Š8 = 4+7+15+18+21 = 65

Beregner for den niende løsningen Š9 = 5+7+14+16+23 = 65

Beregner for den tiende løsningen Š10 = 5+8+11+19+22 = 65

Dette tallet gjelder imidlertid for ethvert sett med celler så lenge det ikke er gjentatte kolonner eller rader. For eksempel: Šdiagonal = 1 + 7 + 13 +19 +25 = 65

Deretter blir tallet Š gitt opp til brettet n = 10 (algoritmer sjekket beregningsmessig for alle løsninger opp til 11 x 11-tavlen som har 2680 løsninger).

Sekvensen til Š(n) er {34, 65, 111, 175, 260, ...}, den ble oppdaget av Paul Muljadi i 2005 (sekvens A006003 i OEIS).

Referanser

↑ a b c Alain Campbell White (1963) [Original publikasjon 1913 av Whitehead og Miller]. Sam Lloyd og hans sjakkproblemer . Dover Publikasjoner . s. 101. ISBN 0486209288 .
^ abc Haynes , Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998). Dominans i grafer: Bind 2: Avanserte emner . New York: Marcel Decker. s. 142. ISBN 0824700341 . OCLC 38201061 .
↑ a b Rivin, Igor; Vardi, Ilan; Zimmerman, Paul (1994). " N -queens-problemet". American Mathematical Monthly (7. utgave) 101 : 629-639. JSTOR 2974691 . doi : 10.2307/2974691 .
↑ Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998). Grunnleggende om dominans i grafer . New York: Marcel Decker. s. 295. ISBN 0824700333 . OCLC 37903553 .
↑ Ball, W. W. Rouse (1914). Matematiske rekreasjoner og essays (Sjette utgave). London: Macmillan. s. 113-122.
^ Dijkstra, Edsger W. (august 1971). En kort introduksjon til kunsten å programmere . Eindhoven: Technische Hogeschool. s. 84-91. OCLC 3474242 . EWD316 .
↑ Dijkstra, Edsger W.; Dahl, Ole-Johan ; Hoare, BIL (1972). Strukturert programmering . London: Academic Press . s. 72-82. ISBN 0122005503 .
↑ Preußer, Thomas B. (26. juni 2019), 27-Queens Puzzle: Massively Parellel Enumeration and Solution Counting: preusser/q27 , hentet 21. september 2019 .

Gomez Campos, Luis Ernesto (2004). Over hele linja: Matematikken til sjakkproblemer . Princeton: Princeton University Press . ISBN 0-691-11503-6 .
Brassard, Gilles; Bratley, Paul (1997). «Graf-utforskning». Grunnleggende om algoritmer . Madrid: Prentice Hall . ISBN 84-89660-00-X .

Se også

Eksterne lenker

Weisstein, Eric W. "Queens Problem" . I Weisstein, Eric W, red. MathWorld (på engelsk) . WolframResearch .
Løsninger på 8-dronninger-problemet
Walter Kosters N-Queens-side
Durango Bills N-Queens-side
Online guide til begrensningsprogrammering

Lenker til løsninger

Interaktiv løsning på 8 dronninger-problemet i VB.NET og C#
Generell metode n queens med implementering i java
N-Queens løsere i mange programmeringsspråk
Finn din egen løsning
J Somers N-Queen-kode
Atari BASIC
Genetiske algoritmer
Java
Standard ML
Quirkasaurus' 8 Queens Solution
LISP-løsning for N-Queens-problem
Javascript-løsning for 8-Queens-problem
De åtte dronningene. Løsning
Løsning på problemet med de åtte dronningene (i Institutt for anvendt matematikk ved Universitetet i Valencia ).
N-Queens-problemet
Q27-prosjektet