b'\n_START_ARTICLE_\nIgra 15\n_START_PARAGRAPH_\nIgra petnajst oziroma uganka petnajst je premi\xc4\x8dnica, ki vsebuje 15 o\xc5\xa1tevil\xc4\x8denih plo\xc5\xa1\xc4\x8dic in eno prazno mesto na mre\xc5\xbei 4\xc3\x974. Obstajajo tudi druge razli\xc4\x8dice, na primer igra osem na mre\xc5\xbei 3\xc3\x973, igra N ali pa povsem posplo\xc5\xa1ena igra na mre\xc5\xbei m\xc3\x97n. Cilj igre je s premikanjem praznega mesta dose\xc4\x8di kon\xc4\x8dni polo\xc5\xbeaj plo\xc5\xa1\xc4\x8dic._NEWLINE_Igro naj bi leta 1870 izumil ameri\xc5\xa1ki ugankar Sam Loyd (po novej\xc5\xa1ih raziskavah naj bi igro\xc2\xa0\xc2\xbbizumil\xc2\xab\xc2\xa0ameri\xc5\xa1ki po\xc5\xa1tar Noyes Palmer Chapman) in za re\xc5\xa1itev ponudil nagrado 1000 dolarjev, kar je bilo tistikrat vredno precej ve\xc4\x8d kot dana\xc5\xa1njih 1000. To je povzro\xc4\x8dilo, da se je igra raz\xc5\xa1irila po ZDA in Evropi._NEWLINE_Matemati\xc4\x8dni premislek poka\xc5\xbee, da vsi polo\xc5\xbeaji (vseh je 16! = 20.922.789.888.000) pri igri 15 razpadejo v dve lo\xc4\x8deni mno\xc5\xbeici polo\xc5\xbeajev z razli\xc4\x8dno parnostjo. V eni mno\xc5\xbeici lahko dose\xc5\xbeemo poljuben polo\xc5\xbeaj iz te mno\xc5\xbeice, izka\xc5\xbee pa se, da nikakor ni mogo\xc4\x8de dose\xc4\x8di nobenega polo\xc5\xbeaja iz druge mno\xc5\xbeice. V originalni uganki sta polo\xc5\xbeaja iz razli\xc4\x8dnih mno\xc5\xbeic, zato igra ni re\xc5\xa1ljiva, kar je Loyd vedel \xc5\xbee ob zastavi uganke._NEWLINE_Igra 15 je klasi\xc4\x8dni problem za modeliranje s pomo\xc4\x8djo hevristike. Obi\xc4\x8dajna hevristika za ta problem vklju\xc4\x8duje \xc5\xa1tevilo plo\xc5\xa1\xc4\x8dic, ki so na napa\xc4\x8dnem polo\xc5\xbeaju in vsota Manhattanskih razdalj plo\xc5\xa1\xc4\x8dic do ciljnega polo\xc5\xbeaja. Odlo\xc4\x8ditveni problem, ki za dano konfiguracijo igre N spra\xc5\xa1uje, ali je igro mo\xc4\x8d re\xc5\xa1iti v kve\xc4\x8djemu k potezah, je NP-poln.'