15-peli

15-peli (engl. Fifteen Puzzle tai Boss Puzzle, ransk. Jeu de Taquin)[1] on ongelmapeli, jossa on tavallisimmin 15 numeroitua laattaa sijoitettuna neliömäiseen, 4×4 = 16 ruutua sisältävän kehykseen, jossa täten on aina yksi ruutu tyhjänä. Pelistä on myös versioita, joissa kehyksen koko on toinen, esimerkiksi 8-peli, jossa on 3×3 = 9 ruutua ja kahdeksan numerolaattaa. Numerolaatat voivat olla missä järjes­tyksessä tahansa, ja tehtävänä on saada ne numero­järjestykseen siirtämällä (liu’uttamalla) aina yksi laatta kerrallaan viereisestä ruudusta kulloinkin tyhjänä olevaan ruutuun.

Ratkaistu 15-peli

Ratkaistavuus

Jokainen mahdollinen tapa, jolla laatat voidaan sijoittaa kehykseen, vastaa yhtä 16-alkioisen joukon permutaatiota. Tällaisia tapoja on kaikkiaan 16! = 20 922 789 888 000 (yli 20 biljoonaa), mutta vain puolet näistä asetelmista on sellaisia, että tehtävä on ratkaistavissa, tehtiinpä kuinka monta siirtoa tahansa.[1] Woolssey Johnson ja William E. Story osoittivat tämän vuonna 1897 permu­taatioiden pari­teettiin perustuvalla päättelyllä.[2]

Aina kun yhtä laattaa siirretään, muuttuu permutaation pariteetti parillisesta parittomaksi tai päinvastoin, mutta samalla myös tyhjän ruudun sijainti vasemmasta yläruudusta laskettuna pysty- ja vaakarivejä pitkin muuttuu yhden yksikön verran. Tästä seuraa, että jos permutaation pariteetin ja mainitun etäisyyden summa oli ennen siirtoa parillinen, se on parillinen sen jälkeenkin, ja jos se oli pariton, se myös pysyy parittomana. Erityisesti jos tyhjä ruutu on oikeassa alakulmassa, tehtävä on ratkaista­vissa vain, jos permutaation pariteetti on parillinen. Täten mahdolliset alkuasetelmat voidaan jakaa kahteen ekvivalenssi­luokkaan, joista toiseen kuuluvat ratkaistavissa olevat asetelmat, toiseen taas ne, jotka eivät ole ratkaistavissa.

Johnson ja Story osoittivat myös kääntäen, että jokainen asetelma, jonka pariteetti on parillinen, on ratkaistavissa.[2] Tämä osoitettiin matemaattisella induktiolla lähtien 2×2 laattaa sisältä­västä muunnelmasta. Vuonna 1999 Archer esitti asialle toisenlaisen todistuksen, joka perustuu Hamiltonin polun avulla määriteltyyn ekvivalenssiluokkaan.[3]

Esimerkki asetelmasta, joka ei ole ratkaistavissa

Käytännössä yksin­kertaisemmin voidaan tietyn asetelman ratkaistavuus selvittää laskemalla inversioiden lukumäärä. Inversioksi lasketaan jokainen kahden numero­laatan pari, jossa suurempi luku on ennen pienempää. Mikäli tyhjä ruutu on alimmalla rivillä, asetelma on ratkaistavissa, jos ja vain jos inversioiden lukumäärä on parillinen.[1]

Esimerkiksi oheisessa kuviossa on

  • luku 5 ennen lukuja 1, 2, 3 ja 4; yhteensä 4 inversiota
  • luku 6 ennen lukuja 2, 3, ja 4; yhteensä 3 inversiota
  • luku 7 ennen lukuja 3 ja 4; yhteensä 2 inversiota
  • luku 8 ennen lukua 4; yhteensä 1 inversio
  • luku 9 ennen lukuja 1, 2, 3, 4, 5, 6, 7 ja 8; yhteensä 8 inversiota
  • luku 10 ennen lukuja 2, 3, 4, 6, 7 ja 8; yhteensä 6 inversiota
  • luku 11 ennen lukuja 3, 4, 7 ja 8; yhteensä 4 inversiota
  • luku 12 ennen lukuja 4 ja 8; yhteensä 2 inversiota
  • luku 13 ennen lukuja 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ja 12; yhteensä 12 inversiota
  • luku 14 ennen lukuja 2, 3, 4, 6, 7, 8, 10, 11 ja 12; yhteensä 9 inversiota
  • luku 15 ennen lukuja 3, 4, 7, 8, 11 ja 12; yhteensä 6 inversiota.

Kaikkiaan inversioita on siis tässä asetelmassa 4+3+2+1+8+6+4+2+12+9+6 = 57, joten asetelma ei ole ratkaistavissa.

Silloinkin kun asetelma on ratkaistavissa, tehtävä yleensä edellyttää, samoin kuin Rubikin kuutiossakin, että nekin laatat, jotka on jo saatu kohdalleen, joudutaan myöhemmin tila­päisesti siirtämään siitä pois. Tämä saattaa olla peliä ensimmäisen kerran kokeilevalle vaikea käsittää tai hyväksyä,[4] mutta kunhan tämä seikka on tullut selväksi, tehtävä on kohtalaisen helppo oppia ratkaisemaan. On kuitenkin osoitettu, että tehtävän lyhyimmän ratkaisun löytäminen on NP-vaikea tehtävä.[5][6] Teo­reetti­sesti tehtävä on mistä tahansa ratkaistavissa olevasta alku­asetelmasta lähtien ratkaistavissa 80 yhden laatan siirrolla[7] tai 43 siirrolla, jos tapaus, jossa laatta työntää edellään yhtä tai useampaa muuta laattaa, lasketaan yhdeksi siirroksi.[8]

