Problemet med åtta drottningar

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 januari 2022; kontroller kräver 2 redigeringar .

Problemet med åtta damer  är ett välkänt kombinatoriskt problem för att arrangera pjäser på ett schackbräde . Initial formulering: "Arrangera 8 damer på ett standard 64-cells schackbräde så att ingen av dem attackeras av en annan . " Det är underförstått att drottningen slår alla celler som ligger längs vertikalerna, horisontalerna och båda diagonalerna.

En generalisering av problemet är att placera damerna på samma sätt på ett godtyckligt rektangulärt fält, i synnerhet ett kvadratiskt med sida .

Formulering

Strikt matematiskt kan problemet formuleras på flera sätt, till exempel på följande sätt: ”Fyll matrisen med nollor och ettor på ett sådant sätt att summan av alla element i matrisen är lika med 8, medan summan av elementen i någon kolumn, rad eller diagonal rad i matrisen inte överstiger en."

Det slutliga målet för lösaren av problemet kan formuleras på flera sätt:

Ibland kräver förklaringen av problemet att man hittar sätt att ordna damerna på cellens styrelse (observera att problemet inte har någon lösning).

Funktioner i lösningen

Det totala antalet möjliga arrangemang av 8 drottningar på en 64 -cellstavla är ( kombinationsformel ). Det totala antalet möjliga arrangemang som uppfyller villkoren för problemet är 92. Uppsättningen av dessa 92 arrangemang är uppdelad i 12 delmängder (11 delmängder av 8 arrangemang vardera och en av de fyra återstående), i var och en av vilka alla arrangemang är erhållna från varandra genom symmetritransformationer: reflektioner från vertikala och horisontella axlar, reflektioner från tavlans diagonaler och rotationer med 90, 180 och 270 grader.

Moderna datorer tillåter redan att lösa problemet (att hitta någon eller alla lösningar) genom att uttömmande räkna upp alla möjliga arrangemangsalternativ, men en sådan lösning anses vanligtvis vara felaktig: lösaren av problemet måste hitta en algoritm som avsevärt skulle minska mängden uppräkning . Till exempel är det uppenbart att det inte kan finnas mer än en dam på en horisontell eller vertikal bräda, så lösningsalgoritmen bör initialt inte inkludera i sökningen de positioner där två damer är på samma horisontella eller vertikala. Även en sådan enkel regel kan avsevärt minska antalet möjliga platser: istället för 4 426 165 368 . Genom att generera permutationer som är lösningar på problemet med åtta torn, och sedan kontrollera attackerna längs diagonalerna, kan vi minska antalet möjliga arrangemang till bara . Om, vid generering av positioner, även det diagonala attackförhållandet beaktas, ökar räknehastigheten med en storleksordning och antalet cykler för att lösa problemet kommer att vara 4022.

En av de typiska algoritmerna för att lösa problemet är användningen av backtracking : den första drottningen placeras på den första horisontella, sedan placeras varje nästa på nästa så att den inte slås av de tidigare etablerade drottningarna. Om det i nästa steg av inställningen inte finns några lediga fält, sker ett steg tillbaka - den tidigare inställda drottningen omarrangeras.

Anteckningar

Länkar