← Herna
Vyplutí z přístavu ve 3D
📖 Průvodce
📖 Průvodce: Posuvné hlavolamy12 kapitol hned pod hrou ↓
Posuvné hlavolamy🧭 Další průvodci a hry
INTERAKTIVNÍ PRŮVODCE · LISTOPAD 2026

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.

tah–
nejmenší–
stavů–
technika–
Úvodem

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

Tab. 0.1Kapitoly, úroveň a co se v nich naučíte
KapitolaÚroveňCo se naučíte
1 Pojmy a historiezákladyco 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 stavzákladytah 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 cestuzákladyčtení od ústí, kdo stojí v cestě, kam musí uhnout – nahoru, nebo dolů podle délky lodi
4 Řetěz překážekzákladykdo komu brání, strom závislostí, plánování od konce, slepé uličky
5 Krok zpětpokročilíproč je někdy nutné pozici zhoršit, dva druhy kroku zpět, odhad obtížnosti úlohy
6 Patnáctka a osmičkapokroč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í úlohpokroč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 šířkymistr a vědafronta a vrstvy, proč BFS dává nejmenší počet tahů, velikost stavových prostorů, obousměrné prohledávání
10 Heuristikymistr a vědaA* a IDA*, manhattanská vzdálenost, lineární konflikty, databáze vzorů, „Boží číslo“ 31 a 80
11 Složitostmistr a vědaNP-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ědanejtěžší 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).

Tab. 0.2Režimy a obtížnosti 3D hry a kapitoly, které k nim patří
Režim / obtížnostNejmenší počet tahů úlohyKapitoly
Pro děti2–61, 3
Úlohy 14–83
Úlohy 29–143, 4
Úlohy 315–204, 5
Úlohy 421–275, 8
Úlohy 528–465, 12
Patnáctkaosmička 3 × 3 a patnáctka 4 × 4, jen řešitelná zamíchání6, 10
Denní výzva je jedna úloha obtížnosti 3 až 4, v daný den stejná pro všechny. Rozdělení úloh v bance hry ukazuje kapitola 8.

Čtyři druhy rámečků

Příklad Řešený krok nebo výpočet

Konkrétní pozice, tah nebo výpočet, který si můžete ověřit v laboratoři.

Z historie

Kdo hlavolam vymyslel, kdy vyšel a co o něm zjistili matematici a informatici.

Mistrovská pomůcka

Rychlé pravidlo, zkratka nebo návyk, který používají zkušení hráči.

Pozor

Č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.

Hrajte

Vyplutí z přístavu ve 3D

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.

Jak to funguje: každá úloha v bance je ověřená prohledáním do šířky – hra zná její nejmenší počet tahů a ukazuje ho jako „tahy / nejmenší“. Tah je posun jedné lodi o libovolný počet polí jedním směrem (kapitola 2). Hvězdičky: ★★★ za vyřešení na nejmenší počet tahů, ★★ nejvýš o čtvrtinu tahů víc (vždy alespoň o 2), ★ za každé vyřešení. Nápověda trenéra má tři stupně: první klepnutí ukáže loď, druhé pojmenuje techniku a ukáže směr – Volná cesta, Uvolnit cestu, Řetěz překážek, Krok zpět, v patnáctce Řádek po řádku a Poslední dvojice – vždy s odkazem na kapitolu, třetí tah provede. Trenér vychází z řešiče: zná vzdálenost každého stavu od cíle a radí tah, který vede o krok blíž (kapitola 12); v patnáctce pomáhá heuristické prohledávání (kapitola 10). Po vyřešení zlatá loď vypluje ústím, zazní siréna a krátký ohňostroj. Rekordy, vyřešené úlohy a série denních výzev se ukládají jen ve vašem prohlížeči.
Část IZáklady
1

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.

Posuň loď
Klepněte na loď – zelené tečky ukážou pole, kam může dojet. Klepnutím na tečku loď posunete. Tah je posun o libovolný počet polí, krok o jedno pole; laboratoř počítá obojí. Vyveďte zlatou loď Z k ústí vpravo ve třetí řadě.
LABORATOŘ
Model: přístav 6 × 6, lodě dlouhé 2 nebo 3 pole jezdí jen po své délce a zastaví o jinou loď nebo o nábřeží. Úloha je vyřešená, když zlatá loď dojede k ústí (pole ř3s5 a ř3s6). Nejmenší počet tahů i kroků spočítal řešič průvodce prohledáním do šířky (kapitola 9). Nápověda ukáže jeden tah, který vede o krok blíž k cíli.
+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.

121215116587109413143
patnáctka – 15 dlaždic, jedno volné pole
ZABCDEFGHI
dopravní hlavolam – lodě jezdí po své délce
★
bloky různých tvarů – velký čtverec ven dole
Obr. 1.1Tři rodiny posuvných hlavolamů. Vlevo patnáctka (zamíchaná), uprostřed úloha obtížnosti 3 z banky 3D hry, vpravo tradiční čínský hlavolam s velkým čtvercem (hvězdička) v počátečním rozestavení.

1.2Tři rodiny

Tab. 1.1Rodiny posuvných hlavolamů v průvodci
RodinaDeska a kusyJak se kusy pohybujíCílKapitoly
patnáctka a osmička4 × 4 (3 × 3), stejné čtvercové dlaždice s čísly, jedno volné poledlaždice vedle volného pole se do něj posuneseřadit čísla, volné pole vpravo dole6, 10
dopravní hlavolamy6 × 6, obdélníky 1 × 2 a 1 × 3jen po své délce, o libovolný počet volných polívyvést určený blok otvorem v okraji3–5, 12
bloky různých tvarů4 × 5, kusy 2 × 2, 1 × 2, 2 × 1 a 1 × 1libovolným směrem na volná polevelký čtverec otvorem dole ven7

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.

Z historie

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).

Pozor

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č.
123456123456ZABCD
řady 1–6 shora, sloupce 1–6 zleva; oranžově cesta zlaté lodi k ústí
123456123456ZABCD
řešení na 2 tahy: D↓1, pak Z→4
Obr. 1.2Úloha 1 z laboratoře. Vlevo značení řad a sloupců a cesta zlaté lodi k ústí (oranžově) – stojí v ní člun D. Vpravo řešení na dva tahy: D↓1 (o jedno pole dolů) a Z→4 (zlatá loď o čtyři pole doprava k ústí).
Příklad Tahy a kroky úlohy 1

Č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í

