Åttadamersproblemet
Åttadamersproblemet går ut på att placera åtta damer på ett schackbräde utan att två av dem angriper varandra. Schackkompositören Max Bezzel publicerade det 1848, och det har blivit det klassiska första exemplet på sökning med backtracking.
Ett schackproblem från 1848
Max Bezzel, en tysk schackkompositör, ställde problemet i en schacktidskrift i Berlin 1848. Franz Nauck publicerade alla 92 lösningar 1850 och ställde samma fråga för större bräden. Carl Friedrich Gauss följde problemet med intresse och diskuterade det i sina brev.
En dam per rad och kolumn
Åtta damer som inte angriper varandra måste stå på åtta olika rader och i åtta olika kolumner. En lösning är alltså en omkastning av talen 1 till 8, en permutation, med en extra regel: inga två damer får dela en diagonal. Av de 40 320 permutationerna klarar sig bara 92.
Backtracking
Backtracking bygger upp en lösning en bit i taget och backar så fort den hamnar i en återvändsgränd. För damerna: sätt en dam på den första säkra rutan på nästa rad, och när en rad inte har någon säker ruta, gå tillbaka till raden ovanför och flytta den damen vidare. År 1972 använde Edsger Dijkstra problemet för att förklara strukturerad programmering med just den här sökningen.
Symmetri
Vrid brädet ett kvarts varv, eller spegla det, så förblir en lösning en lösning. Det ger upp till åtta versioner av varje lösning. De 92 lösningarna faller i 12 sådana familjer: elva med 8 medlemmar och en med bara 4, eftersom den lösningen ser likadan ut efter ett halvt varv.
Problemet med n damer
På ett n×n-bräde är frågan densamma med n damer. Det finns lösningar för varje n från 4 och uppåt, och antalet växer snabbt: 2 för 4×4, 92 för 8×8 och 14 200 för 12×12. Ingen formel för antalet är känd; rekordvärdena kommer från stora datorsökningar.
Prova i PictorX
Öppna Åtta damer och klicka på en ruta för att placera en dam; klicka igen för att ta bort den. Visa angrepp sätter en prick på rutorna som dina damer angriper, och röda damer angriper varandra. Lös kör sökningen med backtracking ett steg i taget och behåller de damer du har placerat. Nästa lösning går igenom alla lösningar i ordning, och Storlek ändrar brädet från 4×4 till 12×12.
Ofta ställda frågor
Vem uppfann åttadamersproblemet?
Max Bezzel, en tysk schackkompositör, 1848. Franz Nauck publicerade den första fullständiga uppsättningen lösningar 1850.
Hur många lösningar finns det?
92 på det vanliga brädet. Om rotationer och speglingar räknas som en är det 12.
Varför har 6×6-brädet så få lösningar?
Det har bara 4, alla från en enda familj. Det mindre 5×5-brädet har 10. Större bräden har fler och fler: 40 på 7×7 och 92 på 8×8.
Laddar PictorX upp något?
Nej. Brädet ritas på en canvas i webbläsaren. Spara laddar ner en PNG, och Redigera öppnar bilden i PictorX-redigeraren.
Relaterade verktyg
Åtta damer
Placera åtta damer på ett schackbräde så att ingen angriper en annan. Prova själv, se sökningen med backtracking hitta en lösning steg för steg och gå igenom alla 92 lösningar.
Springartur
Låt en springare hoppa till varje ruta på brädet exakt en gång. Spela själv med Warnsdorff-tips, eller se Lös slutföra en öppen eller sluten tur. Spara vägen som PNG.
Springarturen
Springarturens historia och matematik: Euler och Warnsdorff, öppna och slutna turer, varför udda bräden saknar sluten tur och hur en dator hittar en.
Tornen i Hanoi
Flytta ett torn av skivor mellan tre pinnar i webbläsaren. En skiva i taget, aldrig en större på en mindre. Den kortaste lösningen är 2ⁿ − 1 drag.
Tornen i Hanoi
Tornen i Hanoi: tre pinnar, en skiva i taget och aldrig en större på en mindre. Den kortaste lösningen är 2ⁿ−1 drag. Édouard Lucas presenterade pusslet 1883.
Langtons Myra
Kör Langtons myra i webbläsaren. Se symmetri, kaos och motorvägen på 104 steg, och prova sedan flerfärgade regler, flera myror, ett sexkantigt rutnät och turmiter.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova Åtta damer