Posuvné hlavolamy
Patnáctka, přístav plný lodí a velký čtverec
od prvního tahu po prohledávání a složitost
Na pozadí řeší počítač úlohy z banky 3D hry: zlatá loď musí vyplout ústím vpravo ve třetí řadě. Řešič prohledá do šířky všechny stavy úlohy a pak hraje vždy tah, který vede o krok blíž k cíli – tedy nejkratší řešení. Oranžově je loď, která se právě posunula; jméno techniky najdete v kapitolách 3 až 5, proč je řešení nejkratší, v kapitole 9.
Jak průvodce používat
Posuvný hlavolam je rámeček s kusy, které se nedají zvednout – jen posouvat po desce na volná místa. Patří sem patnáctka (a menší osmička), dopravní hlavolamy, ve kterých bloky jezdí jen po své délce a jeden z nich musí vyjet ven, a posuvné bloky různých tvarů jako tradiční čínský hlavolam s velkým čtvercem. Průvodce vede od pravidel a prvních technik – číst cestu od ústí, uvolnit ji, rozplést řetěz překážek, udělat krok zpět – přes paritu, která rozhodne, zda jde patnáctka vůbec složit, k prohledávání do šířky, heuristikám, složitosti a k tomu, jak počítač našel nejtěžší úlohy. Je pro hráče, kteří chtějí hrát s rozmyslem, pro rodiče a děti a pro studenty matematiky a informatiky, které zajímá, co je pod kapotou.
Tři patra každé kapitoly. Nahoře krátké vysvětlení a laboratoř nebo minihra, kde si věc vyzkoušíte klepáním. Pod ní dvě mise za XP. Dole rozbalovací teorie pro ty, kdo chtějí jít do hloubky: přesné definice, proč technika funguje, řešené příklady a procvičení s řešením. Teorie bývá o úroveň náročnější než úvod kapitoly. Barevná tečka v obsahu ukazuje úroveň. Postup se ukládá jen ve vašem prohlížeči.
Hned za úvodem najdete sekci Vyplutí z přístavu ve 3D: přístav s vodou, loděmi a majákem, pět obtížností s ověřenými úlohami, denní výzvu, patnáctku a osmičku s očíslovanými bednami, režim pro děti a trenéra, který ukáže dobrý tah, pojmenuje techniku a odkáže na kapitolu, kde se vykládá.
Mapa průvodce
| Kapitola | Úroveň | Co se naučíte |
|---|---|---|
| 1 Pojmy a historie | základy | co je posuvný hlavolam, tři rodiny, horečka patnáctky v roce 1880 a nepravdivé Loydovo tvrzení, dopravní hlavolamy, pravidla hry v průvodci |
| 2 Tahy, zápis a stav | základy | tah a krok, zápis tahů, stav jako uzel grafu a tah jako hrana, nejmenší počet tahů jako vzdálenost |
| 3 Volná cesta a Uvolnit cestu | základy | čtení od ústí, kdo stojí v cestě, kam musí uhnout – nahoru, nebo dolů podle délky lodi |
| 4 Řetěz překážek | základy | kdo komu brání, strom závislostí, plánování od konce, slepé uličky |
| 5 Krok zpět | pokročilí | proč je někdy nutné pozici zhoršit, dva druhy kroku zpět, odhad obtížnosti úlohy |
| 6 Patnáctka a osmička | pokročilí | inverze a parita, proč polovina pozic nejde složit, úloha 14–15, techniky Řádek po řádku a Poslední dvojice |
| 7 Bloky různých tvarů | pokročilí | čínský hlavolam s velkým čtvercem, tři způsoby počítání tahů (81, 90 a 116), počet stavů, zdravé hraní |
| 8 Navrhování úloh | pokročilí | co dělá úlohu těžkou, jak generátor hry tvoří a vybírá úlohy, rozdělení obtížností v bance |
| 9 Prohledávání do šířky | mistr a věda | fronta a vrstvy, proč BFS dává nejmenší počet tahů, velikost stavových prostorů, obousměrné prohledávání |
| 10 Heuristiky | mistr a věda | A* a IDA*, manhattanská vzdálenost, lineární konflikty, databáze vzorů, „Boží číslo“ 31 a 80 |
| 11 Složitost | mistr a věda | NP-těžkost nejkratšího řešení patnáctky, PSPACE-úplnost dopravních hlavolamů a posuvných bloků, co z toho plyne pro hráče |
| 12 Nejtěžší úlohy a počítač | mistr a věda | nejtěžší počáteční pozice přístavu 6 × 6, symbolické prohledávání, jak hra ověřuje úlohy a jak nápověda hledá nejlepší tah |
Co budete potřebovat
Tužku, čtverečkovaný papír a pár kartiček nebo mincí – přístav i osmičku si snadno postavíte na stole a tahy si zapisujete. Všechny úlohy jsou ale i v laboratořích. Dítě, které zvládne posouvat kostky prstem, projde kapitoly 1 až 4 a minihry k nim. V kapitole 6 se hodí sudá a lichá čísla, v kapitolách 9 až 12 trocha algoritmického myšlení – vše potřebné průvodce vysvětlí na místě.
Navazující látku najdete v sousedních průvodcích: hlavolamy s kusy z čtverečků a paritní důkazy v průvodci Blokové hlavolamy, slučování dlaždic na desce 4 × 4 v průvodci 2048, plánování tahů dopředu v průvodci Šachy, logické hry s jediným řešením v průvodci Sudoku, permutace a dělitelnost v průvodci Matematika, důkaz sporem a invarianty v průvodci Logika a kritické myšlení, grafy, fronty a složitost obecně v průvodci Informatika a odhady a simulace v průvodci Statistika a modely.
Značení a předpoklady
Přístav má 6 řad (shora 1 až 6) a 6 sloupců (zleva 1 až 6); pole ř3s5 je ve 3. řadě, 5. sloupci. Zlatá loď má v textu písmeno Z, ostatní lodě písmena A, B, C… v pořadí čtení (shora, zleva). Loď dlouhá 2 pole je člun, dlouhá 3 pole nákladní loď. Tah se zapisuje písmenem lodi, šipkou a počtem polí: C↓2 = loď C o dvě pole dolů. Pokud není řečeno jinak, tah je posun jedné lodi o libovolný počet polí jedním směrem; posun o jedno pole je krok. Úloha je vyřešená, když zlatá loď dojede k ústí (zaujme pole ř3s5 a ř3s6) – odtud už vypluje sama. Laboratoře, hero i trenér ve 3D hře počítají stejně: nejmenší počet tahů je ověřený úplným prohledáním (kapitola 9).
| Režim / obtížnost | Nejmenší počet tahů úlohy | Kapitoly |
|---|---|---|
| Pro děti | 2–6 | 1, 3 |
| Úlohy 1 | 4–8 | 3 |
| Úlohy 2 | 9–14 | 3, 4 |
| Úlohy 3 | 15–20 | 4, 5 |
| Úlohy 4 | 21–27 | 5, 8 |
| Úlohy 5 | 28–46 | 5, 12 |
| Patnáctka | osmička 3 × 3 a patnáctka 4 × 4, jen řešitelná zamíchání | 6, 10 |
Čtyři druhy rámečků
Konkrétní pozice, tah nebo výpočet, který si můžete ověřit v laboratoři.
Kdo hlavolam vymyslel, kdy vyšel a co o něm zjistili matematici a informatici.
Rychlé pravidlo, zkratka nebo návyk, který používají zkušení hráči.
Častá chyba, mýtus nebo past, do které se snadno spadne.
Studijní materiál o hře. Hrajte pro radost a s mírou – bez sázek a peněz. Průvodce nejmenuje ani nedoporučuje žádné aplikace ani hry; obchodní názvy se objevují jen ve věcné historii a v názvech citovaných článků. Historické údaje a výsledky výzkumu mají v příloze C zdroj a datum ověření (10. 11. 2026). Počty stavů a tahů, pozice v minihrách i tabulky spočítal vlastní řešič průvodce – přímo v prohlížeči nebo skriptem nad stejným kódem.
Rozsahem odpovídá: matematika – permutace, inverze a parita, invarianty, grafy stavů a jejich komponenty, kombinatorika počtu stavů na úrovni úvodních vysokoškolských kurzů diskrétní matematiky; informatika – prohledávání do šířky a do hloubky, obousměrné prohledávání, A* a IDA*, přípustné heuristiky a databáze vzorů z úvodu do umělé inteligence, třídy P, NP a PSPACE a převody z úvodu do teorie složitosti; pravidla – patnáctka a čínský hlavolam podle pramenů v příloze C a vlastní pravidla přístavu 6 × 6, ze kterých vychází hra průvodce.
Vyplutí z přístavu ve 3D
🎮 Zpět ke hře Hra je nahoře na této stránce. Tlačítkem 📲 v její liště si ji nainstalujete do telefonu nebo počítače a hrajete i bez připojení.
Přístavní bazén 6 × 6 s vodou, kamennými nábřežími a dřevěnými moly. Lodě – zlatá loď, čluny dlouhé dvě pole a nákladní lodě dlouhé tři pole – jezdí jen dopředu a dozadu po své délce. Úkol: uvolnit cestu, aby zlatá loď ve třetí řadě vyplula ústím přístavu u majáku. Na výběr jsou Úlohy (obtížnost 1 až 5 podle nejmenšího počtu tahů, v každé alespoň 60 ověřených úloh; postup a hvězdičky se ukládají), Denní výzva (jedna úloha obtížnosti 3 až 4, v daný den stejná pro všechny), Patnáctka (osmička 3 × 3 a patnáctka 4 × 4 s očíslovanými bednami na nábřeží, jen řešitelná zamíchání – kapitola 6) a Pro děti (úlohy na 2 až 6 tahů, neomezené vracení tahů i nápovědy). Pravidla a zápis tahů vysvětlují kapitoly 1 a 2, techniky 3, 4 a 5, jak vznikly úlohy, kapitola 8. V nastavení jde přepnout Pohled 3D / 2D shora. Ovládání v kostce: loď táhněte prstem nebo myší po její délce – zastaví se o jinou loď nebo o nábřeží. Na klávesnici Tab nebo 1–9 výběr lodi, šipky posun, Z zpět, R znovu, T nápověda, N další úloha.
Pojmy a historiezáklady
Posuvný hlavolam má pevný rám a kusy, které se nesmějí zvednout ani otočit – jen posunout po desce na volná pole. Volného místa je málo, a tak každý pohyb jednoho kusu závisí na ostatních. Průvodce se věnuje třem rodinám: patnáctce (stejné čtvercové dlaždice a jedno volné pole), dopravním hlavolamům (obdélníkové bloky jezdí jen po své délce a jeden musí vyjet ven) a posuvným blokům různých tvarů (velký čtverec se prodírá mezi menšími kusy).
Ráno v přeplněném přístavu: zlatá loď chce vyplout, jenže ústí zatarasily čluny a nákladní lodě. Žádná se nemůže otočit ani přeskočit sousedku – může jen popojet dopředu nebo couvnout. Kdo začne tou správnou lodí, je venku za pár tahů. Kdo začne naslepo, točí se v kruhu.
+Teorie: co je posuvný hlavolam, tři rodiny, horečka patnáctky, posuvné bloky, dopravní hlavolamy a pravidla přístavu
1.1Co je posuvný hlavolam
Posuvný hlavolam tvoří deska (rám) rozdělená na pole a kusy, které zabírají celá pole a nepřekrývají se. Jediný dovolený pohyb je posun kusu na sousední volná pole: kus se nezvedá, neotáčí a nepřeskakuje jiné kusy. Cílem je buď dané uspořádání všech kusů (patnáctka), nebo dostat jeden určený kus na určené místo či ven z rámu (dopravní hlavolamy, čínský hlavolam).sliding puzzle, sliding-block puzzle
Všechny tři rodiny sdílejí důležitou vlastnost: každý tah jde vrátit. Když kus posunete, můžete ho stejnou cestou posunout zpět. Proto posuvné hlavolamy nemají „prohrané“ pozice – z každé pozice, ze které šlo úlohu vyřešit, jde vyřešit i dál; nanejvýš jste si zašli. Tahle vlastnost (vratnost) bude důležitá v kapitolách 2 a 9.
1.2Tři rodiny
| Rodina | Deska a kusy | Jak se kusy pohybují | Cíl | Kapitoly |
|---|---|---|---|---|
| patnáctka a osmička | 4 × 4 (3 × 3), stejné čtvercové dlaždice s čísly, jedno volné pole | dlaždice vedle volného pole se do něj posune | seřadit čísla, volné pole vpravo dole | 6, 10 |
| dopravní hlavolamy | 6 × 6, obdélníky 1 × 2 a 1 × 3 | jen po své délce, o libovolný počet volných polí | vyvést určený blok otvorem v okraji | 3–5, 12 |
| bloky různých tvarů | 4 × 5, kusy 2 × 2, 1 × 2, 2 × 1 a 1 × 1 | libovolným směrem na volná pole | velký čtverec otvorem dole ven | 7 |
1.3Patnáctka a horečka roku 1880
Za vynálezce patnáctky se dnes považuje Noyes Palmer Chapman, poštmistr z Canastoty ve státě New York; podle pramenů ukazoval přátelům předchůdce hlavolamu už kolem roku 1874. V prosinci 1879 začal hlavolam vyrábět truhlář Matthias Rice v Bostonu. V únoru 1880 vypukla horečka, v březnu zasáhla Spojené státy od pobřeží k pobřeží a brzy i Evropu. Trvala jen několik měsíců. Chapman podal 21. února 1880 patentovou přihlášku; byla zamítnuta, nejspíš proto, že se příliš podobala patentu Ernesta U. Kinseyho z 20. srpna 1878 na posuvné bloky s čísly.
Ještě v roce 1879 vyšly v časopise American Journal of Mathematics dvě krátké poznámky W. W. Johnsona a W. E. Storyho: dokázaly, že přesně polovinu zamíchání nejde vrátit do výchozího pořadí, ať se snažíte sebevíc. Důkaz a pravidlo, jak to poznat, jsou v kapitole 6.
Americký autor hlavolamů Sam Loyd (1841–1911) o patnáctce poprvé psal v roce 1886 a od roku 1891 až do smrti tvrdil, že ji vymyslel. Vyprávěl také o odměně 1 000 dolarů pro toho, kdo prohodí dlaždice 14 a 15 zpět do pořadí – úloha, která nemá řešení. Jerry Slocum a Dic Sonneveld prošli pro knihu o patnáctce (2006) tisíce dobových novin v Americe i Evropě a ukázali, že Loyd s hlavolamem v letech jeho vzniku a horečky nijak spojen nebyl. Mýtus o Loydově autorství přesto přežíval přes sto let.
1.4Posuvné bloky různých tvarů
Hlavolamy s bloky různých velikostí se objevují na přelomu 19. a 20. století. Americký patent Henryho Waltona z roku 1893 popisuje posuvné obdélníky stejného tvaru; Lewis W. Hardy podal v roce 1907 patent na hlavolam s bloky různých velikostí (udělen 1912) a v roce 1909 si takový hlavolam nechal chránit autorským právem. Anglický patent Johna Harolda Fleminga z roku 1934 popisuje téměř stejné rozestavení, jaké má tradiční čínský hlavolam Chua-žung tao (华容道, „cesta Chua-žung“). Jeho jméno odkazuje na epizodu z klasického románu Příběhy Tří říší, ve které vojevůdce Cchao Cchao prchá úzkou cestou; velký čtverec je on, ostatní kusy vojáci, kteří cestu hlídají. Ve Francii se stejnému hlavolamu říká Červený osel. Kdy a kde vznikla nejstarší verze, prameny nevědí. Nejkratší řešení na 81 tahů zveřejnil Martin Gardner ve Scientific American v únoru 1964 (kapitola 7).
1.5Dopravní hlavolamy
Japonský tvůrce a sběratel hlavolamů Nob Jošigahara (1936–2004) vymyslel podle encyklopedických pramenů v 70. letech hlavolam s auty na zaplněném parkovišti 6 × 6: auta dlouhá dvě pole a nákladní auta dlouhá tři pole jezdí jen dopředu a dozadu a jedno auto musí vyjet ven. Ve Spojených státech se prodává od roku 1996. Tyto hlavolamy zkoumají i matematici: v roce 2002 Gary W. Flake a Eric B. Baum dokázali, že na libovolně velké desce je rozhodnout, zda úloha vůbec má řešení, PSPACE-úplné (kapitola 11), a v roce 2006 Sébastien Collette, Jean-François Raskin a Frédéric Servais spočítali nejtěžší počáteční pozice desky 6 × 6 (kapitola 12).
Obchodní názvy her nejsou obecná jména žánru. Průvodce říká patnáctka, dopravní hlavolam a posuvné bloky; jeho hra je vlastní – místo parkoviště je přístav, místo aut lodě. A Sam Loyd patnáctku nevymyslel, i když to dodnes tvrdí leckterá kniha.
1.6Pravidla přístavu v průvodci
- Přístav je deska 6 × 6 polí. V pravém okraji třetí řady je ústí přístavu s majákem.
- Loď zabírá 2 pole (člun) nebo 3 pole (nákladní loď) v jedné řadě (vodorovná) nebo v jednom sloupci (svislá). Jezdí jen dopředu a dozadu po své délce, o libovolný počet volných polí. Nesmí se překrývat s jinou lodí ani opustit přístav.
- Zlatá loď je vodorovná, dlouhá 2 pole a stojí ve třetí řadě. Jako jediná smí ústím vyplout.
- Ve třetí řadě nestojí jiná vodorovná loď – mezi zlatou lodí a ústím by nikdy nemohla uhnout a úloha by neměla řešení. Zlaté lodi proto brání jen svislé lodě, které třetí řadou procházejí.
- Tah je posun jedné lodi jedním směrem o libovolný počet polí. Úloha je vyřešená, když zlatá loď dojede k ústí. Úkolem je dojít k cíli na co nejméně tahů – na nejmenší počet tahů, který zná řešič.
Člun D stojí svisle v ř3s3 a ř4s3, přímo v cestě. Nahoru nemůže (ř2s3 zabírá loď B), dolů ano: D↓1 ho posune do ř4s3 a ř5s3 a třetí řada je volná. Zlatá loď pak dojede k ústí jedním tahem Z→4. Řešení má 2 tahy a 5 kroků (1 + 4). Kratší být nemůže: zlatá loď se musí pohnout aspoň jednou a dokud v cestě stojí D, k ústí nedojede.
1.7Procvičení
- Posuvný hlavolam: kusy se jen posouvají, nezvedají ani neotáčejí; každý tah jde vrátit.
- Tři rodiny: patnáctka (1880, Chapman – ne Loyd), dopravní hlavolamy (Jošigahara, 70. léta) a bloky různých tvarů (čínský hlavolam, 81 tahů).
- V přístavu jezdí lodě jen po své délce; zlatá loď ve třetí řadě musí k ústí; tah = posun o libovolný počet polí.
Tahy, zápis a stavzáklady
Abychom mohli říct, že úloha má „nejkratší řešení na 10 tahů“, musíme se dohodnout, co je tah. V průvodci je tah posun jedné lodi o libovolný počet polí jedním směrem; posun o jedno pole je krok. Stav je rozmístění všech lodí. Stavy a tahy tvoří graf: stav je uzel, tah hrana – a nejmenší počet tahů je nejkratší cesta v grafu ze startu do cíle.
Představte si mapu, na které je každé rozmístění lodí jedno město a každý tah jedna silnice mezi dvěma městy. Úloha je cesta z města „start“ do některého z měst „zlatá loď u ústí“. Kdo zná mapu, najde nejkratší trasu; kdo ji nezná, bloudí.
+Teorie: tah a krok, zápis tahů a stavů, stav jako uzel, graf stavů, nejmenší počet tahů jako vzdálenost
2.1Tah a krok
Tah je posun jedné lodi jedním směrem o libovolný počet volných polí. Krok je posun jedné lodi o jedno pole. Tah o k polí jsou tedy k kroků. Oba způsoby počítání se používají: hra průvodce a většina sbírek úloh počítají tahy, některé vědecké práce kroky (kapitola 12).move vs. step (single-unit move)
Protože jeden tah v přístavu 6 × 6 posune loď nejvýš o 4 pole (člun ze sloupce 1 do sloupce 5), platí pro nejmenší počet tahů t a nejmenší počet kroků k téže úlohy
Levá nerovnost: každé řešení po krocích je zároveň řešením po tazích (každý krok je tah), takže tahů není víc než kroků. Pravá: nejkratší řešení na t tahů má nejvýš 4t kroků. V bance 3D hry má nejkratší řešení po krocích v průměru zhruba 1,7krát víc kroků než tahů (kapitola 8).
V úloze A.B.CC/ADB.EE/GDZZ.F/G.HIIF/J.HKKK/J.LL.. (zápis viz 2.2) je nejkratší řešení po tazích C←1, E←1, F↑2, Z→2: 4 tahy, ale 6 kroků – nákladní loď F musí uhnout nahoru o dvě pole a k tomu jí musí z cesty C a E. Nejkratší řešení po krocích je jiné: Z→1, H↑1, K←1, F↓1, Z→1 – 5 kroků, ale 5 tahů. Zlatá loď nejdřív popojede, člun H vjede na uvolněné pole, nákladní loď K se posune a F uhne dolů o jediné pole. Řešič průvodce ověřil, že kratší řešení v žádném z obou počítání neexistuje. Jaké řešení je „nejlepší“, tedy záleží na tom, co počítáme.
2.2Zápis tahů a stavů
Tah se zapisuje písmenem lodi, šipkou směru a počtem polí: D↓1, Z→4. Řešení je posloupnost tahů oddělených čárkou. Pole se značí řadou a sloupcem, ř3s5 je třetí řada shora a pátý sloupec zleva.
Celý stav zapíše šest řádků po šesti znacích oddělených lomítkem: tečka je voda, Z zlatá loď, další písmena lodě. Úloha 1 z kapitoly 1 vypadá takto: ....../AABBCC/ZZD.../..D.../....../....... Ze zápisu poznáte i orientaci lodi: písmena vedle sebe v řádku jsou vodorovná loď, pod sebou svislá.
Zapisujte si řešení během hraní. Když se zamotáte, zápis ukáže, kterou loď jste posunuli tam a zpátky zbytečně – dvojice tahů „D↓1, D↑1“ jde vždy škrtnout a řešení se zkrátí o dva tahy.
2.3Stav jako vektor poloh
Každá loď se pohybuje jen ve své řadě nebo sloupci, takže stav popíše jediné číslo pro každou loď: u vodorovné lodi sloupec jejího levého konce, u svislé řada horního konce. Člun má v řadě o šesti polích 5 možných poloh, nákladní loď 4. Počet stavů úlohy s loděmi délek \( \ell_1, \dots, \ell_n \) je proto nejvýš
Skutečně dosažitelných stavů je mnohem méně: lodě se nesmějí překrývat a do mnoha rozmístění se ze startu vůbec nedá dojet. Úloha v laboratoři má 13 lodí (7 člunů včetně zlaté lodi a 6 nákladních), mez dává 57 · 46 = 320 000 000, ale dosažitelných stavů je jen 24.state, state vector
2.4Graf stavů
Graf stavů má za uzly stavy a za hrany tahy: dva stavy spojuje hrana, když jeden vznikne z druhého jedním tahem. Protože každý tah jde vrátit, je graf neorientovaný. Stavy, do kterých se ze startu dá dojet, tvoří jeho komponentu (souvislou část). Cílové stavy jsou ty, ve kterých zlatá loď stojí u ústí; v jedné komponentě jich může být víc – ostatní lodě mohou stát různě.state graph, connected component
2.5Nejmenší počet tahů je vzdálenost
Řešení je cesta v grafu ze startu do některého cílového stavu a jeho délka je počet hran. Nejmenší počet tahů je tedy vzdálenost startu od množiny cílových stavů. Graf po krocích má stejné uzly, ale méně hran (jen posuny o jedno pole), a proto jiné vzdálenosti: v laboratoři má 30 hran místo 36 a nejkratší cesta 15 kroků místo 10 tahů. Jak vzdálenost spočítat pro velký graf, aniž bychom ho kreslili, ukazuje kapitola 9.
Zde \(s_0\) je start a \(C\) množina cílových stavů. Hodnota \(d(s)\) pro všechny stavy komponenty je „mapa vzdáleností“, ze které hra radí (kapitola 12).
Když dva zdroje uvádějí pro stejnou úlohu různý „nejmenší počet tahů“, nemusí se mýlit – mohou počítat jinak. Vždy se ptejte: tah, nebo krok? Počítá se poslední vyplutí lodi jako tah navíc? V průvodci i ve hře končí řešení tahem, kterým zlatá loď dojede k ústí.
2.6Procvičení
- Tah = posun jedné lodi o libovolný počet polí; krok = o jedno pole; t ≤ k ≤ 4t.
- Zápis: „C↓2“ pro tah, šest řádků po šesti znacích pro stav.
- Stavy a tahy tvoří neorientovaný graf; nejmenší počet tahů je vzdálenost startu od cílových stavů.
Volná cesta a Uvolnit cestuzáklady
Dvě nejjednodušší techniky trenéra 3D hry. Volná cesta: když mezi zlatou lodí a ústím nic nestojí, zlatá loď dojede jedním tahem. Uvolnit cestu: když v cestě stojí svislé lodě, každá musí uhnout nahoru, nebo dolů – a u nákladní lodi je jen jedna možnost. Obě techniky začínají stejně: čtením od ústí.
Strážce majáku vidí z věže celou třetí řadu. Nepočítá všechny lodě v přístavu – zajímají ho jen ty, které stojí mezi zlatou lodí a ústím. Kdo se dívá jako on, ví hned, kterou lodí začít.
+Teorie: čtení od ústí, Volná cesta, kam musí člun a nákladní loď, volba směru, z čeho se skládají nejkratší řešení
3.1Čtení od ústí
Začněte u majáku a jděte třetí řadou doleva až ke zlaté lodi. Každá loď, na kterou narazíte, je v cestě. Protože ve třetí řadě nesmí stát jiná vodorovná loď (kapitola 1), jsou to vždy svislé lodě, které třetí řadu kříží. Na startu úloh 3D hry jich v cestě stojí jedna až čtyři, v průměru dvě (Tab. 3.1).blocking vehicles
3.2Volná cesta
Když v cestě nic nestojí, zlatá loď dojede k ústí jedním tahem, ať je to o 1 pole, nebo o 4. Je to vždy poslední tah řešení a nic nestojí víc kroků než tahů navíc. Kontrolujte proto po každém tahu, jestli už cesta není volná – začátečníci často posouvají další lodě, i když už mohli vyplout.
Tah zlaté lodi doprava, který ještě nekončí u ústí (cesta je volná jen zčásti), trenér hry také počítá jako Volnou cestu: zlatá loď popojede a uvolní pole za sebou pro jinou loď.
3.3Kam musí člun a kam nákladní loď
Svislá loď v cestě musí opustit třetí řadu. Nad ní jsou jen dvě řady, pod ní tři. Z toho plyne nejdůležitější pravidlo kapitoly:
- Člun (2 pole) má dvě možnosti: nahoru do řad 1–2, nebo dolů do řad 4–5 (případně dál, do 5–6). Stojí-li v řadách 2–3, je to ↑1, nebo ↓2; stojí-li v řadách 3–4, ↑2, nebo ↓1.
- Nákladní loď (3 pole) se nad třetí řadu nevejde. Musí vždy dolů, až do řad 4–6: z řad 1–3 o 3 pole, z 2–4 o 2 pole, z 3–5 o 1 pole.
Ve vzorci je \(r\) řada horního konce lodi (u člunu v cestě 2 nebo 3, u nákladní lodi 1 až 3). Člun v řadách 2–3 má \(r = 2\): nahoru o 1 pole, nebo dolů o 2 pole. Nákladní loď v řadách 1–3 má \(r = 1\): dolů o 3 pole. Prakticky stačí počítat pole, která musí loď uvolnit.
3.4Kterým směrem a o kolik
Když má člun na výběr, rozhodují tři otázky:
- Jsou potřebná pole volná? Pokud jen na jedné straně, je rozhodnuto. Pokud na žádné, je to Řetěz překážek (kapitola 4).
- Nezatarasí loď cestu jiné lodi, kterou budu potřebovat? V Obr. 3.1 může C dolů o 2 i o 3 pole. Jen posun o 3 nechá volné pole ř4s3, které potřebuje nákladní loď E, aby uhnula doleva a pustila dolů F a G.
- Kolik tahů to stojí celkem? Kratší posun není vždy lepší – počítají se tahy, ne pole.
Start AAABBB/..C.FG/ZZC.FG/D..EEE/D..H../D..HII. Čtení od ústí: G, F, C. Všechny tři jsou čluny v řadách 2–3; nahoru nemohou (ř1 zabírají A a B), musí dolů. F a G dolů nemohou, dokud v ř4 stojí E. Nejkratší řešení: C↓3, E←2, F↓2, G↓2, Z→4 – 5 tahů. Kdo začne C↓2, zablokuje E a potřebuje o tah víc. Řešič průvodce ověřil, že C↓3 je jediný první tah nejkratšího řešení.
3.5Z čeho se skládají nejkratší řešení
Trenér 3D hry každý tah nejkratšího řešení zařadí k jedné technice: tah zlaté lodi doprava je Volná cesta, tah lodi, která stojí v cestě, Uvolnit cestu, tah lodi mimo cestu Řetěz překážek (kapitola 4) a tah, kterým zlatá loď couvne nebo jiná loď vjede do cesty, Krok zpět (kapitola 5).
| Obtížnost | Úloh | Tahů celkem | Lodí v cestě na startu (průměr) | Volná cesta | Uvolnit cestu | Řetěz překážek | Krok zpět |
|---|---|---|---|---|---|---|---|
| pro děti | 70 | 280 | 1,5 | 25,0 % | 37,9 % | 32,1 % | 5,0 % |
| 1 | 64 | 382 | 1,8 | 19,4 % | 32,7 % | 42,4 % | 5,5 % |
| 2 | 64 | 732 | 1,9 | 14,1 % | 27,7 % | 47,4 % | 10,8 % |
| 3 | 64 | 1 116 | 2,1 | 11,0 % | 24,3 % | 51,6 % | 13,1 % |
| 4 | 64 | 1 497 | 2,1 | 9,8 % | 21,8 % | 54,4 % | 14,0 % |
| 5 | 64 | 2 170 | 2,6 | 9,9 % | 21,6 % | 53,2 % | 15,3 % |
Čím těžší úloha, tím méně tahů patří zlaté lodi a lodím přímo v cestě a tím víc „přípravě“ – tahům lodí, které v cestě nestojí. U těžkých úloh je to přes polovinu všech tahů. Proto se další dvě kapitoly věnují právě jim.
Před každým tahem si řekněte nahlas, kterou loď tím tahem pouštíte. Tah, po kterém nedokážete jmenovat loď, které jste uvolnili místo, je podezřelý – buď je to zbytečné bloudění, nebo Krok zpět, a ten má mít jasný důvod.
3.6Procvičení
- Čtěte od ústí: v cestě stojí jen svislé lodě, které kříží třetí řadu.
- Člun uhne nahoru, nebo dolů; nákladní loď vždy dolů do řad 4–6.
- Volte směr a délku posunu tak, abyste nezatarasili loď, kterou budete potřebovat.
Řetěz překážekpokročilí
Loď v cestě často nemůže uhnout, protože jí brání jiná loď – a té zase další. Technika Řetěz překážek hledá, kdo brání tomu, kdo brání, až k lodi, která se pohnout může. Celý řetěz se pak rozmotává od konce. Pomůckou je strom překážek: kořenem je zlatá loď, větvemi možnosti, jak každá loď může uhnout.
Kapitán zlaté lodi volá na člun v cestě: „Uhni!“ – „Nemůžu, za mnou stojí nákladní loď.“ – „Tak ať uhne ona!“ – „Nemůže, za ní je další.“ Kdo si ten rozhovor nakreslí, uvidí, kterou lodí začít.
+Teorie: přímé a nepřímé překážky, strom překážek, kruhy, rozmotání od konce, odhad počtu tahů
4.1Přímé a nepřímé překážky
Přímá překážka stojí zlaté lodi v cestě (kapitola 3). Nepřímá překážka stojí na poli, přes které musí projet jiná překážka, když uhýbá. Nepřímou překážkou bývá i vodorovná loď v řadě 1, 2, 4, 5 nebo 6 – v cestě zlaté lodi nikdy nestojí, ale může zavírat sloupec svislé lodi. V tabulce 3.1 jsou tahy nepřímých překážek ve sloupci Řetěz překážek; v úlohách obtížnosti 3 až 5 tvoří přes polovinu všech tahů.blocking chain
4.2Strom překážek
Strom se staví shora dolů:
- Kořen je zlatá loď. Pod ní jsou lodě v cestě (čtení od ústí).
- U každé lodi jsou možnosti, jak uhnout: nejbližší poloha na jednu stranu a nejbližší na druhou, ve kterých už nepřekáží. U nákladní lodi v cestě je možnost jen jedna (dolů).
- U každé možnosti jsou lodě, které stojí na polích, přes která musí loď projet. Když žádná, je u možnosti volno.
- Pro každou takovou loď se postup opakuje – kam musí uhnout, aby pole uvolnila.
Stačí najít v každé větvi pod lodí v cestě jednu možnost, která vede až k „volnu“. Lodě na této cestě se pak posouvají odspodu nahoru: nejdřív ta, u které je volno, nakonec loď přímo v cestě a zlatá loď.
- Z zlatá loď – v cestě k ústí: E, D
- E musí z cesty:
- dolů o 1 pole – brání I
- I musí z cesty:
- doprava o 1 pole – brání F
- F …
- doprava o 1 pole – brání F
- I musí z cesty:
- dolů o 1 pole – brání I
- D musí z cesty:
- nahoru o 1 pole – volno
- dolů o 2 pole – brání F
- F musí z cesty:
- nahoru o 3 pole – brání D
- D (už výš ve stromu – kruh)
- nahoru o 3 pole – brání D
- F musí z cesty:
- E musí z cesty:
4.3Kruhy
Když loď X brání lodi Y a Y zase lodi X, je ve stromu kruh. Kruh neznamená, že úloha nemá řešení – jen že touto možností nejde začít. Hledejte jinou možnost (v Obr. 4.1 D nahoru místo dolů). Když jsou kruhem zablokované všechny možnosti, musí se některá loď dočasně posunout jinam, i za cenu, že na chvíli překáží víc – to je Krok zpět (kapitola 5).
Start AB..../ABCCCD/ZZE..D/..E..F/GGE..F/HHIIIF, nejmenší počet tahů 9. Strom: D↑1 je volno. E↓1 potřebuje ř6s3, kde stojí I; I→1 potřebuje ř6s6, kde stojí F; F může jen nahoru o 1 – a tím vjede do cesty! Nejkratší řešení proto jde ve dvou vlnách: D↑1, F↑1, I→1, E↓1, Z→3 (zlatá loď popojede za sloupec E až k F) a pak E↑1, I←1, F↓1, Z→1. Lodě E, I a F se vracejí tam, odkud vyjely – uhnuly jen dočasně, aby zlatá loď prošla kolem sloupce 3.
4.4Rozmotání od konce
Řetěz se nejlépe plánuje odzadu. Poslední tah řešení je vždy tah zlaté lodi k ústí. Před ním musí z cesty poslední překážka – a před tím to, co jí bránilo. Kdo si představí cílový stav a jde tahy zpět, vidí, které lodě musí být kde.
4.5Odhad počtu tahů
Zaručená dolní mez je jednoduchá: každá loď v cestě se musí pohnout aspoň jednou a zlatá loď také. Strom odhad zpřesní – když každá možnost lodi v cestě vede přes další lodě, musí se pohnout i ony. Spočítejte lodě na nejkratší cestě stromu a přidejte zlatou loď:
V úloze B stojí v cestě D a E (zaručeně aspoň 3 tahy) a na nejkratší cestě stromu leží D, E, I a F: odhad 1 + 4 = 5 tahů. Skutečné nejmenší řešení má 9 tahů – o 4 víc, protože E, I, F i zlatá loď se pohnou dvakrát. Lodě se často musí vrátit a některé tahy musí udělat jindy, než by chtěly; proto je strom pomůcka, ne řešič.
Když řetěz vede přes nákladní loď v řadě 6 nebo v řadě 1, je to často „úzké hrdlo“ celé úlohy – vodorovná nákladní loď v krajní řadě zavírá tři sloupce najednou. Podívejte se nejdřív, kam se může posunout a které sloupce tím otevře.
4.6Procvičení
- Strom překážek: zlatá loď → lodě v cestě → kam uhnout → kdo brání; hledejte větev, která končí volnem.
- Kruh v jedné větvi neznamená konec – zkuste jinou možnost, nebo dočasný tah.
- Plánujte odzadu; dolní mez = 1 + počet lodí, které se musí pohnout.
Krok zpětpokročilí
Nejtěžší technika, protože jde proti intuici: tah, po kterém to vypadá hůř. Zlatá loď couvne od ústí, nebo jiná loď vjede do cesty – a právě tím uvolní pole, které chybí jiné lodi. V těžkých úlohách 3D hry se bez Kroku zpět neobejde žádné nejkratší řešení.
Řidič, který chce vyjet z parkovacího místa, občas musí nejdřív couvnout, aby se mohl vytočit. Totéž platí v přístavu – jen místo volantu jsou tu ostatní lodě, kterým couvnutí uvolní místo.
+Teorie: co je Krok zpět, dva druhy, jak ho poznat, kolik úloh ho potřebuje, míry obtížnosti
5.1Když musí být hůř, než bude líp
Krok zpět je tah, kterým se cesta zlaté lodi k ústí zhorší: zlatá loď couvne (cesta se prodlouží), nebo jiná loď vjede do cesty (v cestě stojí víc lodí). Vypadá jako chyba, ale v nejkratším řešení má vždy důvod: uvolní pole, které potřebuje jiná loď, a ta pak uvolní cestu. Vzdálenost do cíle se i Krokem zpět zmenší o jeden tah – „hůř“ je to jen na pohled.backward move, detour
5.2Dva druhy
- Zlatá loď couvne. Uvolní pole ve třetí řadě vpravo od sebe – ale také pole, na kterém stála. Do třetí řady pak může sjet svislá loď, která potřebuje projet (nebo uhnout) přes třetí řadu.
- Loď vjede do cesty. Svislá loď se posune do třetí řady, protože jen tak uvolní pole na druhém konci svého sloupce – v řadě 1, 2, 5 nebo 6 – pro vodorovnou loď.
Start A.BBC./A...C./ZZD.../..D.../EEEFF./GGGHHH. Nejkratší řešení: C↓1 (Krok zpět – C vjede do cesty, aby B mohla doprava), B→1, D↑2, Z→1, F→1, E→1, A↓3, Z←1 (Krok zpět), D↓1 (Krok zpět), B←3, C↑1, D↑1, Z→4. Lodě A, B, C a D se točí kolem řady 1: B musí nejdřív doprava, aby D mohla nahoru, a pak doleva, aby C a D mohly nahoru znovu. Řešič průvodce ověřil, že žádné řešení na 13 tahů bez Kroku zpět neexistuje.
5.3Jak Krok zpět poznat
- Strom překážek má jen kruhy. Každá možnost lodi v cestě vede přes loď, která potřebuje právě ji (kapitola 4).
- Chybějící pole zabírá zlatá loď. Svislá loď vlevo od ústí nemůže sjet, protože pod ní stojí zlatá loď – zlatá loď musí na chvíli couvnout nebo popojet.
- Jediné volné místo svislé lodi je ve třetí řadě. Loď musí do cesty, aby uvolnila pole na druhém konci sloupce.
Krok zpět bývá součástí dvojice: loď vjede do cesty a později z ní zase vyjede (C↓1 … C↑1, D↓1 … D↑1 v příkladu). Kdo udělá jen první polovinu a zapomene, proč, zůstane mu v cestě o loď víc.
Ne každý tah, který vypadá jako Krok zpět, je dobrý. Ve většině stavů vede blíž k cíli jen asi každý čtvrtý až pátý tah (Tab. 5.1). Krok zpět dělejte, jen když umíte říct, kterou loď jím pouštíte a kdy se loď vrátí.
5.4Kolik úloh Krok zpět potřebuje
Řešič průvodce u každé úlohy 3D hry zjistil, jestli existuje nejkratší řešení bez Kroku zpět. Výsledek ukazuje, proč je Krok zpět „technikou mistrů“: v lehkých úlohách ho potřebuje asi pětina, v obtížnosti 4 a 5 všechny.
| Obtížnost | Úloh | Nejmenší počet tahů (průměr) | Nejmenší počet kroků (průměr) | Stavů v komponentě (medián) | Krok zpět nutný | Tahů vedoucích blíž k cíli |
|---|---|---|---|---|---|---|
| pro děti | 70 | 4,0 | 7,9 | 150 | 14 (20 %) | 23 % |
| 1 | 64 | 6,0 | 9,9 | 259 | 12 (19 %) | 27 % |
| 2 | 64 | 11,4 | 19,2 | 1 108 | 47 (73 %) | 24 % |
| 3 | 64 | 17,4 | 29,7 | 4 094 | 58 (91 %) | 23 % |
| 4 | 64 | 23,4 | 39,6 | 11 058 | 64 (100 %) | 22 % |
| 5 | 64 | 33,9 | 57,2 | 5 202 | 64 (100 %) | 22 % |
Poslední sloupec: v každém stavu jednoho nejkratšího řešení řešič spočítal, kolik ze všech možných tahů vede o krok blíž k cíli, a podíly zprůměroval. Hádání naslepo tedy trefí dobrý tah zhruba jednou ze čtyř až pěti pokusů – a v úloze na 25 tahů to musí trefit 25krát za sebou.
5.5Co dělá úlohu těžkou
Nejmenší počet tahů je nejjednodušší míra a 3D hra podle něj řadí úlohy do obtížností. Tabulka ale ukazuje, že s ním rostou i další míry: počet stavů, ve kterých se dá bloudit, a potřeba Kroku zpět. Neroste všechno stejně – úlohy obtížnosti 5 mají v mediánu méně stavů než úlohy obtížnosti 4. Horolezení generátoru (kapitola 8) hledá úlohy s dlouhým nejkratším řešením, ne s velkou komponentou. Dlouhé řešení v malé komponentě znamená, že stavy jsou „navlečené“ za sebou jako korálky a hráč nemá zkratky.
V těžké úloze hledejte klíčovou loď – tu, která se v řešení pohne nejvíckrát. Bývá to člun nebo nákladní loď v řadě 1 nebo 6, která otevírá a zavírá více sloupců. Když pochopíte, proč se pohybuje tam a zpátky, zbytek řešení do sebe zapadne.
5.6Procvičení
- Krok zpět: zlatá loď couvne, nebo jiná loď vjede do cesty – a přesto je to tah nejkratšího řešení.
- Poznáte ho podle kruhů ve stromu, podle pole blokovaného zlatou lodí, podle sloupce, který má volno jen ve třetí řadě.
- V obtížnosti 4 a 5 3D hry ho potřebují všechny úlohy.
Patnáctka a osmičkapokročilí
Patnáctka (4 × 4) a osmička (3 × 3) mají jedno volné pole a stejné čtvercové dlaždice. Přesně polovinu zamíchání nejde seřadit – a poznat to lze bez jediného tahu, spočítáním inverzí. Řešitelná zamíchání se skládají technikami Řádek po řádku a Poslední dvojice, které radí i trenér 3D hry.
Za horečky roku 1880 hledali lidé od pobřeží k pobřeží, jak v seřazené patnáctce prohodit 14 a 15. Nenašli – a matematici už tehdy věděli proč. Stačí spočítat, kolikrát je větší číslo před menším.
+Teorie: inverze, proč tah nemění paritu, polovina zamíchání, úloha 14–15, Řádek po řádku, Poslední dvojice, nejtěžší pozice
6.1Pravidla a počítání tahů
Deska W × H má W·H − 1 dlaždic a jedno volné pole. Tah je posun jedné dlaždice sousedící s volným polem na volné pole. Cíl: dlaždice 1, 2, 3, … po řádcích, volné pole vpravo dole. Hra i laboratoř počítají tahy po jedné dlaždici; posun celé řady dlaždic najednou se v literatuře počítá zvlášť (u osmičky pak stačí nejvýš 24 tahů místo 31 – spočítal řešič průvodce).15 puzzle, 8 puzzle, single-tile move
6.2Inverze
Přečtěte dlaždice po řádcích a volné pole vynechte. Inverze je každá dvojice, ve které je větší číslo dřív než menší. Seřazená deska má 0 inverzí; obrácené pořadí 15, 14, …, 1 má jich 15 · 14 / 2 = 105.inversion, parity
Po řádcích: 1, 2, 3, 4, 5, 6, 8, 7. Jediná dvojice v nesprávném pořadí je (8, 7): 1 inverze, lichý počet. Osmička má lichou šířku, takže pozice je neřešitelná – žádnou posloupností tahů se 7 a 8 prohodit nedají.
6.3Proč tah nemění paritu
Vodorovný tah nezmění pořadí dlaždic při čtení po řádcích, tedy ani počet inverzí. Svislý tah přesune jednu dlaždici o W − 1 míst v pořadí čtení – přeskočí W − 1 jiných dlaždic a s každou se inverze buď objeví, nebo zmizí. Počet inverzí se tedy změní o liché, nebo sudé číslo podle toho, jestli je W − 1 liché, nebo sudé.
- Lichá šířka (osmička, W = 3): W − 1 = 2 je sudé, parita inverzí se nikdy nezmění. Cíl má 0 inverzí, proto je zamíchání řešitelné, právě když má sudý počet inverzí.
- Sudá šířka (patnáctka, W = 4): svislý tah změní počet inverzí o liché číslo (3, 1, −1 nebo −3) a zároveň posune volné pole o řádek. Součet inverzí a řádku volného pole (počítaného odspodu, spodní řádek = 1) proto paritu nemění. V cíli je součet 0 + 1 = 1, lichý.
Zde \(r\) je řádek volného pole odspodu. Že je podmínka nejen nutná, ale i postačující – každé zamíchání se správnou paritou se dá seřadit – dokázali W. W. Johnson a W. E. Story už v roce 1879 (kapitola 1). Proto je řešitelných zamíchání přesně polovina:
Úloha 14–15 – seřazená patnáctka s prohozenými posledními dvěma dlaždicemi – je nejznámější neřešitelná úloha patnáctky. Sam Loyd později vyprávěl, že za její vyřešení slíbil 1 000 dolarů. Výhra byla jistá jen pro něj: úloha řešení nemá.
6.4Řádek po řádku
Lidská metoda, kterou radí trenér 3D hry, když je zamíchání daleko od cíle. Desku zmenšujete: seřadíte první řádek a už na něj nesáhnete, pak první sloupec zbytku, pak další řádek a sloupec, až zbude 2 × 2 – ten se jen otáčí, dokud dlaždice nejsou na místě. Výsledné řešení bývá delší než nejkratší, ale metoda funguje vždy (u řešitelného zamíchání) a nevyžaduje počítání.row by row method
6.5Poslední dvojice
Poslední dvě dlaždice řádku (třeba 3 a 4) nejde uložit jednu po druhé – když položíte trojku na místo, čtyřka ji při příchodu vytlačí. Technika Poslední dvojice: připravte čtyřku na místo trojky a trojku pod ni, volné pole vedle. Pak čtyřka jde doprava a trojka nahoru – oba kusy zapadnou dvěma tahy. Stejně se skládají poslední dvě dlaždice sloupce, jen otočeně.
Dlaždici posouvejte k cíli „kolem dokola“: volné pole obíhá dlaždici a ta se posune o jedno pole za každý oběh (zhruba 5 tahů na pole po přímce). Nikdy nepřetahujte volné pole přes hotové řádky – rozbijete, co už máte.
6.6Nejtěžší pozice
Řešič průvodce prohledal do šířky všech 181 440 řešitelných pozic osmičky: nejvzdálenější jsou od cíle 31 tahů a jsou jen 2; průměrná vzdálenost je 22,0 tahu. U patnáctky je pozic přes deset bilionů. Že každou jde seřadit nejvýš na 80 tahů, ukázal v roce 1999 Adrian Brüngger se spolupracovníky (paralelní prohledávání ZRAM); úplné prohledání do šířky všech pozic patnáctky dokončili Richard Korf a Peter Schultze v roce 2005. Pozic, které 80 tahů opravdu potřebují, je 17.
| Osmička 3 × 3 | Patnáctka 4 × 4 | |
|---|---|---|
| všech rozmístění | 9! = 362 880 | 16! = 20 922 789 888 000 |
| řešitelných (polovina) | 181 440 | 10 461 394 944 000 |
| nejvíc tahů do cíle | 31 (2 pozice) | 80 (17 pozic) |
| nejvíc tahů při posunu celé řady | 24 (1 pozice) | – |
| průměrná vzdálenost od cíle | 22,0 tahu | – |
| zdroj | úplné prohledání řešičem průvodce | Brüngger a kol. 1999, Korf a Schultze 2005 |
6.7Procvičení
- Inverze rozhodnou bez hraní: osmička řešitelná při sudém počtu, patnáctka při lichém součtu inverzí a řádku volného pole odspodu.
- Řešitelná je přesně polovina zamíchání; prohození dvou dlaždic řešitelnost obrátí.
- Skládejte Řádek po řádku, poslední dvě dlaždice řádku technikou Poslední dvojice.
Bloky různých tvarůpokročilí
Tradiční čínský hlavolam má na desce 4 × 5 deset kusů čtyř tvarů a jen dvě volná pole. Kusy se smějí posouvat libovolným směrem – a proto záleží na tom, co je „jeden tah“. Nejkratší řešení má 81, 90, nebo 116 tahů podle toho, jak počítáte.
Podle čínské legendy prchá vojevůdce Cchao Cchao úzkou cestou Chua-žung a stráže mu ji zatarasily. Velký čtverec je on, ostatní kusy vojáci. Kudy proklouznout, když se vojáci mohou jen posouvat?
+Teorie: kusy a cíl, tři způsoby počítání, stavy, role kusů, historie
7.1Kusy a cíl
Deska má 4 sloupce a 5 řad, ve spodním okraji uprostřed je otvor široký dvě pole. Kusy: velký čtverec 2 × 2, čtyři svislé obdélníky 1 × 2, jeden vodorovný obdélník 2 × 1 a čtyři malé čtverce 1 × 1 – dohromady 4 + 8 + 2 + 4 = 18 polí, 2 zůstávají volná. Na startu je velký čtverec nahoře uprostřed, pod ním vodorovný obdélník. Cíl: velký čtverec dole uprostřed, odkud může otvorem ven.sliding-block puzzle, Klotski
7.2Tři způsoby počítání
V přístavu jezdí lodě jen po přímce, takže tah je jasný. Tady může kus zahnout za roh, a tak se používají tři počítání:
- krok – posun kusu o jedno pole,
- přímý tah – posun jednoho kusu jedním směrem o libovolný počet polí,
- tah cestou – posun jednoho kusu kamkoli po volných polích, i za roh (malý čtverec tak může objet roh, protože volná pole jsou dvě).
| Počítání | Nejmenší počet | Dosažitelných stavů |
|---|---|---|
| tah cestou (kus kamkoli) | 81 | 25 955 |
| přímý tah (jedním směrem) | 90 | 25 955 |
| krok (o jedno pole) | 116 | 25 955 |
Stavů je ve všech počítáních stejně – všechna tři počítání vedou ke stejným rozestavením, jen různým počtem tahů. Číslo 81 je to, které uvádí literatura (kapitola 1); 90 a 116 spočítal řešič průvodce.
7.3Proč jen 25 955 stavů
Kusy stejného tvaru jsou zaměnitelné – dva prohozené malé čtverce jsou totéž rozestavení. I tak se těchto deset kusů dá na desku 4 × 5 rozložit 65 880 způsoby (spočítal řešič průvodce úplným výčtem). Ze startu je ale dosažitelných jen 25 955, asi 39 %. Ostatní rozestavení tvoří jiné komponenty grafu stavů: mezi nimi a startem nevede žádná posloupnost posunů, podobně jako mezi dvěma polovinami zamíchání patnáctky (kapitola 6).
7.4Role kusů
- Velký čtverec je jako zlatá loď: potřebuje dvě volná pole vedle sebe. Každý jeho posun stojí přípravu.
- Vodorovný obdélník je závora: dokud leží pod velkým čtvercem, čtverec nemůže dolů. Většina řešení ho musí dostat na stranu nebo dolů.
- Malé čtverce jsou mazivo: putují tam, kde chybí volné pole. Dobré řešení je drží blízko volných polí.
- Svislé obdélníky chodí v párech: dva vedle sebe zabírají stejný prostor 2 × 2 jako velký čtverec a mohou si s ním „vyměnit místo“.
Udržujte obě volná pole vedle sebe. Dvojice volných polí vedle sebe pustí velký čtverec i obdélník; dvě volná pole daleko od sebe pustí jen malé čtverce. Když se volná pole rozdělí, první starostí je spojit je zpátky.
7.5Historie a jména
Americký patent Henryho Waltona z roku 1893 popisuje posuvné obdélníky stejného tvaru. Lewis W. Hardy podal v roce 1907 patent na hlavolam s kusy různých velikostí (udělen 1912) a v roce 1909 si nechal autorským právem chránit hlavolam Pennant Puzzle. Anglický patent Johna Harolda Fleminga z roku 1934 popisuje téměř stejné rozestavení, jaké má čínský Chua-žung tao; ten se podle pramenů datuje do 30. let 20. století. Ve Francii se mu říká Červený osel. Kde vznikla nejstarší verze, není známo. První řešení na 81 tahů zveřejnil Martin Gardner ve Scientific American v únoru 1964.
Různé zdroje uvádějí pro stejný hlavolam různé počty tahů – 81, 90, 116 i jiné. Obvykle se neliší řešení, ale počítání (a někdy i rozestavení nebo cíl: dojet nad otvor, nebo vyjet ven). Než čísla porovnáte, zjistěte, co se počítá.
7.6Procvičení
- Čínský hlavolam: 10 kusů, 2 volná pole, velký čtverec k otvoru; 25 955 dosažitelných stavů.
- Nejkratší řešení: 81 tahů cestou, 90 přímých tahů, 116 kroků – vždy se ptejte, co se počítá.
- Držte volná pole vedle sebe a vodorovný obdélník dostaňte zpod velkého čtverce.
Navrhování úlohmistr a věda
Kde se berou úlohy 3D hry? Žádnou nevymyslel člověk – vyrobil je generátor: náhodně rozmístí lodě, prohledá všechny stavy, které z rozmístění vedou, a za úlohu vezme ten nejvzdálenější od cíle. Těžké úlohy jsou ale vzácné, a tak je generátor dohledává horolezením. Kapitola ukazuje postup i čísla z výroby banky.
Náhodně rozházené lodě skoro vždy vyplují za pár tahů. Úloha na 40 tahů je mezi nimi vzácná jako perla v ústřici – a kdo ji chce najít, musí otevřít tisíce ústřic, nebo umět poznat, kde perla roste.
+Teorie: dobrá úloha, postup generátoru, nejtěžší stav komponenty, vzácnost těžkých úloh, horolezení, třídění do obtížností, banka patnáctky
8.1Co je dobrá úloha
- Má řešení a jeho nejmenší počet tahů je ověřený – jinak by hra nemohla dávat hvězdičky ani radit.
- Nezačíná uprostřed řešení. Žádný stav, do kterého se z úlohy dá dojet, není od cíle dál než start. Kdyby byl, hráč by mohl „omylem“ dojet do těžší úlohy, než jakou řeší.
- Má správnou obtížnost a v bance se neopakuje (dvě úlohy ze stejné komponenty jsou vlastně jedna úloha).
8.2Postup generátoru
- Náhodné rozmístění zlaté lodi a 3 až 13 dalších lodí.
- Celá komponenta: prohledávání do šířky najde všechny stavy, do kterých se z rozmístění dá dojet (kapitola 9).
- Vzdálenost od cíle: druhé prohledávání do šířky začne ze všech cílových stavů najednou a každému stavu přiřadí nejmenší počet tahů do cíle.
- Úloha = nejvzdálenější stav. Splňuje druhou podmínku dobré úlohy automaticky. Při shodě vybere generátor stav s abecedně nejmenším zápisem, takže stejná komponenta dá vždy stejnou úlohu.
- Třídění podle nejmenšího počtu tahů do obtížností a vyřazení duplicit a úloh na méně než 2 tahy.
8.3Těžké úlohy jsou vzácné
Generátor hry vyzkoušel za 120 sekund 12 965 náhodných rozmístění a našel 8 772 různých komponent s řešením. Nejtěžší stav komponenty byl u naprosté většiny blízko cíle: ze všech 8 909 komponent, které generátor celkem našel (náhodně i horolezením), jich 7 129 (80 %) mělo nejtěžší stav nejvýš 8 tahů od cíle, jen 350 aspoň 15 tahů a jen 84 aspoň 28 tahů (obtížnost 5).
Vlastní pokus průvodce (1 500 rozmístění s 6 až 13 loďmi) ukázal i vliv počtu lodí: se 6 loďmi mělo řešení 97 % rozmístění, se 13 loďmi jen 43 % – lodě se navzájem zablokují. Samotné náhodné rozmístění bylo od cíle v průměru jen 1,9 až 3,9 tahu daleko; teprve nejvzdálenější stav komponenty dává zajímavou úlohu.
| Lodí celkem | Rozmístění | S řešením | Průměrná vzdálenost startu od cíle | Průměr stavů v komponentě |
|---|---|---|---|---|
| 6 | 195 | 189 (97 %) | 1,9 | 2 657 |
| 8 | 180 | 159 (88 %) | 2,6 | 10 693 |
| 10 | 187 | 150 (80 %) | 2,9 | 15 371 |
| 12 | 162 | 89 (55 %) | 3,9 | 12 296 |
| 13 | 189 | 81 (43 %) | 3,3 | 7 517 |
8.4Horolezení
Horolezení (hill climbing) vychází z nejtěžších nalezených úloh a zkouší malé změny: přidat loď, ubrat loď, přesunout loď jinam. Změnu přijme, když nejmenší počet tahů nové úlohy neklesne; každá nová komponenta jde do sbírky. Generátor hry tak za 540 sekund vyzkoušel 135 840 změn, našel 137 nových úloh a nejtěžší měla 46 tahů.hill climbing
Horolezení se může „zaseknout na kopečku“: žádná malá změna úlohu nezlepší, i když jinde je vyšší vrchol. Proto generátor neleze z jediného místa: po 60 změnách začne znovu z jiné úlohy – ze 40 nejtěžších z náhodné fáze nebo z nově nalezených úloh aspoň na 20 tahů. Úlohy, které cestou vzniknou a jsou o tah lehčí, si také uloží do sbírky.
8.5Banka 3D hry
Do obtížností vybírá generátor úlohy rovnoměrně přes počty tahů (aby obtížnost 2 neměla jen úlohy na 9 tahů) a při stejném počtu tahů dá přednost úlohám s víc loděmi – vypadají jako opravdový přístav. Řešič průvodce znovu nezávisle spočítal nejmenší počet tahů všech 390 úloh přístavu a všech 256 úloh patnáctky; všechny souhlasí s bankou.
| Režim | Úloh | Nejmenší počet tahů | Jak vznikly |
|---|---|---|---|
| Pro děti | 70 | 2–6 | náhodná rozmístění se 4 až 6 loďmi včetně zlaté |
| Úlohy 1 až 3 | 64 v každé | 4–8, 9–14, 15–20 | náhodná rozmístění |
| Úlohy 4 a 5 | 64 a 64 | 21–27, 28–46 | náhodná rozmístění i horolezení |
| Patnáctka 1 a 2 (osmička) | 60 a 60 | 8–16, 20–30 | náhodná řešitelná zamíchání a náhodné procházky od cíle |
| Patnáctka 3 až 5 (4 × 4) | 50, 50 a 36 | 16–28, 30–40, 43–64 | procházky od cíle, obtížnost 5 zcela náhodná řešitelná zamíchání; nejmenší počet tahů z IDA* |
Úloha na 46 tahů není „nejtěžší úloha přístavu 6 × 6“ – je to jen nejtěžší, kterou generátor za pár minut našel. Nejtěžší úloha bez zdí má 51 tahů a k jejímu nalezení bylo potřeba projít všechny úlohy (kapitola 12).
8.6Procvičení
- Úloha = nejvzdálenější stav komponenty náhodného rozmístění; nezačíná uprostřed řešení.
- Těžké úlohy jsou vzácné: 80 % komponent má nejtěžší stav do 8 tahů; nad 33 tahů pomůže jen horolezení.
- Všechny úlohy 3D hry ověřil nezávisle i řešič průvodce.
Prohledávání do šířkymistr a věda
Jak řešič zjistí nejmenší počet tahů? Nejjednodušší spolehlivá metoda je prohledávání do šířky (BFS): ze startu projde všechny stavy na 1 tah, pak všechny na 2 tahy a tak dál. První cílový stav, na který narazí, je nejblíž. Stejný algoritmus spuštěný ze všech cílů najednou spočítá vzdálenost každého stavu – na tom stojí nápověda 3D hry.
Hoďte kámen do vody: vlna se šíří ve stále větších kruzích a břehu se dotkne nejdřív tam, kde je nejblíž. Prohledávání do šířky se šíří grafem stavů stejně – vrstvu po vrstvě.
+Teorie: fronta a vrstvy, proč BFS najde nejkratší řešení, paměť a čas, vlna z cílů, obousměrné prohledávání, hloubka napřed
9.1Fronta a vrstvy
Prohledávání do šířky potřebuje dvě věci: frontu stavů, které čekají na zpracování, a seznam objevených stavů (aby žádný nezpracovalo dvakrát). U každého objeveného stavu si pamatuje, odkud do něj přišlo – podle toho se na konci zpětně poskládá řešení.breadth-first search, queue
- Do fronty vlož start a označ ho jako objevený.
- Vyber stav ze začátku fronty. Je-li cílový, skonči – cesta k němu je nejkratší.
- Pro každý tah z něj: když vzniklý stav ještě není objevený, označ ho, zapamatuj si předchůdce a vlož ho na konec fronty.
- Opakuj od kroku 2. Když se fronta vyprázdní a cíl nebyl nalezen, úloha nemá řešení.
9.2Proč najde nejkratší řešení
Fronta zpracovává stavy v pořadí, ve kterém byly objeveny: nejdřív start (vzdálenost 0), pak všechny stavy na 1 tah, pak na 2 tahy… Stav ve vzdálenosti k + 1 se do fronty dostane až za všemi stavy ve vzdálenosti k. Proto první objevený cílový stav leží v nejmenší možné vzdálenosti – žádný bližší cíl neexistuje, jinak by byl objeven dřív.
Nejkratší řešení úlohy z laboratoře je ukázkový Řetěz překážek (kapitola 4). Zlaté lodi brání J a G, oběma ř6, kde stojí M; M potřebuje místo, které uvolní I; I potřebuje místo po H; H potřebuje místo po A; A potřebuje místo po B a B po C. Proto řešení začíná daleko od zlaté lodi – tahem C→1 v řadě 1. Prohledávání do šířky na to přijde samo, bez jakékoli strategie: prostě zkusí všechno.
9.3Paměť a čas
Každý stav se zpracuje jednou a každý tah se zkusí dvakrát (z obou konců hrany), takže čas roste s počtem stavů a hran a paměť s počtem stavů. U přístavu 6 × 6 je to snadné – největší komponenta v bance 3D hry má 79 140 stavů. Osmičku (181 440 stavů) prohledá řešič průvodce celou za necelou sekundu. Patnáctka má přes deset bilionů stavů: úplné prohledání do šířky dokončili Korf a Schultze v roce 2005 a stavy si museli ukládat na disky, protože by se nevešly do paměti.
Zde \(|S|\) je počet stavů a \(|H|\) počet hran (tahů mezi nimi).
9.4Vlna z cílů – mapa vzdáleností
Když na začátku vložíte do fronty všechny cílové stavy najednou, vlna se šíří od cíle a každému stavu přiřadí jeho vzdálenost do cíle \(d(s)\). Protože je graf neorientovaný, je to přesně nejmenší počet tahů ze stavu \(s\) do cíle. Tuhle mapu si 3D hra spočítá pro komponentu každé úlohy: nápověda pak vybere tah do stavu se vzdáleností o 1 menší a generátor (kapitola 8) najde nejvzdálenější stav.
Z mapy vzdáleností plyne, že jeden špatný tah stojí nejvýš dva tahy navíc: tah jde vrátit, takže stav po něm je od cíle nejvýš o 1 dál. Bloudění se ale sčítá – a když v každém stavu vede blíž k cíli jen asi pětina tahů (Tab. 5.1), je špatných tahů hodně.
9.5Obousměrné prohledávání
Počet stavů v okolí startu roste s hloubkou rychle. Obousměrné prohledávání pošle dvě vlny – ze startu a z cíle – a skončí, když se potkají. Každá dojde jen do poloviční hloubky. U osmičky je od cíle do hloubky 15 jen 7 279 stavů, kdežto do hloubky 30 jich je 181 438 – skoro všechny. Pro pozici vzdálenou 30 tahů tak dvě poloviční vlny projdou zhruba desetkrát méně stavů než jedna celá.bidirectional search
9.6Hloubka napřed
Prohledávání do hloubky jde po jedné cestě, dokud může, a pak se vrací. Potřebuje málo paměti (jen aktuální cestu), ale nemusí najít nejkratší řešení. Iterativní prohlubování to spojí: opakuje prohledávání do hloubky s mezí 1, 2, 3, … tahů. Najde nejkratší řešení a paměti potřebuje málo; Richard Korf v roce 1985 ukázal, že opakování ho stojí jen málo času navíc. S heuristikou z něj vznikne IDA* (kapitola 10).depth-first search, iterative deepening
9.7Procvičení
- BFS: fronta + objevené stavy + předchůdci; vrstvy podle vzdálenosti, první cíl je nejbližší.
- Vlna ze všech cílů dá mapu vzdáleností – z ní radí nápověda 3D hry.
- Obousměrné prohledávání a iterativní prohlubování šetří čas, resp. paměť.
Heuristikymistr a věda
Prohledávání do šířky zkouší všechno stejně pečlivě, a proto na patnáctce nestačí. Chytřejší algoritmy používají heuristiku – odhad, kolik tahů ještě zbývá. Když odhad nikdy nepřecení skutečnost, najde A* i IDA* pořád nejkratší řešení, jen prozkoumá stokrát i tisíckrát méně stavů.
Kdo hledá cestu v cizím městě, nechodí do všech ulic stejně. Dívá se, kde je cíl, a dává přednost ulicím, které vedou tím směrem. Heuristika je taková buzola – a dobrá buzola nesmí lhát, že je cíl blíž, než je.
+Teorie: odhad a přípustnost, manhattanská vzdálenost, lineární konflikty, A*, IDA*, databáze vzorů, heuristika pro přístav
10.1Odhad, který nepřeceňuje
Heuristika \(h(s)\) je odhad nejmenšího počtu tahů ze stavu \(s\) do cíle. Je přípustná, když nikdy nepřecení skutečnou vzdálenost \(d(s)\). Přípustné heuristiky vznikají „uvolněním pravidel“: spočítáte, kolik tahů by bylo potřeba, kdyby hlavolam byl jednodušší – a protože skutečný hlavolam je těžší, potřebuje aspoň tolik.admissible heuristic
10.2Manhattanská vzdálenost
Uvolněné pravidlo: dlaždice se smí posunout na sousední pole, i když je obsazené. Pak každá dlaždice potřebuje přesně tolik tahů, kolik je řádků a sloupců mezi jejím polem a cílovým polem. Součet přes všechny dlaždice je manhattanská vzdálenost (jako cesta taxíkem v pravoúhlé síti ulic). Každý skutečný tah posune jednu dlaždici o jedno pole, takže se součet změní nejvýš o 1 – heuristika je přípustná. Slabší (ale také přípustná) je počet dlaždic mimo své místo: každá z nich se musí pohnout aspoň jednou.Manhattan distance, misplaced tiles
10.3Lineární konflikty
Když jsou dvě dlaždice ve své cílové řadě, ale v obráceném pořadí, nemohou se v řadě předběhnout. Jedna z nich musí řadu opustit a vrátit se – to jsou aspoň 2 tahy navíc, které manhattanská vzdálenost nevidí. Lineární konflikty přičtou za každou řadu a sloupec 2 · (počet dlaždic ve své cílové řadě − délka nejdelší rostoucí podposloupnosti); výsledek je stále přípustný.linear conflict
10.4A*
Algoritmus A* (Peter Hart, Nils Nilsson a Bertram Raphael, 1968) rozvíjí stavy podle součtu \(f = g + h\): kolik tahů už stav stál od startu a kolik jich podle odhadu ještě zbývá. Stavy s malým \(f\) jdou první. S přípustnou heuristikou najde A* nejkratší řešení – a čím přesnější odhad, tím méně stavů rozvine. S \(h = 0\) je to přesně prohledávání do šířky.A* search
| Pozice | Do šířky (h = 0) | A*, mimo místo | A*, manhattanská | A*, manhattanská + konflikty | IDA*, manhattanská + konflikty |
|---|---|---|---|---|---|
| osmička, 31 tahů | 181 439 | 121 527 | 6 790 | 3 821 | 8 970 |
| osmička, 20 tahů | 40 415 | 2 260 | 462 | 222 | 241 |
| patnáctka, 28 tahů | přes 400 000 | 203 047 | 3 859 | 1 885 | 3 362 |
| patnáctka, 36 tahů | přes 400 000 | přes 400 000 | 4 503 | 1 274 | 8 612 |
10.5IDA*
A* si musí pamatovat všechny objevené stavy – u těžkých pozic patnáctky jich jsou miliony. IDA* (Richard Korf, 1985) spojuje A* s iterativním prohlubováním (kapitola 9): prohledává do hloubky, ale jen stavy s \(f\) nejvýš rovným mezi; když cíl nenajde, zvýší mez na nejmenší \(f\), které přesáhlo. Paměti potřebuje jen na aktuální cestu. Korf ji v roce 1985 použil k nalezení nejkratších řešení náhodných pozic patnáctky. Generátor 3D hry jí spočítal nejmenší počet tahů všech 136 úloh patnáctky 4 × 4.
U osmičky na 31 tahů začíná IDA* s mezí 23 (heuristika startu) a pokračuje 25, 27, 29, 31. Každý tah změní g o 1 a manhattanskou vzdálenost o +1, nebo −1, takže f se změní o 0, nebo o 2 – lichost f se nemění. Mez proto roste vždy o 2 a IDA* potřebuje jen 5 opakování místo 9.
10.6Databáze vzorů
Ještě silnější odhad dávají databáze vzorů (Joseph Culberson a Jonathan Schaeffer, 1998): předem se úplně prohledá zjednodušený hlavolam, ve kterém záleží jen na několika dlaždicích, a vzdálenosti se uloží do tabulky. Podle jejich článku to u patnáctky s IDA* zmenšilo počet prohledaných stavů na sadě 100 pozic víc než tisíckrát oproti samotné manhattanské vzdálenosti.pattern database
10.7Heuristika pro přístav
Přípustný odhad pro přístav je jednoduchý: \(h = 1 + \text{počet lodí v cestě}\) (a 0 v cíli) – každá loď v cestě se musí pohnout a zlatá loď také. 3D hra ho ale nepotřebuje: komponenty úloh mají nejvýš desítky tisíc stavů a prohledávání do šířky je projde celé za zlomek sekundy. Heuristiky jsou nutné až tam, kde se graf stavů do paměti nevejde – u patnáctky a větších desek.
Manhattanskou vzdálenost používejte i při hraní: dlaždice, která je daleko od svého místa, bude stát hodně tahů. Když se rozhodujete mezi dvěma tahy, ten, který součet zmenší, bývá lepší – ale ne vždy (lineární konflikty, Obr. 10.2).
10.8Procvičení
- Přípustná heuristika nepřeceňuje; vzniká uvolněním pravidel (manhattanská vzdálenost, lineární konflikty).
- A* rozvíjí podle g + h; IDA* totéž s malou pamětí, meze rostou o 2.
- Lepší odhad = méně stavů: u nejtěžší osmičky 3 821 místo 181 439.
Složitostmistr a věda
Na desce 6 × 6 počítač vyřeší každou úlohu za zlomek sekundy. Co když ale deska poroste? Teorie složitosti třídí úlohy podle toho, jak rychle roste potřebný čas a paměť. Posuvné hlavolamy pokrývají celou škálu: řešitelnost patnáctky je snadná (třída P), nejkratší řešení patnáctky je NP-těžké a vyjetí v dopravním hlavolamu je PSPACE-úplné.
Osmička má 181 440 stavů, patnáctka deset bilionů, deska 5 × 5 přes sedm kvadrilionů. Každý řádek a sloupec navíc znásobí počet stavů víc, než kolik je zrnek písku na pláži. Proti takovému růstu nepomůže ani nejrychlejší počítač – pomůže jen chytřejší matematika.
+Teorie: velikost vstupu a růst, třída P, NP a nejkratší řešení patnáctky, PSPACE a dopravní hlavolamy, co to znamená pro hráče
11.1Velikost vstupu a růst
Teorie složitosti se neptá, jak těžká je jedna konkrétní úloha, ale jak roste práce, když roste velikost vstupu – tady strana desky n. Algoritmus je polynomiální, když jeho čas roste nejvýš jako mocnina n (třeba n3); takové úlohy považujeme za „rychle řešitelné“. Počet stavů ale roste mnohem rychleji než jakákoli mocnina:computational complexity
11.2Třída P: řešitelnost patnáctky
Je zamíchaná deska n × n řešitelná? Stačí spočítat inverze a řádek volného pole (kapitola 6) – na to stačí porovnat každou dvojici dlaždic, tedy řádově n4 operací. Úloha patří do třídy P (polynomiální čas). A nejen to: metoda Řádek po řádku řešitelnou desku i seřadí na řádově n3 tahů – každá dlaždice urazí nejvýš řádově n polí a každé pole stojí jen několik tahů.class P
11.3NP: nejkratší řešení patnáctky
Těžší je otázka „dá se deska seřadit nejvýš na k tahů?“. Když někdo řešení ukáže, ověří se snadno – stačí tahy přehrát. Takové úlohy tvoří třídu NP. Daniel Ratner a Manfred Warmuth dokázali (konference 1986, časopis 1990), že najít nejkratší řešení zobecněné patnáctky n × n je NP-těžké; otázka „do k tahů?“ je NP-úplná. Erik Demaine a Mikhail Rudoy později (2017) podali jednodušší důkaz. Pokud P ≠ NP – a to se většinou předpokládá, ale nikdo to nedokázal – neexistuje rychlý algoritmus na nejkratší řešení velkých desek.NP-hard, NP-complete
Na patnáctce z kapitoly 6 rozhodnete o řešitelnosti za pár vteřin. Seřadit ji metodou Řádek po řádku zvládnete také. Ale nejkratší řešení i pro 4 × 4 hledá počítač heuristickým prohledáváním (kapitola 10) – a pro velké desky na to rychlý postup nejspíš neexistuje.
11.4PSPACE: dopravní hlavolamy a posuvné bloky
Třída PSPACE obsahuje úlohy, které jde vyřešit s pamětí rostoucí polynomiálně – i když čas může růst exponenciálně. Do ní patří i otázka „dá se z tohoto stavu dojet do cíle?“ pro posuvné hlavolamy: algoritmus může procházet tahy a pamatovat si jen aktuální stav a počítadlo.PSPACE-complete
- Gary W. Flake a Eric B. Baum (2002): u dopravního hlavolamu na libovolně velké desce je rozhodnout, zda určené auto může vyjet, PSPACE-úplné – tedy nejtěžší úloha celé třídy.
- John Tromp a Rudi Cilibrasi (2005): zůstává PSPACE-úplné, i když jsou všechna auta dlouhá jen 2.
- Robert A. Hearn a Erik D. Demaine (2005): klasické posuvné bloky (jako čínský hlavolam) jsou PSPACE-těžké, i když jsou všechny kusy jen obdélníčky 1 × 2. Použili model „nedeterministické omezující logiky“, se kterým pak dokázali složitost mnoha dalších her (kniha Games, Puzzles, and Computation, 2009).
Proč jsou dopravní hlavolamy „těžší“ než patnáctka? U patnáctky má každá řešitelná pozice řešení na řádově n3 tahů, takže krátký „důkaz řešitelnosti“ vždy existuje. Kdyby měl i každý řešitelný dopravní hlavolam krátké řešení, ležel by problém v NP; PSPACE-úplnost proto naznačuje (pokud NP ≠ PSPACE), že některé úlohy na velkých deskách potřebují řešení nesmírně dlouhá.
11.5Co to znamená pro hráče
Složitost mluví o deskách, které rostou do nekonečna. Přístav 6 × 6 má konečně mnoho úloh a počítač je umí projít všechny (kapitola 12). Pro hráče z teorie plyne hlavně ponaučení: obecný rychlý recept neexistuje. Techniky z kapitol 3–5 jsou užitečné návyky, ne algoritmus, který vždy najde nejkratší řešení.
„NP-těžké“ neznamená „nejde vyřešit“. Patnáctku 4 × 4 počítač řeší optimálně běžně; osmičku zvládne prohledávání do šířky celou. Složitost říká, že s růstem desky práce exploduje – ne že malé případy jsou nemožné.
11.6Procvičení
- Řešitelnost patnáctky n × n: P (inverze); nejkratší řešení: NP-těžké (Ratner a Warmuth 1990).
- Dopravní hlavolamy a posuvné bloky na velké desce: PSPACE-úplné (Flake a Baum 2002, Hearn a Demaine 2005).
- Složitost mluví o růstu desky; pevný přístav 6 × 6 počítač vyřeší celý.
Nejtěžší úlohy a počítačmistr a věda
Přístav 6 × 6 má konečně mnoho úloh, a tak je počítač umí projít všechny. Výčty ukázaly, že nejtěžší úloha bez zdí potřebuje 51 tahů. V této kapitole si ji zahrajete, uvidíte mapu vzdáleností jejích 4 780 stavů a pochopíte, jak z takové mapy radí trenér 3D hry.
Horolezci znají nejvyšší horu světa přesně, protože změřili všechny vrcholy. U dopravních hlavolamů 6 × 6 se stalo totéž: počítač „změřil“ všechny úlohy a našel tu nejvyšší. Vylezete na ni?
+Teorie: úplné výčty, nejtěžší úloha 51 tahů, mapa vzdáleností, jak radí trenér, nejtěžší a nejzajímavější
12.1Úplné výčty
Úloha dopravního hlavolamu 6 × 6 je dána rozmístěním aut, a těch je konečně mnoho. Sébastien Collette, Jean-François Raskin a Frédéric Servais (konference Computers and Games 2006) zapsali pravidla hry ve výrokové logice a symbolickými metodami ověřování modelů roztřídili všechny počáteční pozice podle délky nejkratšího řešení. Podle encyklopedických přehledů potřebuje nejtěžší počáteční pozice měřená v krocích 93 kroků.exhaustive enumeration
Michael Fogleman (2018) sestavil databázi všech úloh 6 × 6, které považoval za zajímavé. Obsahuje 2 577 412 „zajímavých“ úloh, které pokrývají 9 698 093 879 dosažitelných stavů. Počítá tahy (posun auta o libovolný počet polí) a jeho nejtěžší úloha bez zdí potřebuje 51 tahů; s jednou pevnou zdí 60 tahů, se dvěma 58.
Co je „zajímavá“ úloha, si Fogleman definoval podobně jako generátor 3D hry (kapitola 8): žádný řádek není celý zaplněný vodorovnými auty a žádný sloupec svislými, v řadě červeného auta není jiné vodorovné auto, z každé komponenty se bere jen jedna úloha – a to taková, že žádný stav, do kterého se z ní dá dojet, není těžší. Navíc žádné auto není zbytečné: odebrání kteréhokoli auta řešení změní.
12.2Nejtěžší úloha v přístavu
Řešič průvodce úlohu ověřil nezávisle: komponenta má 4 780 stavů (stejně jako ve Foglemanově databázi) a 18 691 hran, cílových stavů je 199 a nejvzdálenější stavy jsou od cíle 51 tahů. Nejkratší řešení má 81 kroků; v krocích je ale nejvzdálenější stav téže komponenty jiný a potřebuje 83 kroků – nejtěžší úloha závisí na tom, co počítáte (kapitola 2).
| Volná cesta | Uvolnit cestu | Řetěz překážek | Krok zpět | Celkem |
|---|---|---|---|---|
| 4 | 8 | 31 | 8 | 51 |
Řetěz překážek tvoří tři pětiny řešení a zlatá loď couvne celkem čtyřikrát – mezi zlatou lodí a ústím se lodě střídají znovu a znovu.
12.3Mapa vzdáleností
Prohledávání do šířky ze všech 199 cílů (kapitola 9) přiřadí každému stavu vzdálenost od cíle. Histogram ukazuje, kde se v komponentě dá bloudit. Nejvíc stavů (551) je jen 3 tahy od cíle. Cestou od startu jsou ale dvě úzká hrdla: ve vzdálenostech 36 až 40 tahů je jen 3 až 7 stavů a ve vzdálenostech 13 až 21 jen 16 až 24 stavů. Každé nejkratší řešení musí projít oběma – a kdo hrdlo mine, bloudí v širokých „sálech“ kolem něj (41 až 49 a 22 až 34 tahů od cíle).
12.4Jak radí trenér 3D hry
- Při načtení úlohy hra spočítá komponentu a mapu vzdáleností (zlomek sekundy).
- První nápověda ukáže loď, kterou začíná některý tah do stavu o 1 bližšího k cíli.
- Druhá nápověda pojmenuje techniku tahu (Volná cesta, Uvolnit cestu, Řetěz překážek, Krok zpět) a ukáže směr – s odkazem na kapitolu průvodce.
- Třetí nápověda tah provede.
Protože se mapa počítá pro celou komponentu, funguje nápověda odkudkoli – i když hráč zabloudil daleko od nejkratšího řešení. A protože každý tah jde vrátit, hráč se z každého stavu dostane do cíle.
V úloze na 51 tahů nehledejte celé řešení najednou. Rozdělte ho na etapy: kdy se zlatá loď posune o kus doprava, co se musí stát předtím a co potom. Laboratoř ukazuje vzdálenost po každém tahu – když po pěti tazích klesla o pět, jste na nejkratší cestě.
12.5Nejtěžší není totéž co nejzajímavější
Nejmenší počet tahů je objektivní míra, ale lidé vnímají obtížnost i jinak: kolik lodí je třeba sledovat, jak dlouhé řetězy, kolik Kroků zpět, jak snadno se zabloudí. Nejtěžší úloha má ze všech stavů nejkratšího řešení v průměru 28 % tahů, které vedou blíž k cíli – víc než úlohy obtížnosti 3 až 5 z 3D hry (22–23 %, Tab. 5.1). Jednotlivé kroky tedy nejsou zrádnější; je jich jen hodně a navazují na sebe.
„Nejtěžší“ vždy platí jen pro danou desku, daná pravidla a dané počítání. Se zdmi, na větší desce nebo při počítání kroků vychází jiná úloha a jiné číslo (51 tahů, 60 tahů s jednou zdí, 93 kroků).
12.6Procvičení
- Přístav 6 × 6 je konečný: úplné výčty našly nejtěžší úlohu bez zdí – 51 tahů, 4 780 stavů (Fogleman 2018).
- Mapa vzdáleností z prohledávání do šířky dává nápovědu odkudkoli.
- „Nejtěžší“ závisí na pravidlech a počítání: 51 tahů, 93 kroků, 60 tahů se zdí.
Slovníček
Česká hesla s anglickým termínem. Hledat lze v obou jazycích.
Vzorce a přehledy
Techniky trenéra
| Technika | Co dělá | Kapitola |
|---|---|---|
| Volná cesta | zlatá loď jede doprava, nejlépe rovnou k ústí | 3 |
| Uvolnit cestu | loď v cestě uhne – člun nahoru nebo dolů, nákladní loď vždy dolů do řad 4–6 | 3 |
| Řetěz překážek | pohnout lodí mimo cestu, aby mohla uhnout loď v cestě; plánovat stromem překážek odzadu | 4 |
| Krok zpět | zlatá loď couvne nebo jiná loď vjede do cesty, aby uvolnila pole jiné lodi | 5 |
| Řádek po řádku | patnáctka: seřadit první řádek, pak první sloupec, a desku tak zmenšovat | 6 |
| Poslední dvojice | poslední dvě dlaždice řádku: čtyřka na místo trojky, trojka pod ni, pak oba dva tahy | 6 |
Vzorce na jednom místě
Důležitá čísla
| Údaj | Hodnota | Zdroj |
|---|---|---|
| řešitelné pozice osmičky / patnáctky | 181 440 / 10 461 394 944 000 | 9!/2 a 16!/2 |
| nejtěžší osmička (tahy po jedné dlaždici) | 31 tahů, 2 pozice | úplné prohledání řešičem průvodce |
| nejtěžší patnáctka | 80 tahů, 17 pozic | Brüngger a kol. 1999, Korf a Schultze 2005 |
| čínský hlavolam: tahy cestou / přímé tahy / kroky | 81 / 90 / 116 | řešič průvodce (81 také Gardner 1964) |
| čínský hlavolam: dosažitelné stavy / všechna rozestavení | 25 955 / 65 880 | řešič průvodce |
| nejtěžší úloha 6 × 6 bez zdí | 51 tahů, 4 780 stavů | Fogleman 2018, ověřeno řešičem průvodce |
| nejtěžší úloha banky 3D hry | 46 tahů | generátor hry, ověřeno řešičem průvodce |
| úlohy 3D hry | 70 + 5 × 64 přístav, 256 patnáctka | banka hry k 10. 11. 2026 |
Zdroje a předpoklady
Historie a výsledky výzkumu
- J. Slocum, D. Sonneveld: The 15 Puzzle, 2006, ISBN 1-890980-15-3 – Noyes P. Chapman, Matthias Rice, horečka 1880, Loydovy nepravdivé nároky. Ověřeno 10. 11. 2026.
- Patentová přihláška N. P. Chapmana z 21. 2. 1880; patent E. U. Kinseyho US 207,124 z 20. 8. 1878 (podle encyklopedického hesla „15 puzzle“ a stránek J. Scherphuise o patnáctce). Ověřeno 10. 11. 2026.
- W. W. Johnson, W. E. Story: Notes on the „15“ Puzzle I a II. American Journal of Mathematics 2 (4), 1879, s. 397–404. Ověřeno 10. 11. 2026.
- D. Ratner, M. Warmuth: konference AAAI 1986; The (n²−1)-puzzle and related relocation problems. Journal of Symbolic Computation 10 (2), 1990, s. 111–137. E. D. Demaine, M. Rudoy: A simple proof that the (n²−1)-puzzle is hard, arXiv 1707.03146, 2017. Ověřeno 10. 11. 2026.
- A. Brüngger, A. Marzetta, K. Fukuda, J. Nievergelt: The parallel search bench ZRAM and its applications. Annals of Operations Research 90, 1999, s. 45–63 – nejtěžší pozice patnáctky potřebují 80 tahů. Ověřeno 10. 11. 2026.
- R. E. Korf, P. Schultze: Large-scale parallel breadth-first search. AAAI 2005, s. 1380–1385 – úplné prohledání patnáctky do šířky; 17 pozic ve vzdálenosti 80 (podle přehledu H. Kociemby a encyklopedického hesla). Ověřeno 10. 11. 2026.
- R. E. Korf: Depth-first iterative-deepening: an optimal admissible tree search. Artificial Intelligence 27, 1985, s. 97–109. Ověřeno 10. 11. 2026.
- P. E. Hart, N. J. Nilsson, B. Raphael: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4 (2), 1968, s. 100–107. Ověřeno 10. 11. 2026.
- J. C. Culberson, J. Schaeffer: Pattern databases. Computational Intelligence 14 (3), 1998, s. 318–334. Ověřeno 10. 11. 2026.
- A. Reinefeld: Complete solution of the eight-puzzle and the benefit of node ordering in IDA*. IJCAI 1993, s. 248–253 (počty pozic osmičky podle vzdálenosti, posloupnost A089473 v OEIS – shodují se s výpočtem průvodce). Ověřeno 10. 11. 2026.
- Čínský hlavolam: patent H. Waltona (US 516,035, 1893), L. W. Hardy (patent podaný 1907, udělený 1912; Pennant Puzzle 1909), anglický patent J. H. Fleminga (1934), Chua-žung tao (30. léta), řešení na 81 tahů – M. Gardner, Mathematical Games, Scientific American, únor 1964 (podle encyklopedického hesla „Klotski“). Ověřeno 10. 11. 2026.
- Nob Jošigahara (1936–2004), dopravní hlavolam ze 70. let, prodej v USA od roku 1996 (podle encyklopedických hesel „Nob Yoshigahara“ a „Rush Hour (puzzle)“). Ověřeno 10. 11. 2026.
- G. W. Flake, E. B. Baum: Rush Hour is PSPACE-complete, or „Why you should generously tip parking lot attendants“. Theoretical Computer Science 270 (1–2), 2002, s. 895–911. Ověřeno 10. 11. 2026.
- J. Tromp, R. Cilibrasi: Limits of Rush Hour Logic Complexity, 2005 (auta délky 2; podle encyklopedického hesla „Rush Hour (puzzle)“). Ověřeno 10. 11. 2026.
- R. A. Hearn, E. D. Demaine: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science 343 (1–2), 2005, s. 72–96; kniha Games, Puzzles, and Computation, A K Peters 2009. Ověřeno 10. 11. 2026.
- S. Collette, J.-F. Raskin, F. Servais: On the symbolic computation of the hardest configurations of the RUSH HOUR game. Computers and Games 2006, LNCS 4630, Springer 2007, s. 220–233. Ověřeno 10. 11. 2026.
- M. Fogleman: Solving Rush Hour, the Puzzle, červenec 2018 (michaelfogleman.com/rush) – 2 577 412 úloh, 9 698 093 879 stavů, nejtěžší bez zdí 51 tahů (zápis GBBoLoGHIoLMGHIAAMCCCKoMooJKDDEEJFFo, 4 780 stavů), s jednou zdí 60 a se dvěma 58 tahů. Ověřeno 10. 11. 2026.
Vlastní výpočty průvodce
Laboratoře, mise, tabulky a schémata počítá jedno jádro (soubor laboratoří, bloky PH-ENGINE a PH-DRAW); stejný kód spouštějí v node pomocné skripty v _obsah/. Řešič průvodce nezávisle přepočítal nejmenší počet tahů všech 390 úloh přístavu a 256 úloh patnáctky z banky 3D hry (stav k 10. 11. 2026) a všechny souhlasí; u 36 nejtěžších pozic patnáctky (43 až 64 tahů) to vlastnímu IDA* trvalo přes půl hodiny. Statistiky technik a měr obtížnosti (Tab. 3.1, 5.1) vycházejí z jednoho nejkratšího řešení každé úlohy – jiné nejkratší řešení může mít tahy rozdělené mezi techniky trochu jinak. Pokus s náhodnými rozmístěními (Tab. 8.1) má pevné semínko a je opakovatelný; čísla o generátoru hry pocházejí z jeho protokolu. Pozice v minihrách vybírá a vyhodnocuje stejný kód, který je v laboratořích; řešitelnost v minihře o patnáctce se počítá z inverzí, třídy složitosti podle citovaných článků.
Co zůstává nejisté
Přesný rok, kdy Chapman hlavolam poprvé ukázal (uvádí se kolem roku 1874), a délku horečky (uvádí se několik měsíců roku 1880) prameny podávají přibližně. Která ze dvou poznámek z roku 1879 dokázala nemožnost a která možnost, se v sekundárních zdrojích liší. Loydova odměna 1 000 dolarů je známa z jeho vlastních vyprávění. Kde a kdy vznikla nejstarší verze čínského hlavolamu, není známo; počty tahů v patentech a starších knihách se liší podle počítání i rozestavení. U dopravního hlavolamu prameny uvádějí jen „70. léta“; údaj 93 kroků pro nejtěžší pozici známe z encyklopedického přehledu a nepodařilo se nám ho ověřit přímo v textu článku Collette, Raskina a Servaise. Autorství heuristiky lineárních konfliktů průvodce neuvádí, protože se ho nepodařilo ověřit. Podíl „dobrých tahů“ (Tab. 5.1) je vlastní míra průvodce, ne převzatý výsledek výzkumu.