Kahdeksan kuningattaren ongelma

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.[1] Ongelmaa ovat tutkineet useat tunnetut matemaatikot, muun muassa Gauss, Lucas ja Pólya, ja se on myös usein käytetty algoritmiikan esimerkkitapaus.[2]

abcdefgh
8
Chessboard480.svg
f8 valkea kuningatar
d7 valkea kuningatar
g6 valkea kuningatar
a5 valkea kuningatar
h4 valkea kuningatar
b3 valkea kuningatar
e2 valkea kuningatar
c1 valkea kuningatar
8
77
66
55
44
33
22
11
abcdefgh
Eräs kahdeksan kuningattaren ongelman 92 ratkaisusta.

HistoriaMuokkaa

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.[3][4] Vuonna 1874 James W. L. Glaisher todisti, ettei ratkaisuja ole enempää kuin nämä 92.[5] 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.[6]

Algoritmiikan esimerkkiongelmaMuokkaa

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.[7][8][9]

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.[2] 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ä.[10]

Ratkaisujen olemassaolo ja konstruktioMuokkaa

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).[11] Todistuksen sille, että ratkaisuja on aina olemassa, esitti ilmeisesti ensimmäisenä E. Pauls vuonna 1874. Yleisiä ratkaisuja on sittemmin esitetty useitakin.[10]

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.[1][10]

  • Jos  , asetetaan kuningattaret paikkoihin   sekä  , kaikilla  .
  • Jos  , asetetaan kuningattaret paikkoihin   sekä  , kaikilla  .
  • Jos n on pariton, otetaan   kuningattaren ratkaisu ja lisätään kuningatar paikkaan  .

Kuvassa konstruktiot tapauksissa  . Tällä konstruktiolla voidaan kuningattaret asettaa helposti mielivaltaisen suurelle laudalle, esimerkiksi 1 000 kuningatarta 1 000 × 1 000 ruudun laudalle.

Ratkaisujen lukumääräMuokkaa

Erilaisten ratkaisujen lukumäärän laskeminen on vaikeampi ongelma, eikä lukumäärälle tunneta yksinkertaista kaavaa.[12] 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).[9] 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.[13]

Nykyään ratkaisujen lukumäärä tunnetaan 27 kuningattaren ongelmaan saakka, johon on noin   ratkaisua, tai   jos toisistaan kiertämällä ja peilaamalla saatavia ratkaisuja pidetään samoina.[14][15] 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.[12][13]

Ratkaisujen lukumäärät n:n eri arvoilla on lueteltu OEIS-tietokannassa.[14][15]

MuunnelmiaMuokkaa

abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Nauckin täydentämisongelma (1850). Voiko laudalle asettaa kuusi kuningatarta lisää niin, etteivät kuningattaret uhkaa toisiaan?[16][17]

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.[11][16][17] 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.[18][11][19]

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  . Ratkaisujen lukumäärä tunnetaan tapaukseen   asti, jossa ratkaisuja on noin   kappaletta.[10][12][20]

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   permutaatio; ratkaisujen lukumäärä on siten   eli n:n kertoma.[10][12]

LähteetMuokkaa

  1. a b Hoffman, E. J. & Loessi, J. C. & Moore, R. C.: Constructions for the Solution of the m Queens Problem. Mathematics Magazine, 1969, 42. vsk, s. 66–72.
  2. a b Erbas, C. & Sarkeshik, S., & Tanik, M. M.: Different perspectives of the N-queens problem (s. 99–108) Proceedings of the 1992 ACM annual conference on Communications. 1992. Viitattu 2.4.2020.
  3. Campbell, Paul J.: Gauss and the eight queens problem: A study in miniature of the propagation of historical error. Historia Mathematica, 1977, 4. vsk, s. 397–404.
  4. Gardner, Martin: Knots and Borromean Rings, Rep-Tiles, and Eight Queens. Cambridge University Press, 2014. ISBN 9780521756136. Google Books -esikatselu (viitattu 2.4.2020).
  5. Rivin, Igor & Vardi, Ilan & Zimmerman, Paul: The n-Queens Problem. The American Mathematical Monthly, 1994, s. 629–639.
  6. Ball, W. W. Rouse: Mathematical Recreations & Essays, s. 166. 11th edition. New York: Macmillan, 1939/1947.
  7. Dijkstra, Edsger W.: A Short Introduction to the Art of Programming. Eindhoven: Technische Hogeschool Eindhoven, 1971. Teoksen verkkoversio (viitattu 2.4.2020).
  8. Neapolitan, Richard E.: Foundations of Algorithms, s. 204–220. Jones & Bartlett Publishers, 2015. ISBN 9781284049206. Google Books -esikatselu (viitattu 2.4.2020).
  9. a b Laaksonen, Antti: Kisakoodarin käsikirja (Sivut 48–49) cs.helsinki.fi. 2018. Viitattu 2.4.2020.
  10. a b c d e Bell, Jordan & Stevens, Brett: A survey of known results and research areas for n-queens. Discrete Mathematics, 2009, 309. vsk, s. 1–31.
  11. a b c The 8-Queens Puzzle Clay Mathematics Institute. Viitattu 2.4.2020.
  12. a b c d Preußer, Thomas B. & Engelhardt, Matthias R.: Putting Queens in Carry Chains, N27. Journal of Signal Processing Systems, 2016, 88. vsk, s. 185–201.
  13. a b 27-Queens Puzzle: Massively Parellel Enumeration and Solution Counting The Q27 Project. Viitattu 3.4.2020.
  14. a b A000170 Number of ways of placing n nonattacking queens on an n X n board. The On-Line Encyclopedia of Integer Sequences. The OEIS Foundation. Viitattu 2.4.2020.
  15. a b A002562 Number of ways of placing n nonattacking queens on n X n board (symmetric solutions count only once). The On-Line Encyclopedia of Integer Sequences. The OEIS Foundation. Viitattu 2.4.2020.
  16. a b Gent, Ian P. & Jefferson, Christopher & Nightingale, Peter: Complexity of n-Queens Completion. Journal of Artificial Intelligence Research, 2017, 59. vsk, s. 815–848.
  17. a b ”Dr. Nauck”: Schach: Eine in das Gebiet der Mathematik fallende Aufgabe von Herrn Dr. Nauck in Schleusingen. Illustrirte Zeitung, 1.6.1850, 14. vsk, nro 361, s. 352. Artikkelin verkkoversio Viitattu 15.5.2020.
  18. Gent, Ian: Why the world’s toughest maths problems are much harder than a chess puzzle, and well worth US$1m theconversation.com. 6.9.2017. Viitattu 5.4.2020.
  19. Kehitä ohjelma "Tuhannen kuningattaren ongelmaan" ja ansaitse 800 000 euroa – ihminen voi ratkaista sen, mutta tekoäly ei MTV Uutiset. 1.9.2017 (päivitetty 2.9.2017). Viitattu 5.4.2020.
  20. A051906 Number of ways of placing n nonattacking queens on an n X n toroidal chessboard. The On-Line Encyclopedia of Integer Sequences. The OEIS Foundation. Viitattu 2.4.2020.