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ärjestyksessä tahansa, ja tehtävänä on saada ne numerojärjestykseen siirtämällä (liu’uttamalla) aina yksi laatta kerrallaan viereisestä ruudusta kulloinkin tyhjänä olevaan ruutuun.
Ratkaistavuus
[muokkaa | muokkaa wikitekstiä]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 permutaatioiden pariteettiin 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 ratkaistavissa vain, jos permutaation pariteetti on parillinen. Täten mahdolliset alkuasetelmat voidaan jakaa kahteen ekvivalenssiluokkaan, 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]
Käytännössä yksinkertaisemmin voidaan tietyn asetelman ratkaistavuus selvittää laskemalla inversioiden lukumäärä. Inversioksi lasketaan jokainen kahden numerolaatan 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 tilapä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] Teoreettisesti tehtävä on mistä tahansa ratkaistavissa olevasta alkuasetelmasta 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
[muokkaa | muokkaa wikitekstiä]Pelin keksi tiettävästi vuonna 1874 Noyes Palmer Champan,[9] joka toimi postimestarina Canastotassa New Yorkin osavaltiossa. 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 kuurojenkoulun (American School for the Deaf) oppilaat alkoivat valmistaa peliä teollisesti, ja joulukuussa 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 ratkaisemisesta rahapalkinnon.[9]
Helmikuussa 1880 pelistä tuli Yhdysvalloissa 1880 suoranainen villitys, samoin Kanadassa saman vuoden maaliskuussa ja laajalti Euroopassakin huhtikuussa. Sitä pelattiin rautatieasemien odotushuoneissa, junissa, lounastauoilla 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". Patenttihakemus kuitenkin hylättiin, todennäköisesti siksi, joska peli muistutti liiaksi Ernest U. Kinseyn keksimää peliä, jolle oli 20. elokuuta 1878 myönnetty yhdysvaltalainen patentti US 207124.[9]
Sam Loyd
[muokkaa | muokkaa wikitekstiä]Sam Loyd väitti vuodesta 1891 kuolemaansa saakka 1911 keksineensä tämän pelin, esimerkiksi vuonna 1914 julkaistussa teoksessa Cyclopedia of Puzzles, jossa hän kuvasi sitä seuraavasti: "Ongelmapelien 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 alkuperä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
[muokkaa | muokkaa wikitekstiä]- ↑ a b c d Mitä-Missä-Milloin – Ongelmakirja, s. 133–134. Otava, 1969.
- ↑ a b Notes on the "15" puzzle. American Journal of Mathematics, 1879, nro 2, s. 397–404. The Johns Hopkins University Press. doi:10.2307/2369492. ISSN 0002-9327. JSTOR:2369492.
- ↑ A modern treatment of the 15 puzzle. The American Mathematical Monthly, 1999, nro 106, s. 793–799. doi:10.2307/2589612. ISSN 0002-9890. MR:1732661.
- ↑ 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.
- ↑ 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.
- ↑ The (n2−1)-puzzle and related relocation problems. Journal of Symbolic Computation, 1990, nro 10. doi:10.1016. ISSN 2.
- ↑ The parallel search bench ZRAM and its applications. Annals of Operations Research, 1999, nro 90, s. 45–63. Artikkelin verkkoversio.
- ↑ The Fifteen Puzzle can be solved in 43 "moves" Domain of the Cube Forum. Arkistoitu 13.12.2013. Viitattu 5.12.2013.
- ↑ a b c d Jerry Slocum, Dic Sonneveld: The 15 Puzzle. Määritä julkaisija! ISBN 1-890980-15-3.
- ↑ Cyclopedia of Puzzles, s. 235. Määritä julkaisija! Teoksen verkkoversio.
- ↑ Barry R. Clarke: Puzzles for Pleasure, s. 10-12. Cambridge University Press, 1994. ISBN 0-521-46634-2.
- ↑ 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. doi:10.1007/3-540-44914-0_3. Teoksen verkkoversio.
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]- 15-peli verkossa
- 15-pelin historia
- 15-pelin ratkaisu
- Tarvittavien siirtojen vähimmäismäärä 15-pelin m × n -ruutuisessa muunnoksessa
- Fifteen Puzzle Optimal Solver (Arkistoitu – Internet Archive)
- Koodaa itse 15-peli. Suomenkieliset ohjeet 15-pelin ohjelmoimiseksi Lazarus-ohjelmankehitysympäristössä.