1
Svislá nákladní loď posune o 3 pole dolů. Kolik je to tahů a kolik kroků?
1 tah, 3 kroky. Tah je posun jedné lodi jedním směrem o libovolný počet polí, krok je posun o jedno pole.
2
Proč ve třetí řadě přístavu nesmí stát jiná vodorovná loď vpravo od zlaté lodi?
Vodorovná loď jezdí jen po třetí řadě. Stála-li by mezi zlatou lodí a ústím, nemohla by se jí nikdy vyhnout – uhnout může jen doleva nebo doprava, tedy pořád v cestě. Úloha by neměla řešení. (Ani vyplout ona nesmí; ústím projíždí jen zlatá loď.)
3
Kdo vymyslel patnáctku a co o ní tvrdil Sam Loyd?
Podle současného bádání Noyes Palmer Chapman, poštmistr z Canastoty (New York), v 70. letech 19. století; vyráběl se od prosince 1879 a horečka vypukla v roce 1880. Sam Loyd od roku 1891 tvrdil, že je autorem, ale Slocum a Sonneveld (2006) ukázali, že s hlavolamem v té době spojen nebyl.
4
Dá se v posuvném hlavolamu „prohrát“, tedy dostat do pozice, ze které už úloha nejde vyřešit, i když ze startu šla?
Ne. Každý tah jde vrátit opačným tahem. Ze kterékoli pozice, do které jste se ze startu dostali, se tedy můžete vrátit na start a odtud úlohu vyřešit. Špatné tahy jen prodlužují cestu.
5
V čem se liší pohyb kusů v patnáctce, v přístavu a v čínském hlavolamu?
V patnáctce se posouvá vždy jedna dlaždice sousedící s jediným volným polem. V přístavu se loď pohybuje jen po své délce (vodorovná doleva a doprava, svislá nahoru a dolů), ale o libovolný počet polí. V čínském hlavolamu se kusy různých tvarů posouvají libovolným směrem, kam je místo – volná pole jsou dvě.
Co si odnést
  • 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í.
Část IZáklady
2

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í.

Graf stavů malé úlohy
Úloha s 13 loďmi, ze které se dá dostat jen do 24 stavů. Každý kroužek je jeden stav, čára mezi kroužky jeden tah. Stavy jsou seřazené do sloupců podle vzdálenosti od startu. Klepněte na kroužek a pod grafem uvidíte, jak stav vypadá. Přepínačem změňte počítání: po tazích, nebo po krocích.
LABORATOŘ
Model: všechny stavy dosažitelné ze startu našel řešič průvodce prohledáním do šířky; číslo ve sloupci dole je vzdálenost od startu. Oranžová start, zelená cíl (zlatá loď u ústí), oranžové hrany jedna nejkratší cesta. Po tazích vede hrana mezi stavy, které dělí posun jedné lodi o libovolný počet polí, po krocích jen o jedno pole – proto se počet hran i délka cesty liší.
+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)

123456123456ZABC
A↑2: 1 tah = 2 kroky
123456123456ZABC
Z→3: 1 tah = 3 kroky
123456123456ZABC
hotovo: 2 tahy, 5 kroků
Obr. 2.1Úloha 2 z laboratoře v kapitole 1. Tah A↑2 posune člun A o dvě pole nahoru – je to 1 tah, ale 2 kroky. Tah Z→3 jsou 3 kroky. Toto řešení má 2 tahy a 5 kroků. Po krocích jde kratší: A↓1, Z→3 – také 2 tahy, ale jen 4 kroky.

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

Tahy a kroky\[ t \le k \le 4\,t \]

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).

Příklad Nejkratší na tahy není nejkratší na kroky

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á.

Mistrovská pomůcka

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ýš

Horní mez počtu stavů\[ |S| \le \prod_{i=1}^{n} (7 - \ell_i) \]

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

123456123456ZADBCEFGHIJKL
stav 1 = start (10 tahů, 15 kroků)
123456789101112131415161718192021222324012345678910
Obr. 2.2Malá úloha z laboratoře a její graf stavů po tazích: 24 stavů ve sloupcích podle vzdálenosti od startu, 36 hran, jeden cílový stav (zeleně). Oranžově jedna nejkratší cesta – 10 tahů.

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.

Nejmenší počet tahů\[ d(s_0) = \min_{c \in C} \operatorname{dist}(s_0, c) \]

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).

Pozor

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í

1
Kolik poloh má svislý člun ve sloupci o šesti polích a kolik nákladní loď?
Horní konec člunu může být v řadách 1 až 5: 5 poloh. Nákladní loď zabírá 3 pole, horní konec může být v řadách 1 až 4: 4 polohy. Obecně 6 − ℓ + 1 = 7 − ℓ.
2
Řešení má tahy C←1, E←1, F↑2, Z→2. Kolik je to tahů a kolik kroků?
4 tahy, kroků 1 + 1 + 2 + 2 = 6.
3
Zapište stav: zlatá loď v ř3s1–s2, svislý člun A v ř2s3–ř3s3, jinak prázdný přístav.
....../..A.../ZZA.../....../....../...... – první řádek prázdný, ve druhém A ve třetím sloupci, ve třetím Z, Z a A.
4
Proč je graf stavů přístavu neorientovaný a co z toho plyne pro hráče?
Ke každému tahu existuje opačný tah (loď se vrátí stejnou cestou na volná pole, která právě opustila). Hrana tedy vede oběma směry. Pro hráče to znamená, že nic nezkazí natrvalo: z každého dosaženého stavu se dá vrátit a úlohu dokončit.
5
Úloha má nejmenší počet tahů 9. Může mít nejkratší řešení po krocích 40 kroků?
Ne. Nejkratší řešení na 9 tahů má nejvýš 9 · 4 = 36 kroků, takže nejmenší počet kroků je nejvýš 36. Naopak méně než 9 kroků mít nemůže.
Co si odnést
  • 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ů.
Část IITechniky přístavu
3

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.

Která loď první?
V každé pozici je jen jedna loď, jejímž tahem začíná nejkratší řešení. Klepněte na ni. Hra pak ukáže správný tah, jeho techniku a vysvětlení. Za tři správné odpovědi získáte body.
MINIHRA
Správně 0 z 0
Model: 13 pozic z nejkratších řešení úloh 3D hry (pro děti, obtížnosti 1 a 2). Řešič průvodce u každé spočítal vzdálenost všech stavů od cíle a vybral jen pozice, kde všechny nejkratší pokračování začínají tahem jediné lodi. Do vyhodnocení hra nic neprozradí; zelená tečka u ústí jen připomíná cíl.
+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

123456123456ZABCFGDEHI
v cestě stojí G, F a C – všechny tři čluny v řadách 2–3
123456123456ZABCFGDEHI
nahoru nemohou (A, B); dolů jen když E uhne doleva
Obr. 3.1Pozice z nejkratšího řešení úlohy obtížnosti 1 z banky 3D hry, 5 tahů do cíle. Vlevo čtení od ústí: v cestě stojí čluny G, F a C (zvýrazněné). Vpravo plán: G a F musí dolů o 2 pole, k tomu musí nákladní loď E uhnout doleva o 2 pole – a aby mohla, musí C dolů rovnou o 3 pole.

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.
člun ř2–3↑1 nebo ↓2člun ř3–4↑2 nebo ↓1nákladní ř1–3↓3nákladní ř2–4↓2nákladní ř3–5↓1
Obr. 3.2Sloupec se svislou lodí, oranžově pole ve třetí řadě. Vedle čárkovaně polohy, do kterých musí loď dojet, aby třetí řadu uvolnila. Člun má dvě možnosti, nákladní loď jedinou – dolů do řad 4–6.
Posun nutný k uvolnění třetí řady\[ \text{člun:}\ \uparrow (r-1)\ \text{nebo}\ \downarrow (4-r), \qquad \text{nákladní loď:}\ \downarrow (4-r) \]

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:

  1. Jsou potřebná pole volná? Pokud jen na jedné straně, je rozhodnuto. Pokud na žádné, je to Řetěz překážek (kapitola 4).
  2. 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.
  3. Kolik tahů to stojí celkem? Kratší posun není vždy lepší – počítají se tahy, ne pole.
