Patnáctka

Základní postavení Patnáctka (známa též jako Loydova patnáctka podle jejího popularizátora Sama Loyda) je hlavolam, ve kterém musí hráč přesouváním kamenů uvnitř malé čtvercové krabičky tyto kameny seřadit.

Hlavolam sestává z krabičky, do které se vejde 4×4 čtvercových kamenů, místo jednoho kamene je však volné místo, které umožňuje kameny v krabičce posouvat. Na začátku jsou kameny zamíchány, cílem hry je seřadit je podle na nich napsaných čísel či jiného označení.

Kromě základní verze 4×4 existují také verze o jiné velikosti, např. jednodušší verze 3×3 (někdy označovaná jako Lišák).

Existence řešení

+more8'>Příklad pozice nemožné vyřešit V hlavolamu existují pozice, ze kterých není možné se dovolenými tahy (tzn. bez vyjmutí kamenů z krabičky) dostat do cílové pozice. Sam Loyd nabídnul odměnu $1000 tomu, kdo jako první nabídne řešení jedné z těchto pozic (viz obrázek vlevo), což vyvolalo ohromný zájem o tuto hru (na čemž Loyd vydělal jmění). Tato odměna samozřejmě nikdy nemohla být vyplacena (což Loyd věděl).

Při podrobnější analýze hry se dá snadno prokázat, že existují právě dvě skupiny pozic, které na sebe nelze vzájemně převést povolenými tahy (jedna skupina obsahuje cílovou pozici, druhá skupina obsahuje např. výše uvedenou neřešitelnou pozici, která se od cílové liší výměnou právě dvou kamenů). +more K důkazu stačí uvědomit si, že parita součtu počtu inverzí v permutaci kamenů s číslem řádku, na kterém je volné místo, je invariantem úlohy, při platných tazích se nemění (při posuvu vodorovně se počet inverzí ani číslo řádku volného místa nemění vůbec, při svislých tazích se číslo řádku změní o jedna a počet inverzí se změní o liché číslo). To znamená, že stavový prostor úlohy obsahuje dvě třídy ekvivalence, které v grafu tvoří dvě oddělené komponenty. V požadovaném cílovém stavu je počet inverzí nula a prázdné pole je na čtvrtém řádku, 0 + 4 = 4, což je sudé číslo, takže řešitelné jsou jen ty pozice, které mají počet inverzí plus číslo řádku prázdného místa sudé (zatímco v uvedeném rozestavení je počet inverzí jedna a prázdné pole je stále na čtvrtém řádku, což dává lichý součet a pozice proto není řešitelná).

Hledání řešení

Patnáctka je typickou ukázkou úlohy řešitelné heuristickým algoritmem. Nejběžnější heuristická ohodnocení používaná pro tuto úlohou jsou počet špatně umístěných kamenů či součet manhattanských vzdáleností kamenů od svých cílových pozic. +more Obě metriky jsou přípustné (nikdy nepodceňují kvalitu pozice), což pro některé algoritmy (např. A*) zaručuje nalezení nejlepšího řešení.

Při zobecnění úlohy na hlavolam N×N je hledání nějakého řešení snadné, hledání nejlepšího řešení je však NP-těžká úloha.

Externí odkazy

[url=http://mathworld. wolfram. +morecom/15Puzzle. html]Patnáctka na encyklopedii MathWorld[/url] (anglicky) * [url=http://www. cut-the-knot. org/pythagoras/fifteen. shtml]Sam Loyd's fifteen[/url] - vysvětlení a Java applet (anglicky).

Kategorie:Hlavolamy Kategorie:NP-úplné problémy