Kahdeksan kuningattaren ongelma

Malline:Shakkilauta Kahdeksan kuningattaren ongelma on klassinen kombinatoriikan ongelma, jossa tehtävänä on asettaa kahdeksan kuningatarta shakkilaudalle siten, etteivät mitkään kaksi kuningatarta uhkaa toisiaan; toisin sanoen mitkään kaksi kuningatarta eivät saa olla samalla vaakarivillä, pystylinjalla tai diagonaalilla. Yleisemmässä versiossa on n kuningatarta asetettava n×n ruudun laudalle. Tämä on aina mahdollista, jos n = 1 tai n ≥ 4, mutta ei onnistu jos n on 2 tai 3. Ongelmaa ovat tutkineet useat tunnetut matemaatikot, muun muassa Gauss, Lucas ja Pólya, ja se on myös usein käytetty algoritmiikan esimerkkitapaus.

Historia

Vuonna 1848 nimimerkki ”Schachfreund” eli saksalainen shakkitehtävien laatija Max Bezzel julkaisi kahdeksan kuningattaren ongelman Schachzeitung-lehdessä. Kaksi ratkaisua löydettiin jo vuonna 1849. Ongelma levisi laajempaan tietoisuuteen, kun Franz Nauck esitti sen Illustrirte Zeitungissa 1. kesäkuuta 1850. Carl Friedrich Gauss kiinnostui ongelmasta, löysi 72 ratkaisua ja totesi, että ratkaisuja voi olla enemmänkin. Syyskuussa 1850 Nauck esitti ongelmaan 12 perusratkaisua, joista kiertämällä ja peilaamalla saadaan yhteensä 92 ratkaisua. Vuonna 1874 James W. L. Glaisher todisti, ettei ratkaisuja ole enempää kuin nämä 92. Glaisherin menetelmä perustuu rekursioon, jossa n kuningattaren ratkaisuista n×n ruudun laudalla pystytään päättelemään n+1 kuningattaren ratkaisut (n+1)×(n+1) ruudun laudalla.

Algoritmiikan esimerkkiongelma

Kahdeksan kuningattaren ongelmaa käytetään usein havainnollistamaan erilaisia algoritmiikan tekniikoita, kuten peruuttavaa hakua (engl. backtracking). Edsger Dijkstra käytti sitä tässä tarkoituksessa vuonna 1971. Peruuttava haku voi toimia esimerkiksi siten, että asetetaan ensimmäinen kuningatar ensimmäiselle riville, vuoron perään kuhunkin kahdeksasta mahdollisesta ruudusta. Kussakin tapauksessa kokeillaan seuraavaksi mahdollisuudet asettaa toinen kuningatar toiselle riville jne.

Ongelmaan on sovellettu lukuisia algoritmiikan menetelmiä, kuten hajota ja hallitse -menetelmiä, rajoiteohjelmointia (CSP), kokonaislukuoptimointia, satunnaisalgoritmeja, symmetrian eliminointia ja neuroverkkoja. Algoritmin tavoitteena voi olla joko löytää ainakin joitakin ratkaisuja, tai luetella ne kaikki. Toisaalta pelkästään siihen, että löydetään jokin ratkaisu, ei tarvita lainkaan algoritmiikkaa eikä hakua, sillä mille tahansa n ≥ 4 voidaan eräs ratkaisu muodostaa yksinkertaisella menetelmällä.

Ratkaisujen olemassaolo ja konstruktio

Kahdeksan kuningattaren ongelma on klassinen ongelma, jonka kaikki 92 ratkaisua on tunnettu pitkään. Myös n kuningattaren ongelma on ratkaistu siinä mielessä, että ratkaisuja tunnetaan kaikilla n:n arvoilla (kun n ≥ 4). Todistuksen sille, että ratkaisuja on aina olemassa, esitti ilmeisesti ensimmäisenä E. Pauls vuonna 1874. Yleisiä ratkaisuja on sittemmin esitetty useitakin.

Seuraava yksinkertainen konstruktio on Hoffmanin, Loessin ja Mooren vuonna 1969 esittämä. Konstruktio jakautuu tapauksiin sen mukaan, mikä on jakojäännös kun n jaetaan kuudella.

• Jos $\text{mod}(n,6)=0\text{ tai }4$, asetetaan kuningattaret paikkoihin $(j,2j)$ sekä $(n/2+j,2j-1)$, kaikilla $1\le j\le n/2$.
• Jos $\text{mod}(n,6)=2$, asetetaan kuningattaret paikkoihin $(j,1+\text{mod}(2(j-1)+n/2-1,n))$ sekä $(n+j-1,n-\text{mod}(2(j-1)+n/2-1,n))$, kaikilla $1\le j\le n/2$.
• Jos n on pariton, otetaan $n-1$ kuningattaren ratkaisu ja lisätään kuningatar paikkaan $(n,n)$.