Příklad Úloha z Obr. 3.1

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).

Tab. 3.1Podíl technik v nejkratších řešeních úloh 3D hry (jedno nejkratší řešení každé úlohy, výpočet řešičem průvodce)
ObtížnostÚlohTahů celkemLodí v cestě na startu (průměr)Volná cestaUvolnit cestuŘetěz překážekKrok zpět
pro děti702801,525,0 %37,9 %32,1 %5,0 %
1643821,819,4 %32,7 %42,4 %5,5 %
2647321,914,1 %27,7 %47,4 %10,8 %
3641 1162,111,0 %24,3 %51,6 %13,1 %
4641 4972,19,8 %21,8 %54,4 %14,0 %
5642 1702,69,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.

Mistrovská pomůcka

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í

1
Nákladní loď stojí svisle v řadách 2–4 a kříží třetí řadu. Kam musí?
Dolů o 2 pole, do řad 4–6. Nad třetí řadou jsou jen dvě řady a nákladní loď je dlouhá tři pole, takže nahoru se třetí řadu uvolnit nedá.
2
Člun stojí svisle v řadách 3–4. Jaké má možnosti?
Nahoru o 2 (do řad 1–2), nebo dolů o 1 (do řad 4–5); dolů o 2 (do řad 5–6) také, pokud je místo.
3
Zlatá loď stojí v ř3s1–s2 a cesta je volná. Kolik tahů a kolik kroků zbývá?
1 tah, 4 kroky – zlatá loď dojede ze sloupců 1–2 do sloupců 5–6.
4
Proč v Obr. 3.1 nestačí posunout C o 2 pole dolů, když tím třetí řadu uvolní?
Člun C by stál v ř4s3 a ř5s3. Nákladní loď E (ř4s4–s6) by pak nemohla uhnout doleva o 2 pole a uvolnit sloupce 5 a 6 pro F a G. C by musel ještě jednou dolů – tah navíc. Posun o 3 uvolní třetí řadu i ř4s3 najednou.
5
V cestě stojí dvě nákladní lodě, obě v řadách 1–3, a pod nimi je volno. Kolik nejméně tahů zbývá do konce?
3 tahy: každá nákladní loď dolů o 3 pole (2 tahy) a zlatá loď k ústí (1 tah). Méně to nejde – každá loď v cestě se musí pohnout aspoň jednou a zlatá loď také.
Co si odnést
  • Č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.
Část IITechniky přístavu
4

Ř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.

Strom překážek
Nahoře přístav, pod ním strom: kdo stojí zlaté lodi v cestě, kam může uhnout a kdo mu v tom brání. Větev končící slovem „volno“ ukazuje loď, která se může pohnout hned. Hýbejte loděmi (klepněte na loď a pak na zelenou tečku) a sledujte, jak se strom mění.
LABORATOŘ
Model: tři úlohy obtížnosti 2 z banky 3D hry, každá na 9 tahů. Strom staví laboratoř stejně jako trenér: pro každou loď v cestě najde nejbližší polohu nahoře i dole (vlevo i vpravo), ve které už nepřekáží, a vypíše lodě, které leží na polích, přes která musí projet. Hloubka omezuje, kolik pater stromu se vypíše; „…“ znamená, že strom pokračuje hlouběji, „kruh“, že loď už výš ve větvi je. Strom je plánovací pomůcka – nejkratší řešení zná jen řešič (nápověda).
+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ů:

  1. Kořen je zlatá loď. Pod ní jsou lodě v cestě (čtení od ústí).
  2. 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ů).
  3. 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.
  4. 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ď.

123456123456ZABCDEFGHI
zlaté lodi brání C, D a E
  • 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 …
    • 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)
Obr. 4.1Úloha B z laboratoře a její strom překážek do hloubky 2. Člun D má volno nahoru o 1 pole. Nákladní loď E musí dolů o 1 pole a brání jí I; I musí doprava a brání jí F. Cesta dolů pro D vede přes F – a F by musela nahoru přes D: kruh.

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).

Příklad Úloha B – rozmotání řetězu

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.

ZABCDEFGHI
cíl: zlatá loď u ústí
ZABCDEFGHI
1. tah od konce: Z→1
ZABCDEFGHI
2. tah od konce: F↓1
ZABCDEFGHI
3. tah od konce: I←1
Obr. 4.2Úloha B od konce. Vlevo cíl, vedle stav před posledním tahem, před předposledním a před třetím od konce. Šipka ukazuje tah, který z daného stavu vede k cíli.

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ď:

Odhad zdola\[ t \ \ge\ 1 + \text{počet lodí v cestě}, \qquad t \approx 1 + \text{počet lodí na nejkratší cestě stromu} \]

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č.

Mistrovská pomůcka

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í

1
Co znamená v listu stromu slovo „volno“?
Že loď může touto možností uhnout hned – na polích, přes která musí projet, nikdo nestojí. Tahem této lodi se dá řetěz začít rozmotávat.
2
Vodorovná nákladní loď v řadě 6 stojí ve sloupcích 3–5. Kam musí, aby uvolnila sloupec 3?
Doprava o 1 (do sloupců 4–6). Doleva by musela tak daleko, aby skončila nejpozději ve sloupci 2 – na to se nákladní loď o třech polích nevejde.
3
Ve stromu je kruh: D brání F a F brání D. Má úloha řešení?
Může mít. Kruh jen říká, že tyto dvě možnosti nejdou použít současně. Řešení vede jinou možností (jiným směrem) nebo přes dočasný tah, po kterém se jedna z lodí vrátí – Krok zpět.
4
Na cestě stromu leží 3 lodě. Může mít úloha řešení na 3 tahy?
Ne – pokud jsou všechny tři nutné. Každá se musí pohnout aspoň jednou a k tomu zlatá loď: nejméně 4 tahy. Méně by bylo možné jen tehdy, kdyby existovala jiná, kratší cesta stromem.
5
Proč se v úloze B vrací nákladní loď E nahoru, když už jednou z cesty uhnula?
Aby mohla zpátky I a po ní F. Dokud E stojí v ř6s3, I nemůže doleva a F nemůže dolů – a F stojí ve třetí řadě ve sloupci 6. Zlatá loď mezitím projela kolem sloupce 3, takže E už jí nepřekáží.
Co si odnést
  • 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.
Část IITechniky přístavu
5

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.

