Problemet med de otte dronninger
Problemet med de otte dronninger går ud på at sætte otte dronninger på et skakbræt, uden at to af dem angriber hinanden. Skakkomponisten Max Bezzel offentliggjorde det i 1848, og det er blevet det klassiske første eksempel på backtracking-søgning.
En skakopgave fra 1848
Max Bezzel, en tysk skakkomponist, stillede opgaven i et skakblad i Berlin i 1848. Franz Nauck offentliggjorde alle 92 løsninger i 1850 og stillede det samme spørgsmål for større brætter. Carl Friedrich Gauss fulgte opgaven med interesse og drøftede den i sine breve.
Én dronning pr. række og kolonne
Otte dronninger, der ikke angriber hinanden, skal stå i otte forskellige rækker og otte forskellige kolonner. En løsning er altså en omrokering af tallene 1 til 8, en permutation, med én ekstra regel: To dronninger må ikke dele en diagonal. Af de 40.320 permutationer er det kun 92, der består.
Backtracking
Backtracking bygger en løsning op én del ad gangen og går tilbage, så snart den løber ind i en blindgyde. For dronningerne: Sæt en dronning på det første sikre felt i den næste række, og når en række ikke har noget sikkert felt, så gå tilbage til rækken ovenover, og flyt den dronning videre. I 1972 brugte Edsger Dijkstra opgaven til at forklare struktureret programmering med netop denne søgning.
Symmetri
Drej brættet en kvart omgang, eller spejl det, og en løsning forbliver en løsning. Det giver op til otte udgaver af hver løsning. De 92 løsninger falder i 12 sådanne familier: elleve med 8 medlemmer og én med kun 4, fordi den løsning ser ens ud efter en halv omgang.
Problemet med n dronninger
På et n×n-bræt er spørgsmålet det samme med n dronninger. Der er løsninger for alle n fra 4 og op, og antallet vokser hurtigt: 2 for 4×4, 92 for 8×8 og 14.200 for 12×12. Der kendes ingen formel for antallet; rekordværdierne kommer fra store computersøgninger.
Prøv det i PictorX
Åbn Otte dronninger, og klik på et felt for at placere en dronning; klik på det igen for at fjerne den. Vis angreb sætter en prik på de felter, dine dronninger angriber, og røde dronninger angriber hinanden. Løs kører backtracking-søgningen ét trin ad gangen og beholder de dronninger, du har placeret. Næste løsning går gennem alle løsninger i rækkefølge, og Størrelse ændrer brættet fra 4×4 til 12×12.
Ofte stillede spørgsmål
Hvem opfandt problemet med de otte dronninger?
Max Bezzel, en tysk skakkomponist, i 1848. Franz Nauck offentliggjorde det første komplette sæt løsninger i 1850.
Hvor mange løsninger er der?
92 på det almindelige bræt. Hvis rotationer og spejlinger tælles som én, er der 12.
Hvorfor har 6×6-brættet så få løsninger?
Det har kun 4, alle fra én og samme familie. Det mindre 5×5-bræt har 10. Større brætter har flere og flere: 40 på 7×7 og 92 på 8×8.
Uploader PictorX noget?
Nej. Brættet tegnes på et lærred i din browser. Gem henter et PNG, og Rediger åbner billedet i PictorX-editoren.
Relaterede værktøjer
Otte dronninger
Placer otte dronninger på et skakbræt, så ingen af dem angriber en anden. Prøv selv, se backtracking-søgningen finde en løsning trin for trin, og gå alle 92 løsninger igennem.
Springertur
Lad en springer hoppe til hvert felt på brættet præcis én gang. Spil selv med Warnsdorff-tips, eller se Løs fuldføre en åben eller lukket tur. Gem ruten som PNG.
Springerturen
Springerturens historie og matematik: Euler og Warnsdorff, åbne og lukkede ture, hvorfor brætter af ulige størrelse ikke har nogen lukket tur, og hvordan en computer finder en.
Tårnet i Hanoi
Flyt et tårn af skiver mellem tre pinde i din browser. Én skive ad gangen, aldrig en større på en mindre. Den korteste løsning er 2ⁿ − 1 træk.
Tårnet i Hanoi
Tårnet i Hanoi: tre pinde, én skive ad gangen og aldrig en større på en mindre. Den korteste løsning er 2ⁿ−1 træk. Édouard Lucas præsenterede puslespillet i 1883.
Langtons Myre
Kør Langtons myre i din browser. Se symmetri, kaos og motorvejen på 104 trin, og prøv derefter flerfarvede regler, flere myrer, et sekskantnet og turmitter.
Er du klar til at prøve?
Åbn PictorX i din browser - ingen installation, ingen kreditkort kræves for at starte.
Prøv Otte dronninger