Kahdeksan kuningattaren ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. tammikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Kahdeksan kuningattaren ongelma on hyvin tunnettu kombinatorinen ongelma nappuloiden järjestämisessä shakkilaudalla . Alkusana: "Järjestä 8 kuningatarta tavalliselle 64-soluiselle shakkilaudalle niin, että kukaan heistä ei ole toisen hyökkäyksen kohteena . " Ymmärretään, että kuningatar voittaa kaikki pystysuorat, vaakasuorat ja molemmat diagonaalit sijaitsevat solut.

Ongelman yleistys on asettaa kuningattaret samalla tavalla mielivaltaiseen suorakaiteen muotoiseen kenttään, erityisesti neliön muotoiseen kenttään, jonka sivu on . $n$

Sanamuoto

Tarkkaan matemaattisesti ongelma voidaan muotoilla useilla tavoilla, esimerkiksi seuraavasti: "Täytä matriisi nolilla ja ykkösillä siten , että matriisin kaikkien elementtien summa on 8, kun taas matriisin summa on 8. matriisin minkään sarakkeen, rivin tai diagonaalirivin elementit eivät ylitä yhtä." ${\näyttötyyli 8\kertaa 8}$

Ongelman ratkaisijalle asetettu lopullinen tavoite voidaan muotoilla useilla tavoilla:

Rakenna mikä tahansa ratkaisu ongelmaan.
Todista analyyttisesti, että ratkaisu on olemassa .
Määritä ratkaisujen lukumäärä.
Rakenna kaikki mahdolliset ratkaisut.
Kirjoita tietokoneohjelma, joka löytää kaikki mahdolliset ratkaisut ongelmaan. Yksi tyypillisistä laskenta-algoritmien ohjelmoinnin tehtävistä .

Joskus ongelman ilmaisu edellyttää, että etsitään tapoja järjestää kuningattaret solutaululle (huomaa, että ongelmaan ei ole ratkaisua). $N$ $N \ kertaa N$ ${\näyttötyyli 1<N<4}$

Ratkaisun ominaisuudet

Mahdollisten 8 kuningattaren järjestelyjen kokonaismäärä 64-soluisella laudalla on ( yhdistelmäkaava ) . Mahdollisia ongelman ehdot täyttäviä järjestelyjä on yhteensä 92. Näiden 92 järjestelyn joukko on jaettu 12 osajoukkoon (11 osajoukkoa 8 järjestelystä kussakin ja yksi neljästä jäljellä olevasta), joissa kussakin kaikki järjestelyt ovat saatu toisistaan symmetriamuunnoksilla: heijastukset pysty- ja vaaka-akseleilta, heijastukset laudan lävistäjästä ja kierrokset 90, 180 ja 270 astetta. $4\,426\,165\,368={\dfrac {64!}{8!\,(64-8)!}}$

Nykyaikaiset tietokoneet mahdollistavat jo ongelman ratkaisemisen (jotta tahansa tai kaikki ratkaisut) luettelemalla tyhjentävästi kaikki mahdolliset järjestelyvaihtoehdot, mutta tällaista ratkaisua pidetään yleensä virheellisenä: ongelman ratkaisijan on löydettävä algoritmi, joka vähentäisi merkittävästi luettelon määrää. . On esimerkiksi selvää, että yhdellä vaaka- tai pystytaululla ei voi olla enempää kuin yksi kuningatar, joten ratkaisualgoritmin ei pitäisi aluksi sisällyttää hakuun paikkoja, joissa kaksi kuningatarta on samalla vaaka- tai pystysuunnassa. Jopa tällainen yksinkertainen sääntö voi merkittävästi vähentää mahdollisten sijaintien määrää: 4 426 165 368 sijasta . Luomalla permutaatioita, jotka ovat ratkaisuja kahdeksan tornin ongelmaan, ja tarkistamalla sitten hyökkäykset diagonaaleja pitkin, voimme vähentää mahdollisten järjestelyjen määrää vain . Jos paikkoja luotaessa otetaan huomioon myös diagonaalinen hyökkäysehto, niin laskentanopeus kasvaa suuruusluokkaa ja syklien lukumäärä ongelman ratkaisemiseksi on 4022. $16\,777\,216=8^{8}$ $40\,320=8!$

Yksi tyypillisistä ongelmanratkaisualgoritmeista on backtracking : ensimmäinen kuningatar asetetaan ensimmäiselle vaakatasolle, sitten jokainen seuraava sijoitetaan seuraavalle, jotta aiemmin perustetut kuningattaret eivät lyödä sitä. Jos seuraavassa asetusvaiheessa ei ole vapaita kenttiä, tapahtuu askel taaksepäin - aiemmin asetettu kuningatar järjestetään uudelleen.

Muistiinpanot

Linkit

Tehtävän fraktaaliratkaisu levyille, jos N=(a1)•(a2)•…•(an), missä a1 ≥ 4 ja a2,…,an > 4 (A. Ermakov, 2011) $N \ kertaa N$
Yleinen n queens -menetelmä java-toteutuksen kanssa