Řešení krok za krokem
Projděte nejkratší řešení tlačítky Dál a Zpět. Šipka ukazuje příští tah, pod přístavem je technika, kterou mu trenér přiřadil. Graf sleduje, kolik lodí stojí zlaté lodi v cestě; Kroky zpět jsou oranžové tečky.
LABORATOŘ
Model: čtyři úlohy obtížnosti 2 a 3 z banky 3D hry, ve kterých řešič průvodce nenašel žádné nejkratší řešení bez Kroku zpět. Laboratoř ukazuje jedno nejkratší řešení (první, které najde prohledávání do šířky). Krok zpět je tah, kterým zlatá loď couvne, nebo kterým jiná loď vjede do třetí řady mezi zlatou loď a ústí.
+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ď.
123456123456ZABCDEFGH
po 7 tazích: Z←1 – zlatá loď couvne a uvolní ř3s3
123456123456ZABCDEFGH
D↓1 – D vjede do cesty a uvolní ř1s3
123456123456ZABCDEFGH
B←3 – řada 1 je volná pro C i D
Obr. 5.1Úloha na 13 tahů z laboratoře, tahy 8 až 10. Zlatá loď couvne (Z←1), tím uvolní ř3s3 a člun D může dolů do třetí řady (D↓1) – dva Kroky zpět za sebou. Až teď je řada 1 volná pro B←3; pak C↑1, D↑1 a Z→4. Celé řešení má tři Kroky zpět.
Příklad Úloha na 13 tahů

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

  1. 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).
  2. 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.
  3. 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.

Pozor

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.

Tab. 5.1Míry obtížnosti úloh 3D hry podle obtížnosti (výpočet řešičem průvodce)
ObtížnostÚlohNejmenší 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ěti704,07,915014 (20 %)23 %
1646,09,925912 (19 %)27 %
26411,419,21 10847 (73 %)24 %
36417,429,74 09458 (91 %)23 %
46423,439,611 05864 (100 %)22 %
56433,957,25 20264 (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.

Mistrovská pomůcka

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í

1
Zlatá loď stojí v ř3s2–s3 a couvne o 1 pole. Proč by to mohl být dobrý tah?
Uvolní pole ř3s3. Svislá loď ve sloupci 3 (například člun v řadách 1–2) může sjet dolů do třetí řady a uvolnit pole v řadě 1 pro vodorovnou loď. Přesně to se děje v Obr. 5.1.
2
Je Krok zpět totéž co špatný tah?
Ne. V nejkratším řešení každý tah – i Krok zpět – zmenší vzdálenost do cíle o 1. Krok zpět jen prodlouží cestu zlaté lodi nebo zvýší počet lodí v ní. Špatný tah naopak vzdálenost do cíle nezmenší.
3
Kolik procent úloh obtížnosti 2 v bance 3D hry potřebuje Krok zpět?
47 ze 64, tedy asi 73 %. V obtížnosti 1 je to 12 ze 64 (19 %), v obtížnosti 4 a 5 všechny.
4
Když v každém stavu vede blíž k cíli asi 22 % tahů, jaká je šance trefit náhodně 5 dobrých tahů za sebou?
0,225 ≈ 0,0005, tedy asi 1 : 1 900. U deseti tahů už jen zhruba 1 : 3,8 milionu. Proto se bez technik neobejdete.
5
V laboratoři u úlohy na 15 tahů je první tah Z←1. Jak poznáte, že jde o Krok zpět?
Je to tah zlaté lodi doleva – a ten trenér počítá jako Krok zpět vždy. Počet lodí v cestě se nezmění (před tahem i po něm E a F), ale cesta se prodlouží o pole, na kterém zlatá loď stála. V grafu laboratoře je oranžová tečka.
Co si odnést
  • 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.
Část IIIPatnáctka a bloky
6

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.

Řešitelnost a parita
V režimu Posouvat klepněte na dlaždici ve stejném řádku nebo sloupci jako volné pole – posune se (i s dlaždicemi mezi). V režimu Prohodit klepněte na dvě dlaždice a prohodí se, jako byste je vyndali z rámečku. Sledujte počet inverzí, řádek volného pole a verdikt.
LABORATOŘ
Model: cíl je 1, 2, 3, … po řádcích a volné pole vpravo dole. Inverze je dvojice dlaždic, ve které je větší číslo dřív (po řádcích) než menší; volné pole se nepočítá. Lichá šířka (3): řešitelné, právě když je počet inverzí sudý. Sudá šířka (4): řešitelné, právě když je součet inverzí a řádku volného pole počítaného odspodu lichý. U osmičky laboratoř spočítá i nejmenší počet tahů (A* s přípustnou heuristikou, kapitola 10), u patnáctky dolní mez – manhattanskou vzdálenost s lineárními konflikty.
Řešitelná, nebo ne?
Patnáctka rozházená náhodně – napůl řešitelná, napůl ne. Spočítejte inverze a řádek volného pole a rozhodněte. Výpočet se ukáže až po odpovědi. Pět správných odpovědí přinese body.
MINIHRA
Správně 0 z 0
+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čet inverzí\[ I = \left|\{(i,j) : i < j,\ a_i > a_j\}\right| \]
Příklad Osmička 1 2 3 / 4 5 6 / 8 7 _

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ý.
Kritérium řešitelnosti\[ W \text{ liché: } I \equiv 0 \pmod 2, \qquad W \text{ sudé: } I + r \equiv 1 \pmod 2 \]

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:

Počet řešitelných pozic\[ \tfrac{9!}{2} = 181\,440, \qquad \tfrac{16!}{2} = 10\,461\,394\,944\,000 \]
123456789101112131514
úloha 14–15: jedna inverze, neřešitelná
123456789101112131415
cíl: 0 inverzí
151413121110987654321
obráceně s volným polem vlevo nahoře: 105 inverzí
Obr. 6.1Vlevo úloha 14–15: 1 inverze a volné pole ve spodním řádku, součet 1 + 1 = 2 je sudý – neřešitelné. Uprostřed cíl. Vpravo obrácené pořadí s volným polem vlevo nahoře: 105 inverzí + řádek 4 = 109, lichý součet – řešitelné.
Z historie

Ú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

1234567891011121314151. řádek 12. sloupec 13. řádek 24. sloupec 25. zbytek 2 × 2
Obr. 6.2Pořadí fází metody Řádek po řádku na patnáctce: řádek 1 (dlaždice 1–4), sloupec 1 (5, 9, 13), řádek 2 (6–8), sloupec 2 (10, 14), zbytek 2 × 2 (11, 12, 15).

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ě.

124··3·········
1. připravit: 4 na místo trojky, 3 pod ni
124··3·········
2. dlaždice 4 doprava
1234···········
3. dlaždice 3 nahoru – řádek hotov
Obr. 6.3Poslední dvojice v prvním řádku: příprava (4 na místě trojky, 3 pod ní, volné pole vpravo nahoře), 4 doprava, 3 nahoru. Tečky jsou dlaždice, na kterých nezáleží.
Mistrovská pomůcka

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.

Tab. 6.1Osmička a patnáctka v číslech (tahy po jedné dlaždici)
Osmička 3 × 3Patnáctka 4 × 4
všech rozmístění9! = 362 88016! = 20 922 789 888 000
řešitelných (polovina)181 44010 461 394 944 000
nejvíc tahů do cíle31 (2 pozice)80 (17 pozic)
nejvíc tahů při posunu celé řady24 (1 pozice)–
průměrná vzdálenost od cíle22,0 tahu–
zdrojúplné prohledání řešičem průvodceBrüngger a kol. 1999, Korf a Schultze 2005

6.7Procvičení

1
Osmička po řádcích: 2, 1, 3, 4, 5, 6, 7, 8 a volné pole vpravo dole. Je řešitelná?
Ne. Jediná inverze (2, 1), lichý počet; osmička má lichou šířku, potřebuje sudý počet.
2
Patnáctka má 6 inverzí a volné pole ve druhém řádku odspodu. Je řešitelná?
6 + 2 = 8 je sudé – neřešitelná. Kdyby bylo volné pole v prvním nebo třetím řádku odspodu, byla by řešitelná.
3
Vyndáte z patnáctky dvě dlaždice a vrátíte je prohozené. Co se stane s řešitelností?
Obrátí se. Prohození dvou dlaždic změní počet inverzí o liché číslo (prohození sousedních o 1, vzdálenějších o 2k + 1), řádek volného pole zůstane. Řešitelná pozice se stane neřešitelnou a naopak – vyzkoušejte v laboratoři v režimu Prohodit.
4
Proč u osmičky nezáleží na tom, ve kterém řádku je volné pole?
Svislý tah u šířky 3 přesune dlaždici přes 2 jiné – počet inverzí se změní o −2, 0 nebo +2, parita zůstane. Řádek volného pole se mění, ale paritu inverzí neovlivní, takže do kritéria nevstupuje.
5
Kolik řešitelných pozic má patnáctka a kolik tahů stačí na každou?
16!/2 = 10 461 394 944 000 pozic a každou jde seřadit nejvýš na 80 tahů (Brüngger a kol. 1999); 80 jich potřebuje jen 17 pozic.
Co si odnést
  • 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.
Část IIIPatnáctka a bloky
7

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?

Velký čtverec ven
Klepněte na kus – zelené tečky ukážou všechna místa, kam může dojet (i za roh). Klepnutím na tečku kus přesunete. Dostaňte velký čtverec s hvězdičkou do středu spodní řady k otvoru. Laboratoř počítá tahy i kroky; nápověda spočítá vzdálenost do cíle pro všech 25 955 stavů.
LABORATOŘ
Model: deska 4 × 5, velký čtverec 2 × 2, čtyři svislé kusy 1 × 2, jeden vodorovný 2 × 1, čtyři malé čtverce a dvě volná pole. Tah = posun jednoho kusu kamkoli po volných polích (i za roh), krok = posun o jedno pole. Kusy stejného tvaru jsou zaměnitelné, proto má hlavolam ze startu 25 955 dosažitelných stavů. Vzdálenosti počítá prohledávání do šířky přímo v prohlížeči (první nápověda chvíli trvá).
+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

★
start: velký čtverec nahoře uprostřed
★
cíl po 81 tazích: velký čtverec dole uprostřed
Obr. 7.1Tradiční rozestavení čínského hlavolamu a cílový stav nejkratšího řešení, které našel řešič průvodce. Hvězdička značí velký čtverec.

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ě).
za roh: 1 tah cestou = 2 přímé tahy = 2 kroky
rovně o 2 pole: 1 tah = 1 přímý tah = 2 kroky
Obr. 7.2Malý čtverec za roh: 1 tah cestou, ale 2 přímé tahy a 2 kroky. Malý čtverec rovně o 2 pole: 1 tah cestou, 1 přímý tah, 2 kroky.
Tab. 7.1Nejkratší řešení čínského hlavolamu z tradičního rozestavení (výpočet řešičem průvodce, prohledávání do šířky)
PočítáníNejmenší početDosažitelných stavů
tah cestou (kus kamkoli)8125 955
přímý tah (jedním směrem)9025 955
krok (o jedno pole)11625 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“.
Mistrovská pomůcka

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.

