Problemet med otte dronninger
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. januar 2022; checks kræver 2 redigeringer .Problemet med otte dronninger er et velkendt kombinatorisk problem til at arrangere brikker på et skakbræt . Indledende formulering: "Arranger 8 dronninger på et standard 64-cellers skakbræt , så ingen af dem er under angreb af en anden . " Det er underforstået, at dronningen slår alle cellerne langs de lodrette, vandrette og begge diagonaler.
En generalisering af problemet er at placere dronningerne på samme måde på et vilkårligt rektangulært felt, især et firkantet med side .
Ordlyd
Strengt matematisk kan problemet formuleres på flere måder, for eksempel som følger: ”Fyld matricen med nuller og ettaller på en sådan måde, at summen af alle elementer i matricen er lig med 8, mens summen af elementerne i en hvilken som helst kolonne, række eller diagonal række i matrixen ikke overstiger én."
Det endelige mål for problemløseren kan formuleres på flere måder:
- Konstruer en hvilken som helst løsning på problemet.
- Bevis analytisk, at der findes en løsning .
- Bestem antallet af løsninger.
- Byg alle mulige løsninger.
- Skriv et computerprogram, der finder alle mulige løsninger på et problem. En af de typiske opgaver for programmering af optællingsalgoritmer .
Nogle gange kræver erklæringen om problemet, at man finder måder at arrangere dronningerne på cellebrættet (bemærk, at problemet ikke har nogen løsning).
Funktioner af løsningen
Det samlede antal mulige arrangementer af 8 dronninger på et 64-cellers bord er (kombinationsformel ) . Det samlede antal mulige arrangementer, der opfylder betingelserne for problemet, er 92. Sættet af disse 92 arrangementer er opdelt i 12 undersæt (11 undersæt af 8 arrangementer hver og en af de fire resterende), i hver af dem er alle arrangementer opnået fra hinanden ved symmetritransformationer: refleksioner fra lodrette og vandrette akser, refleksioner fra brættets diagonaler og rotationer med 90, 180 og 270 grader.
Moderne computere gør det allerede muligt at løse problemet (finde en hvilken som helst eller alle løsninger) ved udtømmende at opregne alle mulige arrangementsmuligheder, men en sådan løsning anses normalt for at være forkert: Problemløseren skal finde en algoritme, der vil reducere mængden af opregning betydeligt . For eksempel er det indlysende, at der ikke kan være mere end én dronning på et vandret eller lodret bræt, så løsningsalgoritmen bør i første omgang ikke inkludere i søgningen de positioner, hvor to dronninger er på samme vandrette eller lodrette. Selv en sådan simpel regel kan reducere antallet af mulige steder væsentligt: i stedet for 4 426 165 368 . Ved at generere permutationer, der er løsninger på problemet med otte tårne, og derefter kontrollere angrebene langs diagonalerne, kan vi reducere antallet af mulige arrangementer til kun . Hvis der ved generering af positioner også tages højde for den diagonale angrebstilstand, så stiger tællehastigheden med en størrelsesorden, og antallet af cyklusser til løsning af problemet vil være 4022.
En af de typiske algoritmer til at løse problemet er brugen af backtracking : den første dronning placeres på den første vandrette, derefter placeres hver næste på den næste, så den ikke bliver slået af de tidligere etablerede dronninger. Hvis der på næste trin af indstillingen ikke er nogen frie felter, sker der et skridt tilbage - den tidligere indstillede dronning omarrangeres.
Noter
Links
- Fraktal løsning af problemet for tavler, hvis N=(a1)•(a2)•...•(an), hvor a1 ≥ 4 og a2,...,an > 4 (A. Ermakov, 2011)
- Generisk n queens-metode med java-implementering