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. Woolssey Johnson ja William E. Story osoittivat tämän vuonna 1897 permu­taatioiden pari­teettiin perustuvalla päättelyllä.
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. 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.
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.
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ä, 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ä. Teo­reetti­sesti tehtävä on mistä tahansa ratkaistavissa olevasta alku­asetelmasta lähtien ratkaistavissa 80 yhden laatan siirrolla tai 43 siirrolla, jos tapaus, jossa laatta työntää edellään yhtä tai useampaa muuta laattaa, lasketaan yhdeksi siirroksi.