Pozor

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í

1
Kolik polí zabírají kusy čínského hlavolamu a kolik zůstává volných?
Velký čtverec 4, čtyři svislé obdélníky 8, vodorovný obdélník 2, čtyři malé čtverce 4: 18 polí. Deska má 4 · 5 = 20 polí, volná jsou 2.
2
Malý čtverec se posune o pole doleva a pak o pole nahoru. Kolik je to tahů v každém počítání?
1 tah cestou (je to jeden kus a jedna souvislá cesta), 2 přímé tahy (dva směry), 2 kroky.
3
Proč je nejkratší řešení v krocích (116) delší než v přímých tazích (90)?
Přímý tah o dvě pole jsou dva kroky. Nejkratší řešení v přímých tazích obsahuje i posuny o dvě pole, a v krocích se proto prodlouží. Obecně platí tahy cestou ≤ přímé tahy ≤ kroky.
4
Může velký čtverec projít kolem vodorovného obdélníku, když jsou obě volná pole rozdělená?
Ne. Velký čtverec se posune jen tehdy, když jsou na jeho straně volná dvě sousední pole. Rozdělená volná pole mu nepomohou – nejdřív je musí spojit malé čtverce.
5
V čem se čínský hlavolam liší od přístavu z kapitol 3–5?
V přístavu jezdí každý kus jen po své délce (jeden rozměr), tady se kusy posouvají všemi čtyřmi směry. Přístav má víc volného místa a cíl jen pro jeden kus; čínský hlavolam má jen dvě volná pole, a proto tak dlouhá řešení.
Co si odnést
  • Čí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.
Část IVPočítač a hlavolamy
8

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.

Generátor v prohlížeči
Nastavte počet lodí a spusťte generátor. Každé náhodné rozmístění prohledá do šířky, najde nejtěžší stav jeho komponenty a zapíše ho do grafu. Nejtěžší nalezená úloha se ukáže v přístavu. Porovnejte s rozdělením banky 3D hry v Obr. 8.2.
LABORATOŘ
Model: zlatá loď ve třetí řadě, ostatní lodě náhodně (vodorovné i svislé, asi 30 % nákladních), ve třetí řadě žádná další vodorovná loď. Komponenty větší než 20 000 stavů laboratoř přeskočí, aby prohlížeč nezamrzl (generátor hry používá mez 300 000). Graf: kolik komponent mělo nejtěžší stav vzdálený 1, 2, 3, … tahů od cíle; neřešitelná rozmístění se počítají zvlášť.
+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í lodícelá komponentastavů (BFS)vzdálenostod cíle (BFS z cílů)nejtěžší stav= úlohatříděnípodle tahů → bankaneřešitelné nebo příliš lehké (méně než 2 tahy) → zahodittěžké úlohy (obtížnost 4 a 5): také horolezení – malé změny rozmístění, které nejmenší počet tahů nesníží
Obr. 8.1Výroba úloh 3D hry. Z každého náhodného rozmístění vznikne nejvýš jedna úloha – nejvzdálenější stav jeho komponenty. Těžké úlohy dohledá horolezení.
  1. Náhodné rozmístění zlaté lodi a 3 až 13 dalších lodí.
  2. Celá komponenta: prohledávání do šířky najde všechny stavy, do kterých se z rozmístění dá dojet (kapitola 9).
  3. 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.
  4. Ú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.
  5. 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).