Historia
Sam Loydin ratkaisematon 15-peli, jossa laatat 14 ja 15 oli vaihdettu keskenään.
Yhdysvaltalainen poliittinen pila­piirros republi­kaanien yrityksestä löytää sopiva presidentti­ehdokas vuonna 1880.

Pelin keksi tiettävästi vuonna 1874 Noyes Palmer Champan,[9] joka toimi postimestarina Canastotassa New Yorkin osa­valtiossa. Sen edeltäjänä oli 16 laatan peli, jossa laatat oli sijoitettava neljän laatan riveihin siten, että muodostui taikaneliö, jossa jokaisen rivin ja sarakkeen summa oli 34. Keksijän poika Frank vei pelistä kopion Syracuseen ja myöhemmin Hartfordiin Connecticutiin, jossa kuurojen­koulun (American School for the Deaf) oppilaat alkoivat valmistaa peliä teollisesti, ja joulu­kuussa 1879 se tuli myyntiin Hartfordissa sekä Bostonissa. Tammikuun lopulla 1880 peli sai osakseen suurta huomiota, kun hammaslääkäri Charles Devey Worcesterissa, Massachusettsissa lupasi tehtävän ratkai­sem­isesta rahapalkinnon.[9]

Helmikuussa 1880 pelistä tuli Yhdysvalloissa 1880 suoranainen villitys, samoin Kanadassa saman vuoden maalis­kuussa ja laajalti Euroopassakin huhtikuussa. Sitä pelattiin rauta­tie­asemien odotus­huoneissa, junissa, lounas­tauoilla ja jopa Britannian parlamentissa.[1] Heinäkuuhun mennessä villitys oli kuitenkin jo laantunut.

Noyes Chapman haki 21. helmikuuta 1880 patenttia pelille, josta hän käytti nimeä "Block Solitaire Puzzle". Patentti­hakemus kuitenkin hylättiin, toden­näköisesti siksi, joska peli muistutti liiaksi Ernest U. Kinseyn keksimää peliä, jolle oli 20. elokuuta 1878 myönnetty yhdys­valtalainen patentti US 207124.[9]

Sam Loyd
Sam Loydia esittävä piirros vuodelta 1914.

Sam Loyd väitti vuodesta 1891 kuolemaansa saakka 1911 keksineensä tämän pelin, esi­merkiksi vuonna 1914 julkaistussa teoksessa Cyclopedia of Puzzles, jossa hän kuvasi sitä seuraavasti: "Ongelma­pelien maan vanhemmat asukkaat muistavat, kuinka minä 1870-luvun alussa sain koko maailman hulluksi pienellä laatikolla, jossa oli siirrettäviä laattoja ja joka tuli tunnetuksi 14-15-pelinä."[10] Loydilla ei kuitenkaan ollut mitään tekemistä pelin keksimisen eikä sen alku­peräisen suosion kanssa, ja sitä paitsi peli tuli tunnetuksi vasta vuonna 1880, ei 1870-luvun alussa. Ensimmäisen artikkelinsa pelistä Loyd julkaisi vuonna 1886, ja vasta vuonna 1891 hän ensimmäisen kerran väitti keksineensä sen.[9][11] Sen sijaan Loydin ansiosta peli oli kyllä myöhemmin saanut uudelleen osakseen suurta huomiota, kun hän oli luvannut 1 000 dollarin palkinnon sille, joka pystyisi ratkaisemaan pelin sellaisesta lähtö­tilanteesta käsin, jossa laatat 14 ja 15 oli vaihdettu keskenään.[12] Tehtävä oli kuitenkin mahdoton suorittaa, kuten Johnson ja Story olivat jo kymmenen vuotta aiemmin osoittaneet, sillä se edellytti parittoman kombinaation muuttamista parilliseksi.

Lähteet
  1. Mitä-Missä-Milloin – Ongelmakirja, s. 133–134. Otava, 1969.
  2. Notes on the "15" puzzle. American Journal of Mathematics, 1879, nro 2, s. 397–404. The Johns Hopkins University Press.
  3. A modern treatment of the 15 puzzle. The American Mathematical Monthly, 1999, nro 106, s. 793–799.
  4. Metamagical Themas – The Magic Cube's cubies are twiddled by cubists and solved by cubemeisters. (Kirjoitus käsittelee varsinaisesti Rubikin kuutiota, mutta vertailun vuoksi sen alussa puhutaan jonkin verran myös 15-pelistä) Scientific American, 1981, nro 4.
  5. Daniel Ratner, Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. National Conference on Artificial Intelligence, 1986.
  6. The (n2−1)-puzzle and related relocation problems. Journal of Symbolic Computation, 1990, nro 10.
  7. The parallel search bench ZRAM and its applications. Annals of Operations Research, 1999, nro 90, s. 45–63. Artikkelin verkkoversio.
  8. The Fifteen Puzzle can be solved in 43 "moves" Domain of the Cube Forum.
  9. Jerry Slocum, Dic Sonneveld: The 15 Puzzle. {{{Julkaisija}}}, 2006. ISBN 1-890980-15-3.
  10. Cyclopedia of Puzzles, s. 235. {{{Julkaisija}}}. Teoksen verkkoversio.
  11. Barry R. Clarke: Puzzles for Pleasure, s. 10-12. Cambridge University Press, 1994. ISBN 0-521-46634-2.
  12. Richard E. Korf: ”Recent progress in the design and analysis of admissible heuristic functions”, SARA 2000. Abstraction, reformulation, and approximation: 4th international symposium, s. 45-55. Texas, USA: Springer, 2000. ISBN 978-3-540-67839-7. Teoksen verkkoversio.

    Aiheesta muualla
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.