Kuvassa konstruktiot tapauksissa $n=4,5,6,7$. Tällä konstruktiolla voidaan kuningattaret asettaa helposti mielivaltaisen suurelle laudalle, esimerkiksi 1 000 kuningatarta 1 000 × 1 000 ruudun laudalle.

Ratkaisujen lukumäärä

Erilaisten ratkaisujen lukumäärän laskeminen on vaikeampi ongelma, eikä lukumäärälle tunneta yksinkertaista kaavaa. Pienissä tapauksissa ratkaisut voidaan luetella peruuttavalla haulla ja sitä kautta laskea niiden lukumäärä. 16 kuningattaren ratkaisujen (14 772 512 kpl) luetteleminen noin 10-rivisellä C-ohjelmalla vie noin minuutin nykyaikaisella tietokoneella (vuonna 2018). 25 kuningattaren ratkaisut laskettiin vuonna 2005 hajautetulla laskennalla tavallisilla toimistotietokoneilla. 26 kuningattaren ratkaisut laskettiin vuonna 2009 ohjelmoitavilla FPGA-logiikkapiireillä Queens@TUD-projektissa noin yhdeksän kuukauden aikana.

Nykyään ratkaisujen lukumäärä tunnetaan 27 kuningattaren ongelmaan saakka, johon on noin $2,349\cdot 10^{17}$ ratkaisua, tai $2,936\cdot 10^{16}$ jos toisistaan kiertämällä ja peilaamalla saatavia ratkaisuja pidetään samoina. Ratkaisut laskettiin hajautetusti usealla tuhannella FPGA-logiikkapiirillä. Laskentaa varten ongelma pilkottiin noin kahteen miljardiin osaongelmaan. Yksittäisen osaongelman ratkaisemiseen FPGA-piirillä meni keskimäärin vajaa minuutti, joten laskentaa tehtiin yhteensä yli 3 500 vuotta. Hajautettu laskenta kesti noin vuoden: se alkoi syyskuussa 2015 ja valmistui syyskuussa 2016.

Ratkaisujen lukumäärät n:n eri arvoilla on lueteltu OEIS-tietokannassa.

Muunnelmia

Malline:Shakkilauta Kahdeksan tai n:n kuningattaren ongelmasta tunnetaan useita muunnelmia. Täydentämisongelmassa (engl. n-Queens Completion) laudalle on valmiiksi asetettu joukko kuningattaria, ja on ratkaistava, voiko asetelman täydentää niin, että laudalla on n kuningatarta, jotka eivät uhkaa toisiaan. Nauck esitti vuonna 1850 kahdeksan kuningattaren täydentämisongelman tapauksen, jossa kaksi kuningatarta oli asetettu ruutuihin B4 ja D5. Gent, Jefferson ja Nightingale osoittivat n kuningattaren täydentämisongelman NP-täydelliseksi vuonna 2017. Joissakin uutisissa tämä tulos selitettiin virheellisesti niin, että kahdeksan tai n kuningattaren ongelman ratkaisemisesta saisi Clay-instituutin miljoonan dollarin Millennium-palkinnon. Gent ja Clay-instituutti joutuivat julkaisemaan selvennyksen, että näiden ongelmien ratkaisuja tunnetaan ennestään. Millennium-palkinto on luvassa P=NP-ongelman ratkaisemisesta, esimerkiksi sen selvittämisestä, onko n kuningattaren täydentämisongelma mahdollista ratkaista polynomisessa ajassa.

Pólya tutki toroidaalista kuningatarongelmaa, jossa shakkilaudan reunaan osuva diagonaali jatkuu vastakkaisesta reunasta, ikään kuin lauta olisi taivutettu rullalle ja vastakkaiset reunat liimattu yhteen. Toisin sanoen laudan ruutujen koordinaatteihin sovelletaan modulaarista aritmetiikkaa. Tämä tekee ongelman matemaattisesti yksinkertaisemmaksi ja symmetrisemmäksi, ja vähentää ratkaisujen lukumäärää huomattavasti. Toroidaaliseen ongelmaan on olemassa ratkaisuja ainoastaan silloin, kun $\text{mod}(n,6)=1\text{ tai }5$. Ratkaisujen lukumäärä tunnetaan tapaukseen $n=31$ asti, jossa ratkaisuja on noin $1,340\cdot 10^{13}$ kappaletta.

Muita muunnelmia ovat muun muassa korkeampiulotteiset laudat sekä kuningattaren korvaaminen jollakin muulla shakkinappulalla. Tornien tapauksessa ratkaisu on yksinkertainen: n×n ruudun laudalle voi asettaa n tornia siten, että kukin torni on omalla rivillään ja tornien linjat ovat mikä tahansa joukon $\{1,2,\dots ,n\}$ permutaatio; ratkaisujen lukumäärä on siten $n!$ eli n:n kertoma.