1101001 00010 00024915212846nejmenší počet tahů nejtěžšího stavu komponentypočet komponent (logaritmická osa)
Obr. 8.2Všechny komponenty, které našel generátor 3D hry, podle nejmenšího počtu tahů jejich nejtěžšího stavu. Osa y je logaritmická: každá čára je desetkrát víc než předchozí. Barvy odpovídají obtížnostem (šedá – pod obtížností 1, zelená 1, modrá 2 a 4, oranžová 3 a 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.

Tab. 8.1Náhodná rozmístění podle počtu lodí včetně zlaté (pokus průvodce: 1 500 rozmístění, 67 s komponentou nad 60 000 stavů vynecháno; výběr řádků)
Lodí celkemRozmístěníS řešenímPrůměrná vzdálenost startu od cílePrůměr stavů v komponentě
6195189 (97 %)1,92 657
8180159 (88 %)2,610 693
10187150 (80 %)2,915 371
1216289 (55 %)3,912 296
1318981 (43 %)3,37 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

Mistrovská pomůcka

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.

03691248121620242832364044nejmenší počet tahů úlohypočet úloh v bance hry
Obr. 8.3Úlohy 3D hry (obtížnosti 1–5) podle nejmenšího počtu tahů. Barvy odpovídají obtížnostem jako v Obr. 8.2.
Tab. 8.2Banka úloh 3D hry (stav k 10. 11. 2026)
RežimÚlohNejmenší počet tahůJak vznikly
Pro děti702–6náhodná rozmístění se 4 až 6 loďmi včetně zlaté
Úlohy 1 až 364 v každé4–8, 9–14, 15–20náhodná rozmístění
Úlohy 4 a 564 a 6421–27, 28–46náhodná rozmístění i horolezení
Patnáctka 1 a 2 (osmička)60 a 608–16, 20–30náhodná řešitelná zamíchání a náhodné procházky od cíle
Patnáctka 3 až 5 (4 × 4)50, 50 a 3616–28, 30–40, 43–64procházky od cíle, obtížnost 5 zcela náhodná řešitelná zamíchání; nejmenší počet tahů z IDA*
Pozor

Ú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í

1
Proč generátor nebere za úlohu přímo náhodné rozmístění?
Náhodné rozmístění bývá od cíle jen 2 až 4 tahy daleko (Tab. 8.1). Nejvzdálenější stav téže komponenty je nejtěžší úloha, kterou daná sada lodí nabízí, a navíc nezačíná uprostřed řešení.
2
Proč s víc loděmi klesá podíl rozmístění s řešením?
Lodě se navzájem zablokují: přibývá rozmístění, ve kterých svislá loď v cestě nemá kam uhnout a nepomůže jí žádný řetěz. Se 13 loďmi mělo řešení jen 43 % rozmístění.
3
Co by se stalo, kdyby generátor vzal za úlohu stav uprostřed komponenty?
Hráč by se mohl tahy dostat do stavu, který je od cíle dál než start. Úloha by „ukrývala“ těžší úlohu a nejmenší počet tahů by neříkal, jak těžké je bloudění v ní.
4
Kolik procent komponent z generátoru mělo nejtěžší stav nejvýš 8 tahů od cíle?
7 129 z 8 909, tedy asi 80 %. Komponent s nejtěžším stavem aspoň 15 tahů od cíle (obtížnost 3 a výš) bylo 350, necelá 4 %.
5
Proč horolezení začíná opakovaně z různých úloh?
Aby se nezaseklo na místním vrcholu – v úloze, kterou už žádná malá změna (přidat, ubrat, přesunout loď) nezlepší. Z jiného výchozího místa vede cesta k jinému, třeba vyššímu vrcholu.
Co si odnést
  • Ú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.
Část IVPočítač a hlavolamy
9

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ě.

Vlna v grafu stavů
Malá úloha se 14 loďmi má jen 17 stavů. Tlačítkem Další vrstva pošlete vlnu o tah dál: nově objevené stavy se rozsvítí, pod grafem je fronta. Přepněte, odkud vlna vychází – ze startu, nebo ze všech cílových stavů. Klepnutím na kroužek uvidíte stav v přístavu.
LABORATOŘ
Model: úloha BBBCC./ADEEFF/ADZZJG/AHHHJG/KL.IJG/KL.IMM, tah = posun jedné lodi o libovolný počet polí. Kroužky jsou stavy rozmístěné do sloupců podle vzdálenosti od startu, čísla v kroužcích pořadí, ve kterém je prohledávání do šířky ze startu objeví. Rozsvícené stavy jsou objevené, s tučným okrajem ty, které právě čekají ve frontě.
+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

  1. Do fronty vlož start a označ ho jako objevený.
  2. Vyber stav ze začátku fronty. Je-li cílový, skonči – cesta k němu je nejkratší.
  3. 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.
  4. Opakuj od kroku 2. Když se fronta vyprázdní a cíl nebyl nalezen, úloha nemá řešení.
1234567891011121314151617012345678910
Obr. 9.1Graf stavů úlohy z laboratoře: 17 stavů, 21 hran, sloupce podle vzdálenosti od startu (0 až 10). Zeleně dva cílové stavy, oranžově nejkratší cesta – 9 tahů: C→1, B→1, A↑1, H←1, I↑1, M←2, J↓1, G↓1, Z→2.

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.

Příklad Řetěz osmi lodí

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.

Čas a paměť BFS\[ T = O(|S| + |H|), \qquad M = O(|S|) \]

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.

Mistrovská pomůcka

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

startcíldvě koule o poloměru d/2 místo jedné o poloměru dhloubka d/2hloubka d/2setkání
Obr. 9.2Obousměrné prohledávání: dvě vlny do hloubky d/2 se potkají uprostřed nejkratší cesty. Objem dvou malých koulí je mnohem menší než objem jedné velké.

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í

1
Proč si prohledávání do šířky musí pamatovat objevené stavy?
Každý tah jde vrátit, takže by se stav objevoval znovu a znovu (tam a zpátky) a prohledávání by nikdy neskončilo. Seznam objevených stavů zaručí, že se každý zpracuje jen jednou.
2
Jak se z prohledávání do šířky dostane samotné řešení (posloupnost tahů), ne jen jeho délka?
U každého stavu je uložený předchůdce a tah, kterým se do stavu přišlo. Od nalezeného cíle se jde po předchůdcích zpět ke startu a tahy se seřadí obráceně.
3
Vlna z cílů v laboratoři: proč začíná dvěma stavy, ne jedním?
Úloha má v komponentě dva cílové stavy – zlatá loď u ústí a ostatní lodě ve dvou různých rozestaveních. Vlna musí začít ze všech, jinak by vzdálenosti nevyšly nejmenší.
4
Kolik stavů osmičky je od cíle nejvýš 15 tahů a kolik nejvýš 30?
7 279 a 181 438 (spočítal řešič průvodce). Zbylé 2 stavy jsou ve vzdálenosti 31.
5
Najde prohledávání do hloubky (bez prohlubování) vždy nejkratší řešení?
Ne. Jde po první cestě, která ho napadne, a cíl může najít po dlouhé oklice. Nejkratší řešení zaručí prohledávání do šířky nebo iterativní prohlubování.
Co si odnést
  • 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ěť.
Část IVPočítač a hlavolamy
10

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.

Závod algoritmů
Vyberte pozici osmičky nebo patnáctky a spusťte závod. Každý algoritmus najde nejkratší řešení; tabulka a graf ukazují, kolik stavů musel rozvinout. Prohledávání do šířky a počet dlaždic mimo místo mají u patnáctky mez 100 000 stavů.
LABORATOŘ
Model: A* rozvíjí stavy podle součtu f = g + h (tahy od startu + odhad do cíle); s h = 0 je to prohledávání do šířky. Heuristiky: počet dlaždic mimo místo, manhattanská vzdálenost, manhattanská vzdálenost s lineárními konflikty. IDA* používá tu nejsilnější. „Rozvinutý stav“ = stav, jehož tahy algoritmus vyzkoušel. Pozice: osmičky z úplného prohledání řešičem průvodce (31 tahů je nejtěžší možná), patnáctky z banky 3D hry.
+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

Přípustnost\[ 0 \le h(s) \le d(s) \quad \text{pro každý stav } s \]

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

Manhattanská vzdálenost\[ h_M(s) = \sum_{t=1}^{N} \left( |r_t - r_t^{*}| + |c_t - c_t^{*}| \right) \]
41372658vzdálenost dlaždic od cíle4: 11: 13: 07: 12: 16: 05: 18: 1součet h = 6
Obr. 10.1Osmička: u každé dlaždice počet řádků a sloupců k cílovému poli. Zeleně dlaždice na svém místě. Součet je manhattanská vzdálenost h = 6.

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

23145678
řádek 2 3 1: manhattanská vzdálenost 4, s konflikty 6, skutečně 16 tahů
Obr. 10.2První řádek 2 3 1: všechny tři dlaždice jsou ve své řadě, ale jednička musí dopředu. Manhattanská vzdálenost 4, s lineárními konflikty 6, skutečná vzdálenost 16 tahů (spočítal řešič průvodce). Obě heuristiky jsou přípustné – jen tahle pozice je pro ně zvlášť zrádná.

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

Tab. 10.1Rozvinuté stavy do nalezení nejkratšího řešení (řešič průvodce)
PoziceDo šířky (h = 0)A*, mimo místoA*, manhattanskáA*, manhattanská + konfliktyIDA*, manhattanská + konflikty
osmička, 31 tahů181 439121 5276 7903 8218 970
osmička, 20 tahů40 4152 260462222241
patnáctka, 28 tahůpřes 400 000203 0473 8591 8853 362
patnáctka, 36 tahůpřes 400 000přes 400 0004 5031 2748 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.

Příklad Proč meze rostou o 2

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.

Mistrovská pomůcka

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í

1
Je počet dlaždic mimo své místo přípustná heuristika?
Ano. Každá dlaždice mimo své místo se musí pohnout aspoň jednou a jeden tah pohne jen jednou dlaždicí. Odhad tedy nikdy nepřecení skutečnost – jen je slabý.
2
Proč A* s přípustnou heuristikou nenajde delší řešení, než je nejkratší?
Cíl rozvine, až když má nejmenší f. Kdyby existovala kratší cesta, stav na ní by měl f ≤ délka kratší cesty (heuristika nepřeceňuje) a byl by rozvinut dřív. Proto první rozvinutý cíl leží na nejkratší cestě.
3
Řádek 3 2 1 ve své cílové řadě: kolik přidají lineární konflikty?
Tři dlaždice, nejdelší rostoucí podposloupnost má délku 1: 2 · (3 − 1) = 4 tahy navíc k manhattanské vzdálenosti.
4
Proč IDA* rozvine u osmičky na 31 tahů víc stavů (8 970) než A* se stejnou heuristikou (3 821)?
IDA* si nepamatuje objevené stavy: v každém opakování prochází znovu stavy z minulých opakování a stejný stav může projít několika cestami. Za to potřebuje paměť jen na jednu cestu.
5
Proč u přístavu stačí prohledávání do šířky, kdežto u patnáctky ne?
Komponenta úlohy v přístavu má tisíce až desetitisíce stavů (v bance nejvýš 79 140), kdežto patnáctka má 10 461 394 944 000 stavů. Do šířky jde prohledat jen to, co se vejde do paměti.
Co si odnést
  • 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.
Část IVPočítač a hlavolamy
11

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.

Exploze stavů
Posuvníkem měňte velikost desky n × n (hlavolam typu patnáctka). Laboratoř spočítá počet řešitelných pozic (n²)!/2 a jak dlouho by trvalo projít je všechny prohledáváním do šířky rychlostí, kterou zvolíte. Graf má logaritmickou osu – každá čára je tisíckrát víc.
LABORATOŘ
Model: řešitelná je přesně polovina z (n²)! rozmístění (kapitola 6). Čas = počet stavů / rychlost, paměť = 1 bit na stav (nejúspornější možná značka „objeveno“). Rychlost miliarda stavů za sekundu je hrubý řád pro výkonný počítač; skutečné prohledávání bývá pomalejší. Rok = 365,25 dne.
Do které třídy patří?
U každé úlohy o hlavolamech na desce libovolné velikosti rozhodněte, do které třídy složitosti patří. Vysvětlení se ukáže po odpovědi. Pět správných odpovědí ze šesti přinese body.
MINIHRA
Úloha 1 ze 6 · správně 0
+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

Řešitelné pozice hlavolamu n × n\[ \frac{(n^2)!}{2}: \quad 12,\ 181\,440,\ \approx 1{,}05 \cdot 10^{13},\ \approx 7{,}76 \cdot 10^{24},\ \approx 1{,}86 \cdot 10^{41} \quad (n = 2, \dots, 6) \]

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

Příklad Snadné a těžké na téže desce

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).
PSPACENPPřešitelnost patnáctky(parita)„je řešení do k tahů?“u patnáctky n × n„dá se vyplout?“dopravní a posuvné blokyna velké desceP ⊆ NP ⊆ PSPACE; zda jsou inkluze ostré, se zatím neví
Obr. 11.1Třídy složitosti a posuvné hlavolamy. Platí P ⊆ NP ⊆ PSPACE. Zda je některá inkluze ostrá (P ≠ NP, NP ≠ PSPACE), patří k největším otevřeným otázkám matematiky.

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í.

