Igra 15

Igra petnajst oziroma uganka petnajst je premičnica, ki vsebuje 15 oštevilčenih ploščic in eno prazno mesto na mreži 4×4. Obstajajo tudi druge različice, na primer igra osem na mreži 3×3, igra N ali pa povsem posplošena igra na mreži m×n. Cilj igre je s premikanjem praznega mesta doseči končni položaj ploščic.

Igro naj bi leta 1870 izumil ameriški ugankar Sam Loyd (po novejših raziskavah^[1] naj bi igro »izumil« ameriški poštar Noyes Palmer Chapman) in za rešitev ponudil nagrado 1000 dolarjev, kar je bilo tistikrat vredno precej več kot današnjih 1000. To je povzročilo, da se je igra razširila po ZDA in Evropi.

Matematični premislek pokaže, da vsi položaji (vseh je 16! = 20.922.789.888.000) pri igri 15 razpadejo v dve ločeni množici položajev z različno parnostjo. V eni množici lahko dosežemo poljuben položaj iz te množice, izkaže pa se, da nikakor ni mogoče doseči nobenega položaja iz druge množice. V originalni uganki sta položaja iz različnih množic, zato igra ni rešljiva, kar je Loyd vedel že ob zastavi uganke.

Igra 15 je klasični problem za modeliranje s pomočjo hevristike. Običajna hevristika za ta problem vključuje število ploščic, ki so na napačnem položaju in vsota Manhattanskih razdalj ploščic do ciljnega položaja. Odločitveni problem, ki za dano konfiguracijo igre N sprašuje, ali je igro moč rešiti v kvečjemu ${\displaystyle k}$ potezah, je NP-poln.^[2]

• Fifteen Puzzle online Arhivirano 2017-10-08 na Wayback Machine.
• http://www.cut-the-knot.com/pythagoras/fifteen.html Arhivirano 2008-07-04 na Wayback Machine.
• http://www-poleia.lip6.fr/~drogoul/projects/eco/npuzzle.html Arhivirano 2005-09-10 na Wayback Machine.