Ogled vira Igra 15

[[Slika:15-puzzle.svg|thumb|Rešena uganka]]
'''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<ref>''The 15 Puzzle'', Jerry Slocum & Dic Sonneveld. ISBN 1-890980-15-3</ref> naj bi igro »izumil« ameriški poštar Noyes Palmer Chapman) in za rešitev ponudil nagrado 1000 [[Ameriški dolar|dolarjev]], kar je bilo tistikrat vredno precej več kot današnjih 1000. To je povzročilo, da se je igra razširila po [[Združene države Amerike|ZDA]] in Evropi.

[[Slika:15-puzzle-loyd.svg|thumb|left|Začetni položaj nerešljive uganke]]

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 [[parnost]]jo. 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 [[hevristika|hevristike]]. Običajna hevristika za ta problem vključuje število ploščic, ki so na napačnem položaju in vsota [[Manhattan]]skih 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 <math>k</math> potezah, je [[NP-poln problem|NP-poln]].<ref>{{Navedi revijo|url = http://www.aaai.org/Papers/AAAI/1986/AAAI86-027.pdf|title = Finding a Shortest Solution for the NxN Extension of the 15-puzzle is Intractable|last=M. Warmuth|first = D. Ratner|date = 1986|journal = AAAI-86 Proceedings|accessdate = 18 marec 2015}}</ref>

== Sklici ==

{{sklici|1}}

== Zunanje povezave ==

* [http://fifteen.logical-games.org Fifteen Puzzle online] {{Webarchive|url=https://web.archive.org/web/20171008173118/http://fifteen.logical-games.org/ |date=2017-10-08 }}
* http://www.cut-the-knot.com/pythagoras/fifteen.html {{Webarchive|url=https://web.archive.org/web/20080704122055/http://cut-the-knot.com/pythagoras/fifteen.html |date=2008-07-04 }} 
* http://www-poleia.lip6.fr/~drogoul/projects/eco/npuzzle.html {{Webarchive|url=https://web.archive.org/web/20050910071904/http://www-poleia.lip6.fr/~drogoul/projects/eco/npuzzle.html |date=2005-09-10 }}

[[Kategorija:Razvedrilna matematika in uganke]]
[[Kategorija:NP-polni problemi]]
[[Kategorija:Uganke]]