Pozor

„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í

1
Proč patří rozhodnutí o řešitelnosti patnáctky n × n do P?
Stačí spočítat inverze (porovnat všechny dvojice dlaždic, řádově n4 porovnání) a řádek volného pole – čas roste polynomiálně.
2
Jak se liší „seřadit desku“ a „seřadit desku nejkratším řešením“?
Seřadit jde rychle (Řádek po řádku, řádově n3 tahů) – úloha v P. Najít nejkratší řešení je NP-těžké (Ratner a Warmuth).
3
Kolik let by trvalo projít všechny řešitelné pozice desky 5 × 5 rychlostí miliarda stavů za sekundu?
Pozic je 25!/2 ≈ 7,76 · 1024; za sekundu 109, tedy ≈ 7,76 · 1015 s ≈ 246 milionů let.
4
Co znamená, že úloha je PSPACE-úplná?
Patří do PSPACE (dá se vyřešit s polynomiální pamětí) a každá jiná úloha z PSPACE se na ni dá rychle převést – je tedy aspoň tak těžká jako kterákoli úloha třídy.
5
Znamená výsledek Flakea a Bauma, že úlohy 3D hry jsou pro počítač těžké?
Ne. Výsledek mluví o deskách libovolné velikosti. Přístav 6 × 6 je pevný a komponenty jeho úloh mají nejvýš desítky tisíc stavů – řešič je projde za zlomek sekundy.
Co si odnést
  • Ř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ý.
Část IVPočítač a hlavolamy
12

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?

Nejtěžší úloha
Klepněte na loď a pak na zelenou tečku. Laboratoř zná vzdálenost každého stavu od cíle a ukazuje ji po každém tahu – vidíte, jestli jste se přiblížili, nebo vzdálili. Nápověda pojmenuje techniku jako trenér 3D hry, Tah řešiče táhne za vás, Přehrát ukáže celé nejkratší řešení.
LABORATOŘ
Model: první úloha je nejtěžší úloha bez zdí z výčtu Michaela Foglemana (2018), převedená do přístavu: auta jsou lodě, červené auto zlatá loď. Druhá je nejtěžší úloha banky 3D hry. Řešič průvodce u obou spočítal celou komponentu a vzdálenost každého stavu od cíle; nápověda vybere tah do stavu o 1 bližšího k cíli a technika se určí stejně jako u trenéra (kapitola 3).
+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.

Z historie

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

123456123456ZABCDEFGHIJKL
51 tahů (81 kroků), 4 780 stavů
Obr. 12.1Foglemanova nejtěžší úloha 6 × 6 bez zdí převedená do přístavu: 13 lodí (10 člunů včetně zlaté lodi a 3 nákladní). Řešič průvodce potvrdil 51 tahů; v krocích je nejkratší řešení dlouhé 81 kroků.

Ř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).

Tab. 12.1Nejkratší řešení nejtěžší úlohy podle techniky trenéra (výpočet řešičem průvodce)
Volná cestaUvolnit cestuŘetěz překážekKrok zpětCelkem
4831851

Ř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).

011122233344401020304051nejmenší počet tahů do cílepočet stavů
Obr. 12.2Stavy komponenty nejtěžší úlohy podle vzdálenosti od cíle. Zeleně 199 cílových stavů, oranžově 3 nejvzdálenější stavy (51 tahů), mezi nimi start.

12.4Jak radí trenér 3D hry

  1. Při načtení úlohy hra spočítá komponentu a mapu vzdáleností (zlomek sekundy).
  2. První nápověda ukáže loď, kterou začíná některý tah do stavu o 1 bližšího k cíli.
  3. 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.
  4. 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.

Mistrovská pomůcka

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.

Pozor

„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í

1
Proč mohl počítač najít nejtěžší úlohu přístavu 6 × 6, kdežto pro patnáctku n × n nejkratší řešení obecně rychle hledat neumíme?
Deska 6 × 6 je pevná a konečná – rozmístění je obrovské, ale konečné množství a dá se projít. Složitost (kapitola 11) mluví o deskách, které rostou; pro ně rychlý postup nejspíš neexistuje.
2
Nejtěžší úloha má v komponentě 3 stavy ve vzdálenosti 51. Proč ne jen jeden?
Tři nejvzdálenější stavy se liší jen polohou člunu B v řadě 1 a člunu D ve sloupci 2 (podle zápisu z Obr. 12.1) – tahy B←1, B→1, D↑1 a D↓1 mezi nimi vzdálenost nemění. Za úlohu stačí vzít kterýkoli z nich.
3
Kolik tahů a kolik kroků má nejkratší řešení nejtěžší úlohy?
51 tahů a 81 kroků (nejkratší řešení v krocích; spočítal řešič průvodce).
4
Jak nápověda pozná, který tah je dobrý?
Podívá se do mapy vzdáleností: dobrý je tah do stavu, jehož vzdálenost od cíle je o 1 menší než vzdálenost současného stavu.
5
Uvádí se, že nejtěžší úloha má 93, jinde 51. Kdo má pravdu?
Oba – počítají jinak. 93 jsou kroky (posun o jedno pole), 51 tahy (posun o libovolný počet polí), a nejtěžší úloha v krocích nemusí být táž jako nejtěžší v tazích. Vždy se ptejte, co se počítá.
Co si odnést
  • 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í.
PřílohaA

Slovníček

Česká hesla s anglickým termínem. Hledat lze v obou jazycích.

PřílohaB

Vzorce a přehledy

Techniky trenéra

Tab. B.1Techniky z nápovědy 3D hry a kapitoly, které je vykládají
TechnikaCo děláKapitola
Volná cestazlatá loď jede doprava, nejlépe rovnou k ústí3
Uvolnit cestuloď v cestě uhne – člun nahoru nebo dolů, nákladní loď vždy dolů do řad 4–63
Řetěz překážekpohnout lodí mimo cestu, aby mohla uhnout loď v cestě; plánovat stromem překážek odzadu4
Krok zpětzlatá loď couvne nebo jiná loď vjede do cesty, aby uvolnila pole jiné lodi5
Řádek po řádkupatnáctka: seřadit první řádek, pak první sloupec, a desku tak zmenšovat6
Poslední dvojiceposlední dvě dlaždice řádku: čtyřka na místo trojky, trojka pod ni, pak oba dva tahy6

Vzorce na jednom místě

Tahy a kroky v přístavu (kap. 2)\[ t \le k \le 4\,t \]
Horní mez počtu stavů (kap. 2)\[ |S| \le \prod_{i=1}^{n} (7 - \ell_i) \]
Nejmenší počet tahů (kap. 2, 9)\[ d(s_0) = \min_{c \in C} \operatorname{dist}(s_0, c) \]
Uvolnění třetí řady (kap. 3)\[ \text{člun:}\ \uparrow (r-1)\ \text{nebo}\ \downarrow (4-r), \qquad \text{nákladní loď:}\ \downarrow (4-r) \]
Řešitelnost patnáctky (kap. 6)\[ W \text{ liché: } I \equiv 0 \pmod 2, \qquad W \text{ sudé: } I + r \equiv 1 \pmod 2 \]
Počet řešitelných pozic (kap. 6, 11)\[ \frac{(W H)!}{2} \]
Manhattanská vzdálenost (kap. 10)\[ h_M(s) = \sum_{t} \left( |r_t - r_t^{*}| + |c_t - c_t^{*}| \right) \le d(s) \]
A* (kap. 10)\[ f(s) = g(s) + h(s) \]
Prohledávání do šířky (kap. 9)\[ T = O(|S| + |H|), \qquad M = O(|S|) \]

Důležitá čísla

Tab. B.2Čísla z průvodce a jejich původ
ÚdajHodnotaZdroj
řešitelné pozice osmičky / patnáctky181 440 / 10 461 394 944 0009!/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áctka80 tahů, 17 pozicBrüngger a kol. 1999, Korf a Schultze 2005
čínský hlavolam: tahy cestou / přímé tahy / kroky81 / 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 hry46 tahůgenerátor hry, ověřeno řešičem průvodce
úlohy 3D hry70 + 5 × 64 přístav, 256 patnáctkabanka hry k 10. 11. 2026
PřílohaC

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.

Interaktivní průvodce Posuvné hlavolamy (listopad 2026). 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 aplikace ani hry; obchodní názvy se objevují jen ve věcné historii a v názvech citovaných článků.