← Herna
Skládačka z kostek ve 3D
📖 Průvodce
📖 Průvodce: Blokové hlavolamy12 kapitol hned pod hrou ↓
Blokové hlavolamy🧭 Další průvodci a hry
INTERAKTIVNÍ PRŮVODCE · LISTOPAD 2026

Blokové hlavolamy

Polyomina, pentomina a mizející řady
od prvního kusu po algoritmy a složitost

Na pozadí hraje počítač skládačku na desce 8 × 8 na obtížnost Střední: tři kusy v zásobníku, pentomina i čtverec 3 × 3, bez otáčení. Každý kus položí tam, kde po tahu zůstane nejlepší deska podle hodnocení z kapitoly 12 – vymazané řady, osamělá pole, místo pro velké kusy a rozbitost – a tah pojmenuje. Oranžově je právě položený kus, modře řady, které zmizely. Pravidla a body vysvětlují kapitoly 3 a 4, proč deska jednou dojde, kapitola 7.

tah–
body–
řady–
technika–
Úvodem

Jak průvodce používat

Blokové hlavolamy se skládají z kusů poskládaných ze shodných čtverečků – polyomin. Jednou je úkolem vyskládat z dvanácti pentomin obdélník bez mezer, jindy pokládat kusy z nabídky na desku 8 × 8, kde plný řádek nebo sloupec zmizí, a vydržet co nejdéle. Průvodce vede od tvarů a pravidel přes techniky, které hráči používají – dokončit řadu, nechat místo pro velké kusy, hlídat pořadí a osamělá pole – k paritním důkazům, krychli ze sedmi kusů, počítání tvarů, algoritmům a k tomu, proč jsou tyto hlavolamy pro počítač obecně těžké. Je pro hráče, kteří chtějí hrát promyšleněji, pro rodiče a děti, které si při skládání cvičí prostorovou představivost, i pro studenty matematiky a informatiky.

🧩

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 Skládačka z kostek ve 3D: dřevěnou desku, na kterou pokládáte barevné kusy, pět obtížností, režim pentomin s ověřenými úlohami, denní výzvu, režim pro děti a trenéra, který ukáže dobrý tah a odkáže na kapitolu, kde se technika vykládá.

Mapa průvodce

Tab. 0.1Kapitoly, úroveň a co se v nich naučíte
KapitolaÚroveňCo se naučíte
1 Kostky, tvary a historiezákladyco je polyomino, monomino až pentomino, souvislost přes hranu; od hlavolamu na šachovnici (1907) přes pentomina (1953/1954) a krychli ze sedmi kusů (1933) k padajícím kostkám (1984) a skládačkám na desce
2 Rodina polyominzákladyvolné, jednostranné a pevné tvary, dvanáct pentomin a jejich písmena, souměrnosti, zrcadlové dvojice
3 Deska, řady a bodyzákladypravidla skládačky na desce 8 × 8, řádky a sloupce mizí současně, body; techniky Dokončit řadu a Místo pro velké kusy
4 Pořadí kusů a sériezákladyproč záleží na pořadí tří kusů, Dvojité vymazání, série a bonus, kalkulačka bodů
5 Pentomina na obdélníkupokročilíobdélníky 6 × 10 až 3 × 20 a počty řešení, šachovnice bez středu, technika Úzké místo
6 Parita a obarvenípokročilíšachovnicový důkaz, prořezaná šachovnice, T a L tetromina, obarvení pruhy a úhlopříčkami, proč 35 hexomin netvoří obdélník
7 Riziko a osamělá polepokročilíkdy se kus přestane vejít, riziko podle zaplnění desky, technika Bez osamělých polí, zdravé hraní
8 Krychle ze sedmi kusůpokročilípolykostky, 24 otočení krychle, sedm kusů a 240 řešení krychle 3 × 3 × 3, paritní argument v prostoru
9 Kolik je polyominmistr a vědapočítání tvarů růstem a Redelmeierovým algoritmem, tvary s dírou, růstová konstanta kolem 4,06 a meze
10 Algoritmus X a tanec odkazůmistr a vědaúloha přesného pokrytí jako matice, Knuthův Algoritmus X, tanec odkazů, výběr sloupce s nejméně možnostmi
11 Složitostmistr a vědaNP-úplnost, 3-dělení, výsledky pro padající kostky, skládání polyomin a skládačky; co z nich plyne pro hráče
12 Počítač hraje a vyrábí úlohymistr a vědahodnoticí funkce a její části, porovnání strategií, férový zásobník, tvorba pentominových úloh s jediným řešením

Co budete potřebovat

Čtverečkovaný papír, tužku a nůžky – z papíru si vystřihnete pentomina a vyzkoušíte je v ruce. Všechny úlohy jsou ale i v laboratořích, takže nic tisknout nemusíte. Pro první část stačí počítat a kreslit; dítě, které umí skládat kostky, zvládne kapitoly 1 až 4 a minihry k nim. Od kapitoly 6 se hodí sudá a lichá čísla a dělitelnost, v kapitole 7 procenta, v kapitole 9 mocniny a v kapitolách 10 až 12 trocha algoritmického myšlení – co je potřeba, průvodce vysvětlí na místě.

Navazující látku najdete v sousedních průvodcích: logické hry s jediným řešením v průvodcích Sudoku, Kakuro a Hledání min, plánování několik tahů dopředu v průvodci Šachy, mocniny, dělitelnost a souměrnosti v průvodci Matematika, pravděpodobnost a simulace v průvodci Statistika a modely, důkaz sporem v průvodci Logika a kritické myšlení a algoritmy, prohledávání a NP-úplnost obecně v průvodci Informatika.

Značení a předpoklady

Pole desky se značí ř3s5 = 3. řádek shora, 5. sloupec zleva. Řadou se v průvodci myslí řádek i sloupec. Kus se v textu jmenuje podle tvaru (rovná čtveřice, malý roh, čtverec 3 × 3, T…), pentomina písmeny F, I, L, N, P, T, U, V, W, X, Y, Z (kapitola 2). Kusy skládačky na desce se pokládají tak, jak přijdou; na obtížnostech 1 a 2 a v režimu pro děti jdou otáčet. Laboratoře, hero i trenér ve 3D hře používají stejná pravidla: deska 8 × 8, body za kostky a vymazané řady (kapitola 3), sady kusů podle obtížnosti.

Tab. 0.2Obtížnosti skládačky ve 3D hře a kapitoly, které k nim patří
ObtížnostKusy a zásobníkKapitoly
1 Pohodovámalé kusy do čtyř kostek, otáčení klepnutím, férový zásobník3
2 Lehkákusy do čtyř kostek, otáčení, férový zásobník3, 4
3 Střednípentomina a čtverec 3 × 3, bez otáčení, férový zásobník3, 4, 7
4 Těžkájako 3, ale náhodný zásobník – nemusí jít položit všechny tři4, 7
5 Mistrovskánáhodný zásobník a víc velkých kusů7, 12
Férový zásobník znamená, že tři nabídnuté kusy jdou na aktuální desku vždy nějak položit všechny (kapitola 12). Režim Pentomina má vlastní obtížnosti: od úloh, kde šest kusů už leží, po prázdný obdélník 3 × 20 (kapitola 5).

Čtyři druhy rámečků

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

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

Z historie

Kdo hlavolam vymyslel, kdo spočítal jeho řešení a co o něm dokázali matematici.

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. Historické údaje a matematické výsledky mají v příloze C zdroj a datum ověření (9. 11. 2026). Počty tvarů a řešení, desky v minihrách a simulace jsou spočítané vlastním řešičem průvodce – přímo v prohlížeči nebo skriptem nad stejným kódem.

Rozsahem odpovídá: matematika – kombinatorika tvarů a souměrností (grupa otočení a zrcadlení čtverce a krychle, počítání orbit), paritní a barvicí důkazy na úrovni úvodních vysokoškolských kurzů diskrétní matematiky, odhad pravděpodobnosti simulací; informatika – prohledávání s návratem, úloha přesného pokrytí a Knuthův Algoritmus X s tancem odkazů, heuristiky výběru proměnné, úvod do NP-úplnosti a převodů (3-dělení); pravidla – pentominové a krychlové hlavolamy podle pramenů v příloze C a vlastní pravidla skládačky na desce, ze kterých vychází hra průvodce.

Hrajte

Skládačka z kostek ve 3D

Pokládejte barevné kusy z dřevěných kostek na desku. Plný řádek nebo sloupec zmizí, hra končí, když se žádný ze zbylých kusů nevejde. Desku jde v nastavení přepnout na Pohled 3D / 2D shora. Na výběr je Klasická (deska 8 × 8, tři kusy v zásobníku), Pentomina (složit všech dvanáct pentomin do obdélníku nebo šachovnice), Denní výzva (v daný den stejná řada 60 kusů pro všechny, obtížnost 3) a Pro děti (deska 6 × 6, malé kusy, otáčení a žádná prohra – když se nic nevejde, zásobník se vymění). Obtížnost 1 až 5 v klasické hře: 1 malé kusy do čtyř kostek s otáčením, 2 kusy do čtyř kostek s otáčením, 3 pentomina a čtverec 3 × 3 bez otáčení, 4 jako 3, ale s náhodným zásobníkem, 5 náhodný zásobník a víc velkých kusů (kapitola 3, 7). Na obtížnostech 1 až 3 je zásobník férový: tři kusy jdou vždy nějak položit všechny, rozhoduje pořadí a místo (kapitola 4, 12). Pentomina mají obtížnosti od šesti ležících kusů po prázdný obdélník 3 × 20 se dvěma řešeními (kapitola 5). Ovládání v kostce: kus táhněte prstem nebo myší na desku – zelený stín jde položit, červený ne a zlatě svítí řady, které zmizí. Klepnutí na kus ho otočí (kde je to dovoleno) a vybere, klepnutí na desku ho položí, dlouhý stisk pentomino zrcadlí. Na klávesnici 1–3 výběr kusu, šipky posun, R otočit, M zrcadlit, mezerník položit, Z zpět (pentomina a děti), T nápověda, Esc zrušit výběr.

Jak to funguje: body jsou stejné jako v průvodci – 1 za každou položenou kostku, 10 za každé pole vymazané řady, při víc řadách naráz se bonus násobí jejich počtem a série vymazání v tazích po sobě přidává +50 % za každý další tah (kapitola 3, 4). Nápověda trenéra má tři stupně: první klepnutí ukáže kus, druhé pojmenuje techniku a ukáže místo – Dokončit řadu, Místo pro velké kusy, Dvojité vymazání, Pořadí kusů, Bez osamělých polí, u pentomin Úzké místo – vždy s odkazem na kapitolu, třetí kus položí. Trenér hledá tah prohledáním pořadí, natočení a poloh kusů v zásobníku podobně jako počítač v kapitole 12; u pentomin vychází z řešiče přesného pokrytí (kapitola 10). Hvězdičky: v klasické hře a pro děti podle skóre, v denní výzvě podle skóre počítače, u pentomin za vyřešení v časovém limitu bez nápovědy. Rekordy, hvězdičky, série denních výzev i rozehraná hra se ukládají jen ve vašem prohlížeči.
Část IZáklady
1

Kostky, tvary a historiezáklady

Všechny hlavolamy v průvodci stojí na jednom pojmu. Polyomino je tvar složený ze shodných čtverečků, které k sobě přiléhají celými hranami. Podle počtu čtverečků (kostek) se jmenují monomino (1), domino (2), trimino (3), tetromino (4), pentomino (5), hexomino (6) a dál. Dva čtverečky, které se dotýkají jen rohem, polyomino netvoří. Z polyomin se skládají dva druhy hlavolamů: skládání (každý kus jednou, oblast vyplnit beze zbytku) a skládačka na desce (kusy přicházejí po třech a plné řádky a sloupce mizí).

🧱

Vezměte dvě kostky domina a položte je vedle sebe. Půjde to dvěma způsoby: dlouhou stranou k sobě (čtverec), nebo krátkou (dlouhá čtyřka). Čtyři čtverečky se dají spojit pěti různými tvary – a pět čtverečků už dvanácti. Kolika způsoby šesti? Odpověď a proč ji nikdo nezná pro velké počty, je v kapitole 9.

Laboratoř tvarů
Klepáním na pole mřížky 5 × 5 přidávejte a odebírejte kostky. Laboratoř řekne, zda jde o polyomino, pojmenuje ho a ukáže všech osm natočení: otočení o 90°, 180°, 270° a zrcadlové obrazy. Natočení, která vypadají stejně jako některé dřívější, jsou zašedlá.
LABORATOŘ
Model: tvar je množina polí; je to polyomino, když se z každého pole dá dojít do každého jiného přes pole tvaru kroky nahoru, dolů, doleva a doprava. Natočení počítá laboratoř osmi shodnostmi čtverce (čtyři otočení a čtyři zrcadlení) a tvary porovnává po posunutí do levého horního rohu. Jména do pěti kostek jsou stejná jako v kapitole 2.
+Teorie: definice polyomina, jména podle velikosti, dva druhy hlavolamů a časová osa od roku 1907

1.1Polyomino přesně

Na čtverečkové síti očíslujte pole dvojicemi (x, y). Dvě pole sousedí, když se liší o 1 v jedné souřadnici a ve druhé se shodují – mají společnou hranu. Konečná množina polí je polyomino, když je souvislá: mezi každými dvěma jejími poli vede cesta po sousedních polích množiny.polyomino, edge-connected

Sousedství a polyomino\[ (x,y) \sim (x',y') \iff |x-x'| + |y-y'| = 1, \qquad P \text{ je polyomino} \iff P \text{ je konečná a souvislá vzhledem k } \sim \]

Dva tvary, které jdou na sebe posunout, jsou tentýž tvar. Zda za stejné považujeme i otočené a zrcadlové tvary, rozlišuje kapitola 2 (volné, jednostranné a pevné tvary). Souvislost přes rohy nestačí: dvě kostky, které se dotýkají jen rohem, nejsou domino – v laboratoři to ukazuje situace „dotek rohem“.

monomino
domino
trimino I
trimino L
tetromino I
tetromino O
tetromino T
tetromino L
tetromino S
Obr. 1.1Všechna polyomina do čtyř kostek, pokud otočené a zrcadlové tvary považujeme za stejné: jedno monomino, jedno domino, dvě trimina (rovné I a roh L) a pět tetromin (I, O, T, L, S). Zrcadlová L a J nebo S a Z se tu počítají jako jeden tvar.

1.2Dva druhy hlavolamů

  • Skládání (packing, tiling) – dána oblast a sada kusů, každý kus se použije právě jednou, kusy se nepřekrývají a oblast vyplní beze zbytku. Kusy jde většinou otáčet i převracet. Příklad: dvanáct pentomin do obdélníku 6 × 10 (kapitola 5) nebo sedm kusů do krychle 3 × 3 × 3 (kapitola 8).
  • Skládačka na desce (block puzzle) – deska 8 × 8, v zásobníku tři kusy. Každý kus položíte celý na volná pole; po položení všech tří přijdou další tři. Plný řádek nebo sloupec zmizí a uvolní místo, kusy nepadají. Hra končí, když se žádný ze zbylých kusů nevejde. Cílem je co nejvíc bodů (kapitoly 3, 4, 7 a 12).
1. deska a kus rovná čtveřice
kus v zásobníku
2. položený kus doplní řadu
3. řada zmizí
Obr. 1.2Jeden tah skládačky na desce 8 × 8 (deska z partie počítače na obtížnost 4). Rovná čtveřice ze zásobníku doplní řadu (oranžové rámečky), ta zmizí a uvolní osm polí. Kostky ostatních kusů zůstanou, kde byly – nic nepadá.
Příklad Kolik kostek má sada pentomin

Dvanáct pentomin má 12 · 5 = 60 kostek. Obdélník z nich proto musí mít plochu 60: 6 × 10, 5 × 12, 4 × 15, 3 × 20, 2 × 30 nebo 1 × 60. Poslední dva nejdou, protože kříž X je široký tři pole. Kolik řešení mají ostatní, spočítá laboratoř v kapitole 5.

1.3Časová osa

Tab. 1.1Od hlavolamu na šachovnici ke skládačkám na mobilu (zdroje v příloze C)
RokUdálost
1907Henry E. Dudeney ve sbírce The Canterbury Puzzles (úloha č. 74 „The Broken Chessboard“) skládá šachovnici z dvanácti pentomin a čtverce 2 × 2 – dávno před slovem pentomino.
1933Dánský básník a vynálezce Piet Hein vymýšlí krychli ze sedmi kusů; okolnosti vzniku uvádějí prameny různě (kapitola 8).
1953–1954Solomon W. Golomb zavádí slovo polyomino v přednášce na Harvardu (1953) a v článku Checker Boards and Polyominoes (American Mathematical Monthly, 1954).
1957Martin Gardner píše o polyominech ve sloupku Mathematical Games v Scientific American (podle seznamu sloupků v prosinci 1957).
1958Dana Scott nechá počítač v Princetonu najít všech 65 řešení šachovnice 8 × 8 bez středu 2 × 2 – jeden z prvních zveřejněných programů, které hledaly řešení hlavolamu prohledáváním s návratem.
1960C. B. a Jenifer Haselgroveovi publikují 2 339 řešení obdélníku 6 × 10.
1961John H. Conway a Richard K. Guy určí 240 řešení krychle ze sedmi kusů.
1965Golombova kniha Polyominoes (2. vydání 1994).
1984Alexej Pažitnov v Moskvě programuje hru s padajícími tetrominy na počítači Elektronika 60; řady se v ní mažou jen vodorovně.
2000Donald E. Knuth popisuje Algoritmus X s tancem odkazů (kapitola 10).
2003Demaine, Hohenberger a Liben-Nowell dokazují, že padající kostky se známou řadou kusů jsou NP-úplné (kapitola 11).
kolem 2014–2016Na mobilních telefonech se rozšiřují skládačky na desce bez padání, ve kterých mizí plné řádky i sloupce.
Z historie

Golomb byl v roce 1953 student na Harvardu a slovo polyomino utvořil podle slova domino. Jeho článek z roku 1954 už v názvu spojuje šachovnici s polyominy – zkoumá, kdy jde šachovnici, i s vynechanými poli, pokrýt kusy daného tvaru. Golombova kniha pak popularizovala pentomina natolik, že se z papírových kusů staly hry a stavebnice. Hra s padajícími kostkami vznikla jinde a nezávisle – její jméno spojuje řecké tetra (čtyři, tetromina) a tenis, Pažitnovův oblíbený sport. Podle oficiální historie byla hotová 6. června 1984, mimo Sovětský svaz se šířila od roku 1985.

1.4Proč polyomina baví i učí

Skládání tvarů trénuje prostorovou představivost – otočit kus v hlavě a odhadnout, zda se vejde. Matematice dávají polyomina nečekaně hluboké otázky: kolik jich je (kapitola 9), kdy jdou složit do obdélníku (kapitoly 5 a 6) a jak těžké je to rozhodnout (kapitola 11). Informatice slouží jako učebnicový příklad prohledávání s návratem: Scottův program z roku 1958 i Knuthův algoritmus z roku 2000 začínaly právě u pentomin.

Pozor

Tetromino není jen kus z padajících kostek. Slovo označuje jakýkoli tvar ze čtyř čtverečků; pět volných tetromin (kapitola 2) zná matematika od Golomba. Obchodní názvy her nejsou obecná jména tvarů – v průvodci se kusy jmenují podle tvaru a počtu kostek.

1.5Procvičení

1
Tři kostky leží v řadě, čtvrtá se dotýká prostřední jen rohem. Je to tetromino?
Ne. Čtvrtá kostka nesdílí hranu s žádnou jinou, takže tvar není souvislý přes hrany. Je to trimino I a samostatné monomino.
2
Kolik kostek má sada všech pěti tetromin (I, O, T, L, S) a dá se z ní složit obdélník 4 × 5?
Kostek je 5 · 4 = 20, takže plocha by seděla. Obdélník přesto nejde – důvod je paritní a ukazuje ho kapitola 6 (tetromino T kryje na šachovnici tři pole jedné barvy a jedno druhé). Řešič průvodce to ověřil úplným prohledáním: 0 řešení.
3
Kolika způsoby jde na prázdnou desku 8 × 8 položit domino?
Vodorovně má 7 poloh v každém z 8 řádků, svisle 7 v každém z 8 sloupců: 2 · 7 · 8 = 112. Obecně kus s obdélníkem w × h má na desce N × N právě (N − w + 1)(N − h + 1) poloh v každém natočení (kapitola 3).
4
V čem se liší skládání pentomin od skládačky na desce?
Při skládání znáte všechny kusy předem, každý použijete jednou a cílem je vyplnit oblast beze zbytku – je to hlavolam s řešením. Ve skládačce na desce kusy přicházejí postupně (po třech), řady mizí a cílem je vydržet a sbírat body – je to hra s náhodou, kde rozhoduje plánování.
5
Proč z dvanácti pentomin nejde složit obdélník 2 × 30?
Kříž X (a také F, T, V, W, Z) má v každém natočení výšku i šířku aspoň 3, do pásu vysokého 2 se nevejde. Plocha 60 sama nestačí – tvar kusů musí do oblasti pasovat.
Co si odnést
  • Polyomino = shodné čtverečky spojené celými hranami; jména podle počtu: monomino, domino, trimino, tetromino, pentomino…
  • Skládání = známé kusy, každý jednou, oblast beze zbytku; skládačka na desce = kusy po třech, plné řady mizí.
  • Od Dudeneyho šachovnice (1907) přes Golomba (1954) a padající kostky (1984) vede cesta k algoritmům a složitosti.
Část IZáklady
2

Rodina polyominzáklady

Kolik je tetromin? Záleží na tom, co považujeme za stejný tvar. Volné tvary smíme otáčet i převracet – tetromin je pak 5. Jednostranné smíme jen otáčet, jako kusy v padajících kostkách – je jich 7, protože L a J nebo S a Z jsou různé. Pevné neotáčíme vůbec, jako kusy na obtížnosti 3 až 5 skládačky na desce – těch je 19. Pentomin je volných 12 a mají jména podle písmen, která připomínají: F, I, L, N, P, T, U, V, W, X, Y, Z.

🔤

Pentomina si zapamatujete dvěma slovy: jméno FILiP (F, I, L, P) a konec abecedy TUVWXYZ. Chybí jen N – to je „zlomená“ čtyřka, jako písmeno N položené na bok.

Všechny tvary dané velikosti
Zvolte počet kostek a způsob počítání. Laboratoř vyrobí všechny tvary růstem – ke každému tvaru o kostku menšímu přidá kostku na každé volné sousední pole – a shodné tvary sloučí. Zvýrazněné jsou tvary s dírou.
LABORATOŘ
Model: tvar se zapíše jako seznam polí posunutý do levého horního rohu. Ze všech jeho natočení (8 u volných, 4 u jednostranných, 1 u pevných) se vybere „nejmenší“ zápis – kanonický tvar. Dva tvary jsou stejné, právě když mají stejný kanonický tvar. Stejnou metodou jsou spočítané tabulky 2.1 a 9.1.
Pojmenuj pentomino
Laboratoř ukáže pentomino v náhodném natočení – klidně otočené nebo zrcadlové. Klepněte na jeho písmeno. Správnou odpověď prozradí až vyhodnocení. Deset kol; za osm a víc správně je odměna.
MINIHRA
Jak to funguje: tvar se losuje z dvanácti pentomin a jedné z osmi shodností čtverce. Laboratoř pozná písmeno porovnáním kanonických tvarů, takže na natočení nezáleží.
+Teorie: volné, jednostranné a pevné tvary, osm shodností čtverce, souměrnosti pentomin a sady kusů skládačky

2.1Tři způsoby počítání

Shodnosti čtverce tvoří osm zobrazení: identita, otočení o 90°, 180° a 270° a čtyři zrcadlení (podle svislé, vodorovné a obou úhlopříčných os). Matematici jim říkají dihedrální grupa D4. Volné tvary jsou třídy tvarů, které na sebe jde převést kteroukoli z osmi shodností, jednostranné jen otočeními, pevné jen posunutím.free, one-sided, fixed polyominoes

Tab. 2.1Počty polyomin podle velikosti (spočítáno laboratoří a skriptem průvodce)
Kostek nVolnéJednostrannéPevnéVolné s dírou
11110
21120
32260
457190
51218630
635602160
71081967601
83697042 7256
91 2852 5009 91037
104 6559 18936 446195
Hodnoty souhlasí s posloupnostmi A000105 (volná), A000988 (jednostranná) a A001168 (pevná) v encyklopedii OEIS (příloha C). Tvar s dírou obklopuje volné pole, ke kterému se zvenku nedá dojít.

2.2Dvanáct pentomin

F
I
L
N
P
T
U
V
W
X
Y
Z
Obr. 2.1Dvanáct volných pentomin a jejich písmena. Barvy jsou stejné jako v laboratořích kapitol 5 a 10.

Jména podle písmen zavedl Golomb a používají se po celém světě. Některá písmena chtějí trochu fantazie: N je zlomená čtyřka, Y je čtyřka s výstupkem, W jsou schody, F se podobá malému psacímu f. V části literatury se pro některé kusy používají jiná písmena (například O místo I); průvodce drží Golombovo značení FILNPTUVWXYZ.

2.3Souměrnosti a počet natočení

Kolik různých natočení má tvar, záleží na tom, kolik z osmi shodností ho zobrazí samo na sebe – to je jeho souměrnost. Platí jednoduchý vztah: počet natočení krát počet souměrností je vždy 8. Tvar, jehož zrcadlový obraz nejde otočením získat zpět, je chirální (jako levá a pravá ruka).

Natočení a souměrnosti (věta o orbitě a stabilizátoru)\[ \#\text{natočení}(P) \cdot \#\text{souměrností}(P) = |D_4| = 8, \qquad \text{pevných} = \sum_{P \text{ volné}} \#\text{natočení}(P), \qquad \text{jednostranných} = \text{volných} + \#\text{chirálních} \]
Pentomino F: 8 různých natočení
0°
90°
180°
270°
zrcadlo
zrcadlo + 90°
zrcadlo + 180°
zrcadlo + 270°
Pentomino T: 4 různá natočení, zbytek se opakuje
0°
90°
180°
270°
stejné
stejné
stejné
stejné
Obr. 2.2Osm shodností použitých na pentomino F a T. F nemá žádnou souměrnost, proto má 8 různých natočení. T má osu souměrnosti, takže každé natočení se objeví dvakrát a různá jsou jen 4 (opakující se jsou šedá).
Tab. 2.2Pentomina podle souměrnosti
PentominaNatočeníSouměrnostíChirální
F, L, N, P, Y81ano
Z42 (otočení o 180°)ano
T, U, V, W42 (osa)ne
I24ne
X18ne
Kontrola: 5 · 8 + 4 + 4 · 4 + 2 + 1 = 63 pevných pentomin a 12 + 6 chirálních = 18 jednostranných – přesně jako v tab. 2.1.
Příklad Tetromina třikrát

Volná tetromina: I, O, T, L, S (5). Jednostranných je 7, protože L a S jsou chirální a přidají zrcadlová J a Z. Pevných: I má 2 natočení, O 1, T 4, L 8 (4 jako L, 4 jako J), S 4 (2 + 2): 2 + 1 + 4 + 8 + 4 = 19.

2.4Sady kusů ve skládačce na desce

Skládačka na desce v průvodci a ve 3D hře používá 21 typů kusů: jedna kostka, domino, rovné trimino, malý roh, čtverec 2 × 2, rovná čtveřice, T, L, J, S, Z, pětice, velký roh, dlouhé L a J, P a zrcadlové P, velké T, U, kříž a čtverec 3 × 3. Kusy jsou jednostranné – L a J jsou různé typy – a na obtížnostech 3 až 5 se ani neotáčejí, takže každé natočení je vlastně samostatný pevný kus. Čtverec 3 × 3 není polyomino z tabulky pentomin; je to velký „nonomino“ z devíti kostek a v kapitole 7 uvidíte, že je ze všech kusů nejnáročnější na místo.

Mistrovská pomůcka

Chirální kusy (L, J, S, Z, F, N, P, Y) poznáte rychle: zkuste si je představit převrácené na druhou stranu papíru. Když to nejde dostat zpět otáčením, jde o zrcadlovou dvojici. Ve skládačce bez otáčení se vyplatí pamatovat si, že L a J potřebují zrcadlově opačná místa.

2.5Procvičení

1
Kolik natočení má trimino L (malý roh) a je chirální?
Malý roh má osu souměrnosti po úhlopříčce, takže souměrnosti jsou 2 a natočení 8 / 2 = 4. Zrcadlový obraz je jen otočený roh – není chirální.
2
Proč je Z pentomino chirální, i když má souměrnost?
Jeho jediná netriviální souměrnost je otočení o 180°. Žádné zrcadlení ho nezobrazí samo na sebe, takže zrcadlový obraz (S pentomino) otočením nedostanete.
3
Hexomin je 35 volných a 60 jednostranných. Kolik z nich je chirálních?
Jednostranných = volných + chirálních, takže chirálních je 60 − 35 = 25.
4
Proč se počet pevných polyomin blíží osminásobku počtu volných?
Čím je tvar větší, tím vzácněji je souměrný. Tvar bez souměrnosti má 8 natočení. U n = 10 je 36 446 / 4 655 ≈ 7,83, a poměr se dál blíží 8 (kapitola 9).
5
Skládačka bez otáčení nabídne dlouhé L. Kolik různých kusů „dlouhé L nebo J“ může v zásobníku přijít?
Dlouhé L má jako jednostranný tvar 4 natočení a dlouhé J také 4. Bez otáčení jde tedy o 8 různých pevných kusů – přesně počet natočení volného L pentomina.
Co si odnést
  • Volné (otočit i převrátit), jednostranné (jen otočit), pevné (nic): tetromin je 5, 7 a 19.
  • Pentomin je 12: F, I, L, N, P, T, U, V, W, X, Y, Z; počet natočení × počet souměrností = 8.
  • Chirální tvary mají zrcadlového dvojníka, kterého otočením nezískáte.
Část IZáklady
3

Deska, řady a bodyzáklady

Skládačka na desce má jednoduchá pravidla. Deska má 8 × 8 polí, v zásobníku čekají tři kusy. Kus položíte celý na volná pole, kusy se nepřekrývají a nepadají. Když je řádek nebo sloupec plný, zmizí – a když kus doplní řádek i sloupec zároveň, zmizí oba naráz. Po položení všech tří kusů přijdou další tři. Hra končí, když se žádný ze zbylých kusů nikam nevejde. Za každou položenou kostku je 1 bod a za každé pole vymazané řady 10 bodů. Dvě základní techniky jsou Dokončit řadu (uvolnit místo, dokud to jde) a Místo pro velké kusy (nezasypat poslední prostor pro čtverec 3 × 3 a pětici).

📦

Je to jako stěhování do pokoje, ze kterého se plné police samy vyklidí. Kdo cpe krabice kamkoli, brzy zjistí, že velká skříň se už nevejde. Kdo nechává volný roh pro velké kusy a doplňuje police do plna, stěhuje se mnohem déle.

Kam s ním?
Na desce z partie počítače leží jeden kus k položení. Klepněte na pole, kam má přijít jeho levá horní kostka (v náhledu kusu je označená tečkou) – zelený náhled jde položit, červený ne. Tlačítkem Položit sem tah potvrdíte. Laboratoř pak porovná vaše místo se všemi ostatními podle hodnocení desky a prozradí, kde bylo nejlepší a proč.
MINIHRA
kus k položení
Jak to funguje: situace jsou desky z partií počítače na obtížnost 4. U každé byl rozdíl mezi nejlepším a druhým nejlepším místem aspoň 3 body hodnocení a nejlepší místo bylo jediné. Hodnocení po tahu = 12 za každou vymazanou řadu − 2 za každé osamělé pole + 4, když se ještě vejde čtverec 3 × 3, + 2, když se vejde pětice, − 1 za každou hranu mezi volným a plným polem (rozbitost). Proč právě tyto váhy, ukazuje kapitola 12.
+Teorie: pravidla přesně, body, současné mizení řádků a sloupců, techniky Dokončit řadu a Místo pro velké kusy, počty poloh

3.1Pravidla přesně

  • Deska má N × N polí (v klasické hře N = 8, pro děti 6). Na začátku je prázdná.
  • Zásobník nabízí tři kusy. Pořadí, ve kterém je položíte, je na vás. Nové tři kusy přijdou, až když položíte všechny.
  • Tah = položení jednoho kusu na volná pole uvnitř desky. Kus se nesmí překrývat s jinými kostkami a nepadá.
  • Mizení: po tahu se najdou všechny plné řádky a všechny plné sloupce a vymažou se současně. Kostka na křížení plného řádku a sloupce zmizí jednou.
  • Konec: když se žádný ze zbylých kusů zásobníku nevejde na žádné místo.

3.2Body

Tah s kusem z n kostek, který vymaže k řad, v sérii s tahů s vymazáním po sobě (s = 1 pro první z nich), dá:

Body za tah (průvodce i 3D hra)\[ \text{body} = n + 10 \cdot N \cdot k^2 \cdot \Big(1 + \tfrac{1}{2}(s-1)\Big), \qquad N = 8:\ \ k = 1 \to 80, \quad k = 2 \to 320, \quad k = 3 \to 720 \]

Deset bodů dostanete za každé pole vymazané řady (k · N polí) a celé se to násobí ještě k – proto má dvojité vymazání čtyřnásobek bodů jednoho a trojité devítinásobek. Sérii a bonus rozebírá kapitola 4.

malý roh doplní 3. řádek i 5. sloupec
oba zmizí naráz: 3 + 320 = 323 bodů
Obr. 3.1Řádek a sloupec mizí současně. Malý roh na polích ř3s5, ř3s6 a ř4s5 doplní 3. řádek i 5. sloupec (oranžové rámečky). Oba zmizí naráz, pole ř3s5 na jejich křížení jen jednou. Tah dá 3 body za kostky a 10 · 8 · 2² = 320 za dvě řady.
Příklad Kolik polí uvolní dvojité vymazání

Řádek a sloupec mají dohromady 8 + 8 − 1 = 15 polí (křížení se počítá jednou). V obr. 3.1 bylo před tahem plných 6 + 6 = 12 z nich a malý roh doplnil zbylá tři; po tahu se uvolní všech 15 polí. Dva řádky by uvolnily 16 polí.

3.3Technika Dokončit řadu

Každá vymazaná řada vrací desce 8 polí. Když jde kus položit tak, aby doplnil řadu, bývá to dobrý tah – nejen kvůli 80 bodům, ale hlavně kvůli místu. V minihře se tahy s vymazáním objevují nejčastěji: v hodnocení desky má vymazaná řada váhu 12, víc než kterákoli jiná část.

Pozor

Dokončit řadu neznamená položit kus kamkoli, kde řadu doplní. Pokud stejný tah vytvoří osamělé pole nebo zasype jediné místo pro čtverec 3 × 3, může být lepší řadu nechat na další kus. Proto minihra hodnotí celou desku po tahu, ne jen body.

3.4Technika Místo pro velké kusy

Čtverec 3 × 3 potřebuje volný blok devíti polí, pětice volný úsek pěti polí v řádku nebo sloupci. Na obtížnostech 3 až 5 přicházejí oba často. Dokud na desce zbývá místo pro každý z nich, nemůže vás žádný kus zaskočit tak snadno. Zkušení hráči proto skládají kusy k okrajům a k sobě a nechávají jeden velký volný blok.

lépe: zůstane místo pro čtverec 3 × 3 (zelené rámečky)
hůř: čtverec 3 × 3 se už nikam nevejde
Obr. 3.2Kus J na desce z partie (situace z minihry). Vlevo nejlepší položení podle hodnocení: zelený kus a zelené rámečky ukazují blok 3 × 3, který zůstal volný. Vpravo nejlépe hodnocené položení z těch, po kterých se čtverec 3 × 3 už nikam nevejde (červený kus). Ze 12 možných míst pro J nechává volný blok 3 × 3 jen 5; místo pro pětici zůstane po kterémkoli z nich.

3.5Kolik míst má kus

Kus s obdélníkovým obrysem w × h má na prázdné desce N × N v jednom natočení (N − w + 1)(N − h + 1) poloh. Tabulka sčítá natočení, která jsou ve hře s otáčením dostupná; bez otáčení má kus jen polohy svého jednoho natočení.

Tab. 3.1Počet poloh kusů na prázdné desce 8 × 8 (všechna otočení / počet otočení)
KusPolohOtočeníKusPolohOtočení
jedna kostka641Z842
domino1122pětice642
rovné trimino962velký roh1444
malý roh1964dlouhé L / J1404
čtverec 2 × 2491P / zrcadlové P1684
rovná čtveřice802velké T1444
T1684U1684
L / J1684kříž361
S842čtverec 3 × 3361
Spočítáno skriptem průvodce položením každého natočení na každé místo prázdné desky. Kříž a čtverec 3 × 3 mají nejméně poloh – na zaplněné desce se přestanou vejít jako první (kapitola 7).
Mistrovská pomůcka

Nejdřív pokládejte kusy, které mají nejméně míst. Velký kus, který se vejde jen na dvě místa, položte dřív než domino, které se vejde skoro kamkoli. Stejnou myšlenku používá počítač při skládání pentomin – vybírá pole s nejméně možnostmi (kapitoly 5 a 10).

3.6Procvičení

1
Rovná čtveřice doplní jeden řádek, žádná série neběží. Kolik bodů tah dá na desce 8 × 8?
4 body za kostky + 10 · 8 · 1² · 1 = 80 za řadu: 84 bodů.
2
Čtverec 3 × 3 doplní najednou tři řádky. Kolik bodů?
9 + 10 · 8 · 3² = 9 + 720 = 729 bodů (bez série).
3
Kolik poloh má čtverec 2 × 2 na prázdné desce 6 × 6 (režim pro děti)?
(6 − 2 + 1)² = 25.
4
Kus doplní 2. řádek a zároveň 7. sloupec. Kolik polí se uvolní a kolik řad se počítá do bodů?
Uvolní se 8 + 8 − 1 = 15 polí, do bodů se počítají 2 řady (k = 2, bonus 320 na desce 8 × 8).
5
Proč hodnocení desky odečítá „rozbitost“ (počet hran mezi volným a plným polem)?
Rozbitá deska má mnoho malých děr a výběžků, do kterých se velké kusy nevejdou. Hladká deska s jedním velkým volným blokem má malou rozbitost. Kapitola 12 ukazuje, že samotná rozbitost prodlouží hru počítače skoro čtyřikrát proti tahům „jen vymazat řadu“.
Co si odnést
  • Plné řádky a sloupce mizí současně; body = kostky + 10 · N · k² (a série).
  • Dokončit řadu vrací desce místo; Místo pro velké kusy hlídá blok 3 × 3 a úsek pro pětici.
  • Nejdřív pokládejte kusy s nejméně místy.
Část IZáklady
4

Pořadí kusů a sériezáklady

Tři kusy v zásobníku smíte položit v libovolném pořadí – a na pořadí často záleží víc než na místě. Řady totiž mizí hned po každém tahu: kus, který se teď nikam nevejde, může mít místo, až jiný kus doplní a vymaže řadu. Technika Pořadí kusů znamená promyslet všech šest pořadí dřív, než položíte první kus. Technika Dvojité vymazání sbírá řady tak, aby jeden kus vymazal dvě a víc naráz – bonus roste s druhou mocninou. A série odměňuje vymazání v tazích po sobě.

🎒

Do kufru se nejdřív dávají velké a nepoddajné věci a ponožky až nakonec do mezer. Kdo začne ponožkami, nemusí kufr zavřít. Se třemi kusy v zásobníku je to stejné – jen se kufr mezi kusy může sám uvolnit, když se zaplní řada.

Které pořadí projde?
Na desce z partie počítače (obtížnost 4, bez otáčení) čekají tři kusy. Vyberte pořadí, ve kterém jdou položit všechny tři. Pořadí jsou správně, když existují místa, kam kusy v tomto pořadí postupně položit (s mizením řad po každém tahu). Vyhodnocení ukáže všech šest pořadí a pro to vaše plán tahů.
MINIHRA
Jak to funguje: situace jsou desky z partií počítače, u kterých jdou všechny tři kusy položit nejvýš ve třech z šesti pořadí. Vyhodnocení zkouší pro každé pořadí všechna místa prvního kusu, po vymazání řad všechna místa druhého a pak třetího – úplné prohledání. Plán ukazuje nejvyšší možný počet bodů v daném pořadí.
Kalkulačka bodů
Nastavte velikost kusu, počet řad vymazaných naráz a délku série. Kalkulačka spočítá body za tah a porovná dvojité vymazání se dvěma jednoduchými po sobě.
LABORATOŘ
Model: body = n + 10 · N · k² · (1 + 0,5 · (s − 1)); s = 1 je první tah s vymazáním, každý další tah s vymazáním hned po něm zvýší s o 1, tah bez vymazání sérii ukončí. Stejné body počítá 3D hra.
+Teorie: šest pořadí, proč mizení řad mění situaci, Dvojité vymazání a série, kolik tahů prohledat

4.1Proč záleží na pořadí

Bez mizení řad by na pořadí skoro nezáleželo: kusy, které se vejdou všechny najednou, jde položit v jakémkoli pořadí na tatáž místa. Mizení všechno mění. Kus, který doplní řadu, uvolní až 8 polí (při řádku i sloupci 15) a dalšímu kusu otevře místa, která předtím neměl. Obráceně kus položený „do cesty“ může budoucí řadu zablokovat.

výchozí deska
kus 1: dlouhé J
kus 2: pětice
kus 3: čtverec 2 × 2
1. kus 3 (čtverec 2 × 2)
2. kus 2 (pětice) – 2 řady zmizí
3. kus 1 (dlouhé J)
Obr. 4.1Deska s 32 plnými poli a tři kusy: dlouhé J (kus 1), pětice (kus 2) a čtverec 2 × 2 (kus 3). Projdou jen pořadí 2-3-1 a 3-2-1. Dole plán pořadí 3-2-1: čtverec do levého dolního rohu, pětice doplní dvě řady naráz a dlouhé J se vejde do uvolněného místa. Plán dá 334 bodů, pořadí 2-3-1 nejvýš 174.
Příklad Rozbor obr. 4.1

Na výchozí desce má dlouhé J jen 4 místa, pětice 4 a čtverec 6. Kdo začne dlouhým J, prohraje v obou pořadích – ať ho položí kamkoli, zbylé dva kusy se už oba nevejdou. Začít čtvercem jde: ze šesti jeho míst vedou tři k úspěchu. Začít pětici jde jen z jednoho ze čtyř míst. Celé rozhodnutí vyžadovalo 76 zkusmých položení – tolik jich udělalo úplné prohledání všech šesti pořadí.

4.2Kolik tahů prohledat

Pořadí tří kusů je 3! = 6. Má-li první kus p1 míst, druhý po něm p2 a třetí p3, je v jednom pořadí nejvýš p1 · p2 · p3 plánů. Na poloprázdné desce to jsou statisíce, na zaplněné desce desítky – a právě tam jde o všechno. S otáčením se počty míst násobí počtem otočení.

Velikost prohledávání jednoho zásobníku\[ \#\text{plánů} \le \sum_{\pi \in S_3} p_{\pi(1)} \cdot p_{\pi(2)} \cdot p_{\pi(3)}, \qquad |S_3| = 3! = 6 \]
Mistrovská pomůcka

Než položíte první kus, zeptejte se u každého: kam by šel, kdyby byl poslední? Kus s nejméně místy (často čtverec 3 × 3, pětice nebo kříž) položte jako první – nebo hned po kusu, který mu vymazáním řady místo uvolní. Malé kusy (domino, jedna kostka) si nechte na konec, ty se vejdou skoro vždy.

4.3Dvojité vymazání a série

Tab. 4.1Bonus za vymazané řady na desce 8 × 8 (bez bodů za kostky)
Řad naráz ks = 1s = 2s = 3s = 4
180120160200
2320480640800
37201 0801 4401 800
41 2801 9202 5603 200
10 · 8 · k² · (1 + 0,5 · (s − 1)). Čtverec 3 × 3 může doplnit až tři řádky a tři sloupce naráz (k = 6, bonus 2 880).

Dvojité vymazání se vyplatí: dvě řady jedním kusem dají 320, dvě řady dvěma kusy po sobě 80 + 120 = 200 a dvě řady s přestávkou jen 80 + 80 = 160. Proto hráči řady „nabíjejí“ – doplňují dvě sousední řady skoro do plna a pak je vymažou jedním kusem. Riziko je zřejmé: dokud je řada skoro plná, zabírá místo.

Pozor

Honba za dvojitým vymazáním končí často dřív, než začne. V simulacích kapitoly 12 vydrží počítač, který vymazává co nejvíc řad hned („hladová“ strategie), na obtížnosti 4 v průměru jen asi 18 tahů – proti 64 tahům strategie, která hodnotí celou desku. Body z dlouhé hry jsou vždy vyšší než bonus z krátké.

4.4Procvičení

1
Kolik je pořadí tří kusů, když dva z nich jsou stejné (třeba dvě domina)?
Stejné kusy prohodit nemá smysl: 3! / 2! = 3 různá pořadí (podle toho, kdy přijde ten jiný kus).
2
Série: v tazích po sobě vymažete 1, 1 a 1 řadu. Kolik bodů dají řady celkem (deska 8 × 8)?
80 · 1 + 80 · 1,5 + 80 · 2 = 80 + 120 + 160 = 360 bodů.
3
Co dá víc: dvojité vymazání v prvním tahu série, nebo dvě jednoduchá vymazání ve 3. a 4. tahu série?
Dvojité: 320. Jednoduchá v sérii 3 a 4: 160 + 200 = 360. Dlouhá série tu vyhraje – ale udržet sérii tři tahy je těžší než jedno dvojité vymazání.
4
První kus má 10 míst, druhý po něm vždy 8 a třetí 5. Kolik plánů nejvýš prohledá počítač v jednom pořadí?
10 · 8 · 5 = 400. Ve všech šesti pořadích dohromady nejvýš šestkrát tolik, pokud mají kusy podobně míst; ve skutečnosti se počty míst po každém tahu mění.
5
Proč férový zásobník (obtížnosti 1–3) neznamená, že jde položit kusy v libovolném pořadí?
Férový zásobník zaručuje jen, že existuje pořadí a místa, kam jdou položit všechny tři. Kapitola 12 ukazuje, jak ho hra vybírá: kusy se losují postupně a každý další se musí vejít po položení předchozích. Špatné pořadí nebo místo může zásobník „zkazit“.
Co si odnést
  • Řady mizí po každém tahu, proto může kus, který se teď nevejde, dostat místo – rozhodujte o pořadí předem.
  • Kus s nejméně místy dejte dopředu, malé kusy na konec.
  • Bonus roste s k²: dvojité vymazání 320 proti 80; série přidává +50 % za každý další tah.
Část IIPokročilí
5

Pentomina na obdélníkupokročilí

Dvanáct pentomin má 60 kostek a jde z nich složit obdélník 6 × 10, 5 × 12, 4 × 15 i 3 × 20. Kolika způsoby? Obdélník 6 × 10 má 2 339 řešení, 5 × 12 jich má 1 010, 4 × 15 368 a úzký 3 × 20 jen 2 – otočené a zrcadlové kopie se nepočítají. Šachovnice 8 × 8 bez středního čtverce 2 × 2 má 65 řešení. Kdo skládá rukou, začíná nejlépe technikou Úzké místo: najde volné pole, kam se vejde nejméně kusů, a vyplní ho jako první.

🧭

Při skládání puzzle začínáte rohy a okraji – mají nejméně možností, takže chyba se ukáže hned. U pentomin je „roh“ každé pole, kam se vejde jen pár kusů: často kout, úzká chodbička nebo díra vedle už položených kusů.

Řešič pentomin
Zvolte oblast. Najít řešení vyskládá jedno náhodné řešení (řešič zkouší kusy v náhodném pořadí). Spočítat všechna projde všechny možnosti a řešení sečte – u 6 × 10 to v prohlížeči trvá několik sekund, průběh vidíte v počítadle uzlů.
LABORATOŘ
Model: úloha přesného pokrytí – každé pole oblasti a každý z dvanácti kusů musí být pokrytý právě jednou. Řešič je Algoritmus X s tancem odkazů z kapitoly 10, v každém kroku vybírá pole nebo kus s nejméně možnostmi. Počet všech řešení zahrnuje otočené a zrcadlené kopie; různých řešení je čtvrtina (u šachovnice osmina), viz oddíl 5.3.
Kde je úzké místo?
Obdélník 6 × 10 je rozpracovaný, zbývají čtyři kusy. Klepněte na volné pole, kam se podle vás vejde nejméně poloh zbylých kusů. Vyhodnocení u každého volného pole ukáže, kolik poloh ho pokrývá.
MINIHRA
Jak to funguje: úlohy vznikly z řešení obdélníku 6 × 10 odebráním čtyř kusů; u každé má nejvýš dvě pole nejmenší počet možností. Poloha se počítá se všemi natočeními včetně zrcadlení, i když by kus na tom místě nakonec nešel doskládat. Správně je kterékoli pole s nejmenším počtem.
+Teorie: které obdélníky jdou, počty řešení a jak je počítat, proč dělit čtyřmi, Úzké místo a historie výpočtů

5.1Které oblasti přicházejí v úvahu

Plocha musí být 60. Obdélníky 6 × 10, 5 × 12, 4 × 15, 3 × 20 řešení mají, 2 × 30 a 1 × 60 ne (kříž X je široký 3). Z šachovnice 8 × 8 je třeba vynechat 4 pole – nejznámější je vynechat střední čtverec 2 × 2. Hlavolamů je mnohem víc: krabice 3 × 4 × 5 z pentomin v prostoru, dva obdélníky 5 × 6 naráz, tvary zvířat… Řešič z laboratoře zvládne jakoukoli oblast, kterou zapíšete jako množinu polí.

5.2Počty řešení

Tab. 5.1Počty řešení spočítané řešičem průvodce (Algoritmus X, výběr sloupce s nejméně možnostmi)
OblastRůzných řešeníVšech řešeníŘádků maticeUzlů prohledáváníČas
6 × 102 3399 3562 0564 056 4457,9 s
5 × 121 0104 0401 9362 488 5255,2 s
4 × 153681 4721 696933 2881,9 s
3 × 20281 23635 7250,07 s
8 × 8 bez středu 2 × 2655201 568319 0740,6 s
Matice má 72 sloupců (60 polí a 12 kusů). Řádek = jedno umístění jednoho kusu v jednom natočení. Uzel = položení řádku během prohledávání. Čas na běžném notebooku v Node.js; v prohlížeči podobně. Hodnoty souhlasí s literaturou v příloze C.
LLXFFTTTWWLXXXFFTWWNLUXUFZTWNNLUUUYZZZNVPPPYYYYZNVPPIIIIIVVV
6 × 10 – 2 339 řešení
LLXUUTTTPPPYLXXXUVTWPPYYLFXUUVTWWZZYLFFVVVNNWWZYFFIIIIINNNZZ
5 × 12 – 1 010 řešení
LLXFFPPPIIIIIZZLXXXFFPPWWTTTZVLUXUFNNNYWWTZZVLUUUNNYYYYWTVVV
4 × 15 – 368 řešení
UUXIIIIINNNFTWYYYYZVUXXXPPLNNFFFTWWYZZZVUUXPPPLLLLFTTTWWZVVV
3 × 20 – 2 řešení
Obr. 5.1Jedno řešení každého obdélníku – první, které řešič najde. Obdélník 3 × 20 má jen dvě řešení: obě mají vlevo stejné kusy U, X, I a P a vpravo V, liší se jen prostřední částí.
LLXUUVVVLXXXUVZZLFXUUVZNLFFZZNFFYWNNYYYYWWNTPPPWWTTTPPIIIIIT
Obr. 5.2Šachovnice 8 × 8 bez středního čtverce 2 × 2 – jedno z 65 řešení. Tuto úlohu nechal v roce 1958 vyřešit počítačem Dana Scott.

5.3Proč dělit čtyřmi

Obdélník má čtyři souměrnosti: identitu, otočení o 180° a zrcadlení podle svislé a vodorovné osy. Každé řešení tak dává čtyři kopie. Mohly by dvě z nich splývat? Jen kdyby řešení bylo samo souměrné. Pak by souměrnost musela zobrazit každý kus na stejný kus (všech dvanáct je různých), tedy na sebe – a to u zrcadlení vylučují chirální kusy F, L, N, P, Y, Z (žádný nemá osu souměrnosti) a u otočení o 180° kusy jako F, L, P nebo Y, které nemají ani tuto souměrnost. Žádné řešení proto souměrné není a všech řešení je přesně čtyřikrát víc než různých. U čtvercové šachovnice bez středu je souměrností osm.

Různá řešení\[ \#\text{různých} = \frac{\#\text{všech}}{|G|}, \qquad |G| = 4 \text{ (obdélník)}, \ 8 \text{ (čtverec)}; \qquad 9\,356 / 4 = 2\,339 \]
Tab. 5.2Počet umístění kusů na obdélníku 6 × 10 (všechna natočení včetně zrcadlení)
FILNPTUVWXYZ
2565624824830412815212812832248128
Součet 2 056 = počet řádků matice. Kříž X má jen 32 umístění – je to „úzké místo“ mezi kusy a řešič ho volí brzy.

5.4Technika Úzké místo

Pro každé volné pole spočítejte, kolik umístění zbylých kusů ho pokrývá. Pole s nejmenším počtem vyplňte jako první a vyzkoušejte všechny jeho možnosti. Má-li nějaké pole nulu, je rozpracované řešení mrtvé a je třeba se vrátit. Má-li jedničku, je tah vynucený. To je lidská podoba heuristiky, které počítač říká výběr sloupce s nejméně možnostmi (kapitola 10).

UUX23511TTTUXXX1F2012TIUUXFFF2215TIPZZ2F123016VIPPZ716242513VIPPZZ68VVVI
Obr. 5.3První úloha minihry: zbývají kusy N, W, Y a L. Čísla v prázdných polích říkají, kolik umístění zbylých kusů pole pokrývá (všech umístění je 50). Oranžové pole má jedinou možnost – tah je vynucený. Nejvíc možností má jedno pole (30). Úloha má jediné dokončení.
Tab. 5.3Kolik uzlů potřebuje řešič k prvnímu řešení
OblastPole s nejméně možnostmiVždy první volné pole
6 × 10862301 017
5 × 121 071485 230
4 × 1521664 105
3 × 20238868 699 875
„První volné pole“ = pole nejvíc vlevo nahoře, jak by postupoval člověk bez rozmyslu. U 3 × 20 to trvalo přes deset minut, s výběrem úzkého místa zlomek sekundy.
Z historie

Dana Scott, tehdy student v Princetonu, v roce 1958 nechal univerzitní počítač najít všechna řešení šachovnice bez středu – 65. Souměrné kopie vyloučil tím, že kříž X zkoušel jen v několika polohách, které se souměrností šachovnice nedají převést jedna na druhou. Obdélník 6 × 10 a jeho 2 339 řešení spočítali C. B. Haselgrove a Jenifer Haselgroveová; výsledek vyšel v roce 1960 v britském studentském časopise Eureka. Knuth v článku o tanci odkazů (2000) použil pentomina jako hlavní příklad.

Mistrovská pomůcka

Při skládání rukou umístěte nejdřív kříž X – má nejméně poloh a jeho okolí je těžké vyplnit. Pak hlídejte kouty a okraje: do rohu obdélníku se vejde jen pár kusů. Vzniklá díra o velikosti, která není násobkem pěti, znamená slepou uličku – oblast se dá vyplnit jen pentominy, tedy po pěti polích.

5.5Procvičení

1
Při skládání vznikla uzavřená díra ze 7 volných polí. Jde ji vyplnit?
Ne. Každý kus má 5 polí, uzavřenou oblast lze vyplnit jen celými kusy – její plocha musí být násobek 5. Díra 7 polí znamená slepou uličku.
2
Řešič našel u obdélníku 5 × 12 celkem 4 040 řešení. Kolik je různých?
4 040 / 4 = 1 010 (obdélník má 4 souměrnosti a žádné řešení není souměrné).
3
Proč šachovnice bez středu dělí počet všech řešení osmi?
Čtverec s dírou uprostřed má všech 8 souměrností (4 otočení a 4 zrcadlení) a žádné řešení není samo souměrné: 520 / 8 = 65.
4
Volné pole pokrývá 0 umístění zbylých kusů. Co to znamená?
Rozpracovaná deska nemá dokončení – na toto pole se už žádný kus nevejde. Je třeba vrátit některý dřívější tah. Řešič takovou větev pozná okamžitě, když vybírá sloupec s nejméně možnostmi.
5
Proč je 3 × 20 pro řešiče s výběrem prvního volného pole tak těžké?
Pole vlevo nahoře pokrývá mnoho kusů, ale skoro žádné z nich nevedou k řešení; chyba se ukáže až daleko vpravo. Řešič tak prozkoumá obrovské množství slepých začátků (868 699 875 uzlů). Výběr úzkého místa začne poli, kde je jen pár možností, a slepé větve uřízne hned.
Co si odnést
  • 6 × 10: 2 339 řešení, 5 × 12: 1 010, 4 × 15: 368, 3 × 20: 2, šachovnice bez středu: 65 (bez souměrných kopií).
  • Všech řešení je 4× (u čtverce 8×) víc, protože žádné řešení není samo souměrné.
  • Úzké místo: začněte polem, kam se vejde nejméně kusů; nula = vrátit se, jednička = vynucený tah.
Část IIPokročilí
6

Parita a obarvenípokročilí

Jak dokázat, že hlavolam nemá řešení, aniž zkusíte všechny možnosti? Obarvěte pole a počítejte barvy. Šachovnice bez dvou protilehlých rohů má 32 polí jedné barvy a 30 druhé – a každé domino kryje jedno tmavé a jedno světlé pole. 31 domin ji proto pokrýt nemůže. Stejný trik s pruhy, úhlopříčkami nebo třemi a čtyřmi barvami rozhodne o mnoha dalších úlohách: proč pět tetromin netvoří obdélník, proč devět L nepokryje čtverec 6 × 6 a proč 35 hexomin nepokryje žádný obdélník.

♟️

Šachový střelec na bílém poli zůstane na bílém celou partii. Barva je invariant – vlastnost, kterou tah nezmění. Paritní důkazy hledají invariant, který každý kus splní a celá oblast poruší.

Laboratoř obarvení
Zvolte oblast a způsob obarvení. Laboratoř spočítá pole každé barvy. Porovnejte to s tím, kolik polí které barvy kryje jeden kus – v textu pod laboratoří a v teorii.
LABORATOŘ
Model: šachovnice = barva (řádek + sloupec) mod 2, pruhy = sloupec mod 2, 3 barvy = (řádek + sloupec) mod 3, 4 barvy = (řádek + sloupec) mod 4. Domino kryje na šachovnici 1 : 1, rovné trimino na třech barvách 1 : 1 : 1 a rovná čtveřice na čtyřech barvách 1 : 1 : 1 : 1 – v každé poloze.
Jde, nebo nejde?
Laboratoř ukáže oblast a kusy. Rozhodněte, zda z nich jde oblast poskládat. Teprve po odpovědi prozradí, jak to je, proč – obvykle obarvením – a co našel řešič.
MINIHRA
Jak to funguje: čtrnáct úloh, u každé je výsledek ověřený úplným prohledáním řešičem průvodce (počet pokrytí a uzlů ukáže vyhodnocení). Kde pokrytí existuje, laboratoř jedno najde a nakreslí.
+Teorie: šachovnicový argument, tetromina T a L, pruhy a úhlopříčky, tři barvy na čtverci 5 × 5, hexomina a meze paritních důkazů

6.1Šachovnicový argument

Obarvěte oblast jako šachovnici. Pro každý kus spočítejte rozdíl tmavá − světlá polí, která kryje; u nesouměrného kusu se znaménko může podle polohy otočit, absolutní hodnota (nerovnováha) zůstává. Součet rozdílů všech kusů se musí rovnat rozdílu barev oblasti.checkerboard colouring argument

Paritní podmínka\[ \sum_{\text{kusy } i} \varepsilon_i\, d_i = D_{\text{oblast}}, \qquad \varepsilon_i \in \{+1, -1\}, \quad d_i = |\text{tmavá}_i - \text{světlá}_i| \]
bez rohů a1 a h8: 32 polí jedné barvy, 30 druhé
každé domino kryje jedno pole každé barvy
Obr. 6.1Šachovnice bez dvou protilehlých rohů. Oba rohy mají stejnou barvu, zbude 32 polí jedné barvy a 30 druhé. Každé domino (vpravo dvě ukázky) kryje jedno pole každé barvy, 31 domin tedy kryje 31 a 31.
Z historie

Úlohu o prořezané šachovnici uvádí filozof Max Black v knize Critical Thinking (1946), později George Gamow a Marvin Stern v knížce hlavolamů Puzzle-Math (1958) a Martin Gardner v únoru 1957 v Scientific American. Elegantní řešení obarvením se často připisuje Golombovi, ten ho ale převzal z dřívější tradice; kdo ho vymyslel první, není jisté. Řešič průvodce ověřil, že pokrytí opravdu neexistuje – bez obarvení na to potřeboval 1 213 564 uzlů.

6.2Tetromino T a pět tetromin

Tetromina I, O, L a S kryjí na šachovnici vždy 2 : 2. Jen T kryje 3 : 1 (obr. 6.2). Pět volných tetromin tak dá nerovnováhu ±2 – a každý obdélník s plochou 20 má barvy vyrovnané. Proto z nich nejde žádný obdélník, a ze sedmi jednostranných tetromin (I, O, T, L, J, S, Z) ze stejného důvodu ani obdélník 4 × 7. Čtyři T pokryjí čtverec 4 × 4 (dvě z nich položené „tmavě“, dvě „světle“), šest T ale obdélník 4 × 6 nepokryje, i když barvy sedí: parita je nutná podmínka, ne postačující. D. W. Walkup v roce 1965 dokázal, že tetromina T pokryjí obdélník, právě když jsou obě jeho strany dělitelné čtyřmi.

T na šachovnici: 3 : 1
L na svislých pruzích: 3 : 1
rovná čtveřice na 4 barvách: 1 : 1 : 1 : 1
Obr. 6.2Tři obarvení a tři kusy, které je „poruší“ nebo „splní“. T kryje na šachovnici 3 : 1, L na svislých pruzích 3 : 1, rovná čtveřice na čtyřech barvách po úhlopříčkách každou barvu právě jednou.

6.3Pruhy: proč devět L nepokryje 6 × 6

Na šachovnici kryje L 2 : 2 a nic nepozná. Obarvěte ale sloupce střídavě. L má tři kostky v jednom sloupci nebo řádku a jednu vedle – na pruzích kryje vždy 3 : 1 (rozdíl ±2). Devět kusů dá součet devíti čísel ±2. Počet kladných a záporných se liší o liché číslo, takže součet není nula. Čtverec 6 × 6 má pruhy 18 : 18. Obdélník 4 × 6 ze šesti L jde – tři kusy +2 a tři −2 – a řešič najde 42 pokrytí.

Příklad Rovné čtveřice a čtverec 6 × 6

Obarvěte pole čtyřmi barvami podle (řádek + sloupec) mod 4. Rovná čtveřice kryje vodorovně i svisle čtyři po sobě jdoucí hodnoty, tedy každou barvu jednou. Čtverec 6 × 6 má barvy 9, 10, 9 a 8 – nestejně, takže devět rovných čtveřic ho nepokryje. Stejně dopadne slavná úloha 10 × 10 z 25 čtveřic: barvy 25, 26, 25 a 24.

6.4Tři barvy na čtverci 5 × 5

Ze čtverce 5 × 5 vynechte jedno pole a zbytek pokryjte osmi rovnými trimino. Které pole smí chybět? Obarvěte pole třemi barvami po úhlopříčkách zleva, (řádek + sloupec) mod 3, a podruhé zprava, (sloupec − řádek) mod 3. Rovné trimino kryje v obou obarveních každou barvu jednou. V obou obarveních je jedna barva „nadbytečná“ (9 polí místo 8) a vynechané pole ji musí mít v obou zároveň. To splní jen střed.

abcabbcabccabcaabcabbcabc
barvy a/b/c: 8 / 9 / 8
abcabcabcabcabcabcabcabca
barvy a/b/c: 9 / 8 / 8
Obr. 6.3Dvě obarvení čtverce 5 × 5 třemi barvami a, b, c. Vlevo má 9 polí barva b, vpravo barva a. Jen střed (oranžový rámeček) je v obou obarveních nadbytečné barvy. Řešič potvrdil: bez středu 2 pokrytí, bez rohu i bez pole ř1s2 žádné.

6.5Hexomina a pentomina

Ze 35 hexomin jich 24 kryje na šachovnici 3 : 3 a 11 kryje 4 : 2 (spočítáno skriptem průvodce). Celková nerovnováha je součet jedenácti čísel ±2 – liché množství, takže nemůže být nula. Každý obdélník s plochou 6 · 35 = 210 má ale barvy vyrovnané (sudá plocha obdélníku = stejně tmavých a světlých polí). Proto 35 hexomin nepokryje žádný obdélník. U pentomin šachovnice nic nezakáže: X kryje 4 : 1 (rozdíl 3), ostatní 3 : 2 (rozdíl 1), a jedenáct čísel ±1 se dá s ±3 složit na nulu.

Pozor

Obarvení dokazuje jen „nejde“. Když barvy sedí, o řešení to nic neříká – rozhodne až konstrukce nebo řešič. Úlohy 4 × 6 ze šesti T a 6 × 6 z devíti L ukazují, že správné obarvení se musí hledat: šachovnice nepozná nic, pruhy u L ano, u T teprve složitější úvaha.

Mistrovská pomůcka

U úlohy „jde, nebo nejde“ si nejdřív ověřte plochu, pak zkuste šachovnici, pak pruhy a nakonec barvy po úhlopříčkách s tolika barvami, kolik je dlouhý rovný kus. Teprve když nic nezabere, začněte skládat.

6.6Procvičení

1
Šachovnici 8 × 8 chybí dva rohy v jednom sloupci. Jde ji pokrýt 31 dominy?
Rohy v jednom sloupci mají opačné barvy, zbude 31 : 31 – obarvení nic nezakáže. A pokrytí existuje: sloupec bez rohů má 6 polí (3 svislá domina), ostatní sloupce po 4 svislých dominech.
2
Kolik tmavých a světlých polí kryje pentomino X?
Střed má jednu barvu a čtyři ramena druhou: 4 : 1 nebo 1 : 4, nerovnováha 3.
3
Mohou dvě T tetromina pokrýt obdélník 2 × 4?
Barvy by šly (jedno T 3 : 1, druhé 1 : 3), ale tvar ne: T zasahuje do dvou řádků výčnělkem a druhé T by muselo vyplnit dvě oddělené díry. Nejde – a Walkupova věta to potvrzuje (2 není násobek 4).
4
Obdélník 3 × 5 bez jednoho pole pokrýt rovnými trimino (14 polí)?
Nejde nikdy: 14 není dělitelné třemi. Plocha je první kontrola, ještě před obarvením.
5
Proč obdélník se sudou plochou má stejně tmavých a světlých polí?
Sudá plocha znamená, že aspoň jedna strana je sudá. Pak se obdélník rozpadne na pásy dlouhé 2 ve směru této strany a každý pás má jedno pole každé barvy.
Co si odnést
  • Obarvení je invariant: když každý kus kryje barvy jinak, než je má oblast, úloha nemá řešení.
  • Šachovnice (domina, T), pruhy (L), úhlopříčky s k barvami (rovné kusy délky k).
  • Obarvení dokáže jen „nejde“; „jde“ dokáže až řešení.
Část IIPokročilí
7

Riziko a osamělá polepokročilí

Dokud je deska poloprázdná, vejde se skoro každý kus. S přibývajícími kostkami ale riziko neroste pozvolna, nýbrž prudce: na obtížnosti 4 se při 16 až 23 plných polích nevejde náhodný kus jen ve 2 zásobnících z tisíce, při 40 až 47 plných polích už ve třetině případů. Nejdřív přestane mít místo čtverec 3 × 3. Druhým nepřítelem jsou osamělá pole – volná pole, která nemají volného souseda. Vejde se do nich jen jedna kostka a zabírají místo, dokud je nevymaže celá řada. Technika Bez osamělých polí je nevytvářet.

🅿️

Na parkovišti, kde každý zaparkuje kousek od ostatních, zbudou mezi auty mezery, do kterých se nevejde nikdo. Kdo parkuje těsně vedle souseda, nechává volný celý zbytek řady.

Simulace rizika
Počítač odehraje sérii her se strategií hodnocení desky z kapitoly 12. Před každým zásobníkem si zapíše, kolik polí je plných a jaká je pravděpodobnost, že se náhodný kus dané obtížnosti nikam nevejde. Graf ukazuje výsledek vaší simulace (body) a referenční simulaci tisíce her (čára).
LABORATOŘ
Model: deska 8 × 8, náhodný zásobník (obtížnost 4 a 5 bez férového výběru), kusy bez otáčení s váhami losování jako ve hře. Riziko v jednom stavu = součet vah typů kusů, které se nikam nevejdou, děleno součtem všech vah. Stavy se seskupují podle počtu plných polí po osmi. Referenční čára: 1 000 her stejným kódem.
Najdi osamělá pole
Klepnutím označte všechna volná pole, která nemají žádného volného souseda (nahoře, dole, vlevo ani vpravo). Opětovné klepnutí značku zruší. Pak stiskněte Vyhodnotit.
MINIHRA
správně nalezenépřehlédnutéoznačené navíc
Jak to funguje: desky pocházejí z partií, ve kterých počítač pokládal kusy náhodně – tak osamělá pole vznikají nejčastěji. Každá deska má 2 až 4 osamělá pole. Úhlopříční sousedé se nepočítají: do pole bez volného souseda přes hranu se vejde jen jedna kostka.
+Teorie: riziko podle zaplnění, které kusy přestanou mít místo, osamělá pole, rozbitost desky a zdravé hraní

7.1Riziko podle zaplnění

Tab. 7.1Kolik procent stavů, ve kterých se daný kus nikam nevejde (obtížnost 4, 1 000 her)
Plných políStavůNáhodný kus3 × 3PěticeVelký rohKříž2 × 2Rovná čtveřiceMalý roh
0–154 2450,00,10,00,00,00,00,00,0
16–237 0190,22,80,70,00,00,00,00,0
24–316 6331,715,55,01,72,10,00,30,0
32–392 3859,752,519,916,622,02,43,30,1
40–4730232,992,147,057,467,221,521,43,6
Stav = deska před příchodem zásobníku. Hry odehrál počítač se strategií hodnocení desky (kapitola 12), v průměru 60,5 tahu na hru; desky s 48 a více plnými poli se vyskytly jen dvakrát. Domino se nikdy nestalo nepoložitelným. Obtížnost 5: v průměru 35,8 tahu, náhodný kus se nevejde v 15,4 % stavů s 32–39 plnými poli a ve 42,5 % stavů se 40–47.
0 %20 %40 %60 %80 %100 %081624324048plných polí na desce 8 × 8 (skupiny po 8)kus se nikam nevejdenáhodný kus, obtížnost 4obtížnost 5čtverec 3 × 3pětice
Obr. 7.1Riziko roste s počtem plných polí prudce. Modře pravděpodobnost, že se náhodný kus obtížnosti 4 nikam nevejde, šedě totéž na obtížnosti 5, oranžově čárkovaně čtverec 3 × 3, zeleně čárkovaně pětice. Data z tab. 7.1.

Proč tak prudce? Volné místo se s každou kostkou nejen zmenšuje, ale i trhá. Čtverec 3 × 3 potřebuje souvislý blok, kterých na desce s 32 plnými poli bývá málo – i když volných polí je ještě 32. Odtud praktické pravidlo: držte desku pod polovinou. Kdo má trvale přes 32 plných polí, hraje s rizikem kolem 10 % na každý náhodný kus.

Příklad Riziko celého zásobníku

Při 32–39 plných polích se náhodný kus nevejde s pravděpodobností asi 9,7 %. Zásobník tří nezávislých kusů obsahuje aspoň jeden takový s pravděpodobností 1 − 0,903³ ≈ 26 %. To je hrubý odhad (kusy se navzájem ovlivňují a řady mezi tahy mizí), ale ukazuje, proč je deska s víc než 32 plnými poli nebezpečná.

7.2Osamělá pole

Volné pole je osamělé, když jeho čtyři sousedé přes hranu jsou plní nebo mimo desku. Na obtížnosti 3 až 5 přijde jedna kostka zřídka (má malou váhu losování), takže osamělé pole obvykle zmizí až s celou řadou – a ta se kvůli němu hůř doplňuje.isolated cell

Obr. 7.2Deska z partie s náhodnými tahy, ve které vznikla dvě osamělá pole (červené rámečky). Do žádného se nevejde nic většího než jedna kostka a obě blokují svůj řádek i sloupec.
Osamělá pole a rozbitost desky\[ \text{osamělá} = \#\{\, v \text{ volné} : \text{žádný soused } v \text{ není volný} \,\}, \qquad \text{rozbitost} = \#\{\, \text{hrany mezi volným a plným polem} \,\} \]

Jak moc osamělá pole škodí, ukazuje simulace (kapitola 12, 400 her na obtížnost 4): počítač, který jen vymazává řady, vytvoří v průměru 0,64 osamělého pole na tah; když za osamělé pole dostane trest, jen 0,10. Samotný trest za osamělá pole ale hru skoro neprodlouží (15,3 → 15,8 tahu). Mnohem víc pomůže hlídat celou rozbitost desky – počet hran mezi volnými a plnými poli: s ní vydrží počítač přes 58 tahů. Osamělé pole je jen nejhorší případ rozbité desky.

Mistrovská pomůcka

Pokládejte kusy tak, aby se dotýkaly co nejvíc hranami okraje desky a jiných kusů. Každá nová hrana mezi volným a plným polem je malá škoda. Dvě volná pole vedle sebe jsou ještě v pořádku (vejde se domino), jedno samotné ne. Než kus položíte, podívejte se na pole kolem něj, ne jen pod něj.

7.3Zdravé hraní

Skládačka na desce nemá konec – hra vždy jednou skončí a začne nová. Proto je snadné hrát déle, než jste chtěli. 3D hra průvodce po dvaceti minutách nepřetržitého hraní připomene přestávku: protáhnout se a podívat se do dálky. Hra nepoužívá peníze ani sázky, rekordy a hvězdičky zůstávají jen ve vašem prohlížeči.

Pozor

„Ještě jedna hra, teď se to povede“ je past náhody: na obtížnosti 4 a 5 může i nejlepší hráč dostat zásobník, který se nevejde. Délka hry počítače se strategií hodnocení desky kolísá od několika tahů po stovky (medián 50, průměr 64 tahů). Jedna špatná hra neznamená, že hrajete hůř.

7.4Procvičení

1
Volné pole v rohu desky má jednoho souseda volného. Je osamělé?
Ne. Osamělé je jen pole bez volného souseda. S volným sousedem se do nich vejde domino.
2
Deska má 40 plných polí. Jak velká je podle tab. 7.1 šance, že se čtverec 3 × 3 nikam nevejde?
Ve skupině 40–47 plných polí je to asi 92 %. Při takovém zaplnění je čtverec 3 × 3 skoro jistě nepoložitelný – pokud nepřijde řada, která místo uvolní.
3
Kus vytvoří jedno osamělé pole, ale doplní řadu. Je to dobrý tah?
Často ano: řada uvolní 8 polí a hodnocení desky dává vymazané řadě váhu 12, osamělému poli −2. Záleží ale i na tom, zda by osamělé pole zůstalo i po vymazání – mizí jen to, co leží v plné řadě.
4
Odhadněte šanci, že se při 24–31 plných polích nevejde aspoň jeden ze tří náhodných kusů.
1 − (1 − 0,017)³ ≈ 5 %. Hrubý odhad, kusy nejsou úplně nezávislé.
5
Proč domino v simulaci nikdy nebylo nepoložitelné?
Domino potřebuje dvě sousední volná pole. Hra končí dřív: dokud je na desce volné místo pro jakýkoli větší kus, je tam i místo pro domino, a desky, kde už nejsou ani dvě sousední volná pole, simulace na obtížnosti 4 nezažila – hra skončila dřív na velkých kusech.
Co si odnést
  • Riziko roste prudce: kolem 32 plných polí se čtverec 3 × 3 nevejde v polovině stavů.
  • Osamělé pole = volné pole bez volného souseda; nevytvářejte je, kus pokládejte těsně k ostatním.
  • Nejvíc pomáhá hladká deska s malou rozbitostí; hrajte s přestávkami a pro radost.
Část IIPokročilí
8

Krychle ze sedmi kusůpokročilí

Polyomina mají prostorové sourozence – polykostky, tvary z krychliček spojených celými stěnami. Nejslavnější prostorový hlavolam z nich je krychle 3 × 3 × 3 ze sedmi kusů: malého rohu ze tří kostek a šesti „nepravidelných“ kusů ze čtyř kostek. Kostek je 3 + 6 · 4 = 27, přesně na krychli. Řešení je 240, když otočené a zrcadlové krychle nepočítáme zvlášť. V prostoru má krychle 24 otočení a se zrcadlením 48 shodností – a tady zrcadlení prohodí dva kusy, které jsou zrcadlovou dvojicí.

🎲

Kostka na hraní má šest stěn a jde položit 24 způsoby: kteroukoli stěnou nahoru a pak ji otočit čtyřikrát kolem svislé osy. 6 · 4 = 24 – to je celá „grupa otočení krychle“, se kterou pracuje laboratoř.

Krychle ze sedmi kusů
Prohlížejte všech 240 řešení. Posuvníkem Kusů skládáte krychli od spodní vrstvy kus po kusu, tlačítky natočení se na krychli díváte z jiné strany. Pod obrázkem jsou všechny tři vrstvy shora.
LABORATOŘ
Model: řešení spočítal řešič průvodce (Algoritmus X, 688 umístění kusů, 34 sloupců: 27 kostek a 7 kusů) – 11 520 řešení v pevně postavené krychli. Každé řešení má 48 obrazů (24 otočení, s každým zrcadlení, které prohodí šrouby A a B); žádné není samo souměrné, takže různých je 11 520 / 48 = 240. Laboratoř ukazuje z každé skupiny jeden zástupce.
Natočení v prostoru
Vyberte kus a spočítejte, kolik různých poloh v prostoru má. Laboratoř projde všech 24 otočení krychle (nebo 48 shodností včetně zrcadlení) a nakreslí každou různou polohu jednou.
LABORATOŘ
Model: otočení krychle jsou permutace os se znaménky s determinantem +1 (24), se zrcadlením všechny (48). Poloha kusu se porovnává po posunutí k počátku, stejně jako u polyomin v kapitole 2.
+Teorie: polykostky, 24 otočení krychle, sedm kusů a jejich polohy, výpočet 240 řešení, paritní argument v prostoru a historie

8.1Polykostky

Tab. 8.1Počty polykostek (spočítáno skriptem průvodce)
KostekJen otočeníI zrcadleníPevné
1111
2113
32215
48786
52923534
61661123 481
Hodnoty souhlasí s posloupnostmi A000162 a A038119 v OEIS. Tetrakostek je 8 při počítání jen otočení, protože dva šrouby (A a B) jsou zrcadlové a otočením je na sebe převést nejde.

8.2Sedm kusů

Z osmi tetrakostek chybí v sadě rovná čtveřice a čtverec 2 × 2 – jediné dvě „pravidelné“ (bez vnitřního rohu); z trikostek chybí rovná trojice. Zbude malý roh V a šest tetrakostek: L, T, Z (ty leží v rovině) a tři prostorové – šroub A, šroub B a trojnožka P (tři ramena do tří směrů z jednoho rohu).

V malý roh
L L
T T
Z Z
A šroub A
B šroub B
P trojnožka
Obr. 8.1Sedm kusů krychle. V, L, T a Z leží v rovině, A, B a P jsou prostorové. A a B jsou zrcadlová dvojice – jako levý a pravý šroub.
Tab. 8.2Polohy kusů v prostoru a v krychli 3 × 3 × 3
KusNatočení (24 otočení)Se zrcadlenímUmístění v krychliŠachovnicová nerovnováha
V malý roh12121441
L24241440
T1212722
Z1212720
A šroub1224 (s B)960
B šroub1224 (s A)960
P trojnožka88642
Umístění celkem 688 = řádky matice přesného pokrytí. Natočení × souměrnosti = 24 (u otočení), podobně jako 8 v rovině.

8.3240 řešení

Řešič postaví krychli pevně a hledá všechna pokrytí 27 kostek sedmi kusy, kusy smí jen otáčet (zrcadlový šroub je jiný kus). Najde 11 520 řešení za 1,3 sekundy (280 791 uzlů). Krychle má 48 shodností: 24 otočení a 24 otočení se zrcadlením. Otočení převede řešení na řešení. Zrcadlení také – jen z A udělá B a z B udělá A, a protože sada obsahuje oba, je výsledek zase platné řešení.

Počítání řešení krychle\[ \#\text{různých} = \frac{\#\text{všech v pevné krychli}}{48} = \frac{11\,520}{48} = 240 \]
AABABBLLL
spodní vrstva
PVVABVLZZ
prostřední vrstva
PPTPTTZZT
horní vrstva
složená krychle
Obr. 8.2Jedno ze 240 řešení po vrstvách zdola nahoru a složené. Písmena odpovídají obr. 8.1.

8.4Parita v prostoru

Obarvěte krychličky jako trojrozměrnou šachovnici: barva = (x + y + z) mod 2. Krychle 3 × 3 × 3 má 14 kostek barvy rohů a 13 druhé, rozdíl 1. L, Z, A a B kryjí 2 : 2, V kryje 2 : 1 (nerovnováha 1), T a P kryjí 3 : 1 (nerovnováha 2). Součet musí dát 1:

Paritní podmínka krychle\[ \pm 1 \pm 2 \pm 2 = +1 \ \Rightarrow\ \varepsilon_V = +1, \quad \varepsilon_T = -\varepsilon_P \]

Malý roh V tedy musí mít dvě kostky barvy rohů a T s P musí mít většinu na opačných barvách. Taková podmínka řešení nenajde, ale při skládání rukou ušetří mnoho slepých pokusů.

Z historie

Hlavolam vymyslel dánský básník, matematik a vynálezce Piet Hein a nazval ho Soma. Tradice vypráví, že nápad dostal v roce 1933 při přednášce Wernera Heisenberga o kvantové mechanice; tato anekdota je doložená jen z pozdějších vyprávění. Dánský patent pochází podle dostupných pramenů z prosince 1933. Počet 240 řešení určili John H. Conway a Richard K. Guy v roce 1961; Conway a Guy spolu s Elwynem Berlekampem popsali řešení v knize Winning Ways for Your Mathematical Plays (1982) pomocí přehledné mapy, které říkali „SOMAP“.

Mistrovská pomůcka

Začněte trojnožkou P a T – jsou nejnáročnější na místo a parita jim předepisuje opačné barvy. Malý roh V si nechte na konec do rohu krychle; má jen 3 kostky a vejde se do mezer, kam se tetrakostky nevejdou.

8.5Procvičení

1
Kolik je otočení krychle a proč?
Kterákoli ze 6 stěn může být nahoře a kolem svislé osy jsou 4 otočení: 6 · 4 = 24.
2
Kus má 24 natočení. Kolik má souměrností (otočení, která ho zobrazí na sebe)?
24 / 24 = 1 – jen identitu. To je kus L.
3
Trojnožka P má jen 8 natočení. Kolik otočení ji zobrazí na sebe?
24 / 8 = 3: identita a otočení o 120° a 240° kolem úhlopříčky krychle, která prochází jejím rohem.
4
Proč by bez šroubu B (se dvěma šrouby A) zrcadlení nepřevádělo řešení na řešení?
Zrcadlení udělá z každého A šroub B, který by v sadě nebyl. Počet různých řešení by se pak dělil jen 24 otočeními a zrcadlový obraz řešení by nebyl řešením stejné sady.
5
Kolik kostek barvy rohů má krychle 3 × 3 × 3?
Pole s x + y + z sudým: 14 (8 rohů, 6 středů stěn) a lichým 13 (12 středů hran a střed krychle).
Co si odnést
  • Polykostky = krychličky spojené stěnami; krychle má 24 otočení a 48 shodností.
  • Sedm kusů (V a šest tetrakostek) má 240 různých řešení, v pevné krychli 11 520 = 240 · 48.
  • Parita: V musí mít většinu na barvě rohů, T a P opačné barvy.
Část IIIMistr a věda
9

Kolik je polyominmistr a věda

Pentomin je 12, hexomin 35, heptomin 108 – a pro velikost n nikdo nezná vzorec. Počty se proto počítají počítačem: buď se tvary vyrábějí růstem a porovnávají, nebo se šikovně vyjmenují bez ukládání (Redelmeierův algoritmus z roku 1981). Pevných polyomin je známo do velikosti 70. Jejich počet roste zhruba jako 4,06n – každá kostka navíc znásobí počet tvarů asi čtyřmi. Že taková konstanta existuje, se ví od roku 1967; její přesnou hodnotu nikdo nezná.

🌱

Rodokmen tvarů: každé polyomino z n kostek má „rodiče“ z n − 1 kostek, kterému ubrala jednu kostku. Většina tvarů má rodičů víc – proto se při růstu musí hlídat, aby se žádný tvar nepočítal dvakrát.

Počítadlo polyomin
Redelmeierův algoritmus spočítá pevná polyomina do zvolené velikosti bez ukládání tvarů. Druhé tlačítko spočítá volná polyomina růstem s kanonickými tvary (jako v kapitole 2). Grafy ukazují počty na logaritmické ose a poměr sousedních počtů, který se blíží růstové konstantě.
LABORATOŘ
Model: Redelmeier: pole jsou očíslovaná tak, aby levé dolní pole tvaru bylo vždy počátek. Algoritmus drží seznam „neprozkoumaných“ sousedních polí; z něj postupně bere pole, přidá ho, rozšíří seznam o jeho nové sousedy a zanoří se. Každé pevné polyomino tak vznikne právě jednou a nic se neporovnává. Volná polyomina: růst o kostku a sloučení podle kanonického tvaru z osmi natočení.
+Teorie: počítání růstem, Redelmeierův algoritmus, tvary s dírou, růstová konstanta a její meze, rekordní výpočty

9.1Počítání růstem

Začněte monominem. Ke každému tvaru velikosti n − 1 přidejte kostku na každé volné sousední pole a výsledek převeďte na kanonický tvar (nejmenší zápis ze všech natočení, kapitola 2). Množina kanonických tvarů jsou právě všechna volná polyomina velikosti n. Metoda je jednoduchá, ale musí mít v paměti všechny tvary – u n = 20 jich jsou miliardy.

1101001 00010 000100 000123456789101112počet kostek nvolných tvarů (logaritmická osa)112512351083691 2854 65517 07363 600
Obr. 9.1Počty volných polyomin pro n = 1 až 12 na logaritmické ose. Sloupce rostou skoro po přímce – počet se s každou kostkou zhruba čtyřnásobí. Oranžově pentomina.
Tab. 9.1Počty polyomin spočítané průvodcem
nVolnáVolná s dírouPevnáPoměr pevných A(n)/A(n−1)
710817603,5185
836962 7253,5855
91 285379 9103,6367
104 65519536 4463,6777
1117 073979135 2683,7115
1263 6004 663505 8613,7397
13––1 903 8903,7637
14––7 204 8743,7843
Volná polyomina do 12 růstem s kanonickými tvary, pevná do 14 Redelmeierovým algoritmem (všech 14 velikostí za 0,23 s). Hodnoty souhlasí s OEIS A000105, A001419 (s dírou) a A001168.

9.2Tvary s dírou

Do šesti kostek žádné polyomino díru nemá. První je heptomino – prstenec 3 × 3 bez rohu, uprostřed s volným polem (obr. 9.2). Pak tvarů s dírou rychle přibývá: u n = 12 je jich 4 663 z 63 600, tedy 7,3 %. Pro skládání jsou tvary s dírou nepohodlné – díru už nic nezaplní – proto v hlavolamech obvykle chybějí.

Obr. 9.2Jediné heptomino s dírou.

9.3Redelmeierův algoritmus

D. Hugh Redelmeier v roce 1981 popsal postup, který každé pevné polyomino vyrobí právě jednou a nemusí nic ukládat ani porovnávat. Pole roviny se uspořádají tak, aby „nejnižší“ pole tvaru bylo vždy počátek (pole pod ním a vlevo v téže řadě jsou zakázaná). Prohledávání drží množinu neprozkoumaných polí; z ní bere pole jedno po druhém, přidává ho do tvaru a do množiny přidá jen ty jeho sousedy, kteří tam ještě nebyli. Paměť roste jen s n, čas s počtem tvarů. Pozdější rekordy (Jensen 2001 a 2003, Barequet a Ben-Shachar 2024) používají jiné, ještě rychlejší metody – přenosové matice a paralelní výpočty.

Příklad Pevná trimina Redelmeierem

Z počátku vedou dvě rozšíření (vpravo a nahoru), takže pevná domina jsou 2. Z nich algoritmus vyrobí 6 pevných trimin: 2 rovná (vodorovné a svislé) a 4 rohy (čtyři otočení malého rohu). Každé vznikne jednou, protože pole se z množiny možností po vyzkoušení vyřadí a v téže větvi se do ní už nevrátí.

9.4Růstová konstanta

David Klarner v roce 1967 dokázal, že existuje limita λ = lim A(n)1/n pro pevná polyomina. Odhad z nejdelších známých počtů (Jensen 2003) je λ ≈ 4,0625696 ± 0,0000005, předpokládaný tvar růstu

Růst počtu pevných polyomin\[ A(n) \sim C \cdot \frac{\lambda^n}{n}, \qquad 4{,}00253 \le \lambda \le 4{,}5252, \qquad \lambda \approx 4{,}0626 \]

Dolní mez 4,00253 dokázali Barequet, Rote a Shalah (vyšlo 2016), horní mez 4,5252 Barequet a Shalah (2022); starší horní mez 4,6496 je od Klarnera a Rivesta (1973). Poměr A(n)/A(n − 1) v tab. 9.1 roste k λ pomalu – u n = 14 je teprve 3,78. Faktor 1/n ho snižuje: poměr je zhruba λ · (n − 1)/n, u n = 14 tedy asi 3,77.

Z historie

Iwan Jensen spočítal pevná polyomina v roce 2001 do velikosti 46 a v roce 2003 do 56 metodou přenosových matic na paralelním počítači. V roce 2024 Gill Barequet a Gil Ben-Shachar posunuli hranici na n = 70. Volná polyomina jsou podle OEIS známa o něco méně daleko. Všechny tyto výpočty se dají ověřit pro malá n – tab. 9.1 spočítal prohlížeč za zlomek sekundy.

Pozor

Volná polyomina nejsou přesně pevná / 8. Souměrné tvary mají méně než 8 natočení, takže volných je o něco víc než osmina pevných: u n = 10 je 36 446 / 8 ≈ 4 556, kdežto volných je 4 655. Pro velká n se poměr blíží 8, protože souměrných tvarů je zanedbatelně málo.

9.5Procvičení

1
Odhadněte z poměru 3,78 počet pevných 15-omin.
7 204 874 · 3,8 ≈ 27,4 milionu (poměr ještě roste; laboratoř s Redelmeierovým algoritmem jich napočítá 27 394 666, stejně jako OEIS A001168).
2
Kolik procent volných 10-omin má díru?
195 / 4 655 ≈ 4,2 %.
3
Proč Redelmeierův algoritmus nepotřebuje porovnávat tvary?
Každé pevné polyomino vznikne v prohledávacím stromu jen jednou: pole se do tvaru přidávají v pevném pořadí a pole, které jednou z množiny možností vypadlo, už se v té větvi nevrátí. Duplicitu tak vyloučí sama struktura prohledávání.
4
Pokud by A(n) rostlo přesně jako λn, jaký by byl poměr A(n)/A(n−1)?
Přesně λ pro každé n. Skutečný poměr je menší a k λ roste, protože ve vzorci je ještě faktor 1/n: poměr ≈ λ · (n − 1)/n.
5
Proč existence konstanty λ ještě neříká její hodnotu?
Klarnerův důkaz ukazuje, že posloupnost A(n)1/n konverguje (opírá se o to, že spojením dvou polyomin vznikne větší), ale neříká k čemu. Hodnota se jen odhaduje z dlouhých počtů a ohraničuje mezemi – dnes mezi 4,00253 a 4,5252.
Co si odnést
  • Vzorec pro počet polyomin neznáme; počítá se růstem nebo Redelmeierovým algoritmem bez porovnávání.
  • Počet roste zhruba jako 4,06ⁿ / n; konstanta existuje (Klarner 1967), známe jen meze 4,00253 až 4,5252 a odhad.
  • První tvar s dírou je heptomino; volných je o něco víc než osmina pevných.
Část IIIMistr a věda
10

Algoritmus X a tanec odkazůmistr a věda

Jak počítač skládá pentomina? Úlohu přepíše do tabulky nul a jedniček. Každý sloupec je něco, co musí být pokryté právě jednou – pole oblasti nebo kus. Každý řádek je jedno umístění jednoho kusu a má jedničky ve sloupcích polí, která kryje, a ve sloupci svého kusu. Řešení = výběr řádků, ve kterém má každý sloupec právě jednu jedničku: přesné pokrytí. Donald Knuth pro něj v roce 2000 popsal Algoritmus X – prohledávání s návratem, které v každém kroku vybere sloupec s nejméně možnostmi – a datovou strukturu tanec odkazů, ve které se řádky a sloupce vyjímají a vracejí jen přepojením několika ukazatelů.

💃

Tanečník opustí řadu, ale sousedé si pamatují, kde stál. Když se vrátí, jen se mezi ně zase vmáčkne. Přesně tak se v tanci odkazů vyjímá a vrací prvek ze seznamu – bez kopírování, za konstantní čas.

Algoritmus X krok za krokem
Vyberte malou úlohu a pravidlo výběru sloupce. Krok provede jednu událost algoritmu: výběr sloupce, položení nebo odebrání kusu, návrat. Deska ukazuje aktuálně položené kusy, oranžově pole vybraného sloupce, záznam vpravo dole celou historii.
LABORATOŘ
Model: matice přesného pokrytí jako v kapitole 5 (sloupce = pole po řádcích a pak kusy). Kroky odpovídají Knuthovým krokům algoritmu: vyber sloupec c, zakryj ho, zkus jeho řádky jeden po druhém, po každém zakryj sloupce řádku a zanoř se, po návratu je odkryj. Uzel = položení řádku. „Vždy první sloupec“ bere první nepokryté pole v pořadí čtení, jak by postupoval člověk bez rozmyslu.
+Teorie: přesné pokrytí, Algoritmus X, tanec odkazů, strom prohledávání a výběr sloupce, další úlohy jako přesné pokrytí

10.1Přesné pokrytí

Je dána množina prvků U (sloupce) a soubor jejích podmnožin (řádky). Hledáme podsoubor řádků, které jsou po dvou disjunktní a jejich sjednocení je celé U. U pentomin je U = 60 polí + 12 kusů = 72 sloupců a řádků 2 056 (obdélník 6 × 10). Sloupec kusu zajistí, že se každý kus použije právě jednou.exact cover

Přesné pokrytí\[ \text{najdi } S \subseteq \mathcal{R}: \quad \forall\, u \in U: \ \big|\{\, r \in S : u \in r \,\}\big| = 1 \]
abcdef1.11····2.·11···3.···11·4.····115.1··1··6.·1··1·7.··1··1
Obr. 10.1Matice přesného pokrytí obdélníku 2 × 3 (pole a–f) dominy: 7 umístění domina, 6 sloupců. Zvýrazněné řádky tvoří jedno ze 3 řešení – v každém sloupci mají právě jednu jedničku. Domina jsou všechna stejná, proto tu sloupce kusů nejsou.

10.2Algoritmus X

  1. Nezbývá-li žádný sloupec, je vybraná množina řádků řešení.
  2. Vyber sloupec c (deterministicky – nejlépe ten s nejméně jedničkami). Má-li 0 jedniček, tato větev řešení nemá.
  3. Pro každý řádek r s jedničkou ve sloupci c: přidej r k řešení; odstraň všechny sloupce, ve kterých má r jedničku, a všechny řádky, které mají jedničku v některém z nich (kolidují s r); zanoř se; pak všechno vrať a zkus další řádek.

Algoritmus je „nedeterministický“ jen v tom, že zkouší všechny řádky vybraného sloupce. Výběr sloupce je deterministický – a na něm závisí velikost prohledávání. Knuth navrhl brát sloupec s nejmenším počtem jedniček (anglicky minimum remaining values); v pentominech je to lidská technika Úzké místo z kapitoly 5.

10.3Tanec odkazů

Matice je řídká, proto se ukládají jen jedničky. Každá jednička je uzel ve dvou kruhových obousměrných seznamech: v řádku (doleva, doprava) a ve sloupci (nahoru, dolů). Vyjmout uzel x ze seznamu a vrátit ho zpět jde dvěma přiřazeními:

Vyjmutí a návrat (Knuth: „dancing links“)\[ \text{vyjmi: } L[R[x]] \leftarrow L[x], \ \ R[L[x]] \leftarrow R[x]; \qquad \text{vrať: } L[R[x]] \leftarrow x, \ \ R[L[x]] \leftarrow x \]

Trik je v tom, že vyjmutý uzel si své sousedy L[x] a R[x] pamatuje. Když se prvky vracejí v opačném pořadí, než se vyjímaly – a prohledávání s návratem to tak dělá samo – vrátí se struktura přesně do původního stavu. Žádné kopírování matice, žádné hledání. K tomu se ke každému sloupci drží počet jeho jedniček, takže výběr sloupce s nejméně možnostmi stojí jen projití hlaviček sloupců.dancing links, DLX

10.4Strom prohledávání

∅LTYřešeníLLTTLYřešeníYLřešeníYTLřešeníY
Obr. 10.2Celý strom prohledávání úlohy L, T, Y do 5 × 3 s výběrem sloupce s nejméně možnostmi: 15 uzlů (položení kusu), 8 listů, hloubka 3. Podbarvené listy s popiskem jsou řešení – 4 kopie jediného řešení (obdélník má 4 souměrnosti), listy jen s oranžovým rámečkem jsou slepé uličky.
Tab. 10.1Počet uzlů podle pravidla výběru sloupce (řešič průvodce)
ÚlohaRůzných řešeníNejméně možnostíVždy první sloupec
L, T, Y do 5 × 3 (všechna řešení)11515
N, T, V, Y do 5 × 4 (všechna)156100
F, L, P, U, X do 5 × 5 (všechna)149410
L, P, T, V, W, X do 6 × 5 (všechna)1661 412
všech 12 do 6 × 10 (první řešení)2 339862301 017
všech 12 do 3 × 20 (první řešení)2238868 699 875
Malé úlohy laboratoře vybral skript ze všech trojic až šestic pentomin: do 5 × 3 jde poskládat 7 trojic z 220, do 5 × 4 26 čtveřic z 495, do 5 × 5 45 pětic z 792 a do 6 × 5 172 šestic z 924; u každé zvolené úlohy je řešení jediné.
Příklad První krok úlohy 5 × 3

Matice má 44 řádků: L a Y se do obdélníku 5 × 3 vejdou 16 způsoby, T 12. Roh ř1s1 ale pokrývá jen 7 umístění – nejméně ze všech sloupců – a algoritmus začne tam. Položí L přes ř1s1 až ř1s4 a ř2s1. Pak má pole ř1s5 jedinou možnost (T) a po ní pole ř2s2 jedinou možnost (Y): první řešení po třech položeních. Celý strom má 15 uzlů. Krokujte v laboratoři a sledujte, který sloupec algoritmus vybere a kolik má možností.

10.5Kde všude je přesné pokrytí

  • Sudoku: 324 sloupců (každé pole má číslici, každý řádek, sloupec a blok má každou číslici) a 729 řádků (číslice d v poli p). Stejný řešič vyřeší každé sudoku.
  • N dam: řádky a sloupce šachovnice povinně, úhlopříčky jako volitelné sloupce (nejvýš jednou).
  • Krychle ze sedmi kusů (kapitola 8): 27 kostek a 7 kusů, 688 řádků.
  • Úlohy ve 3D hře: trenér v režimu Pentomina hledá úzké místo a ověřuje dokončení stejným druhem řešiče.
Z historie

Knuth popsal Algoritmus X a tanec odkazů v článku Dancing Links (sborník Millennial Perspectives in Computer Science, 2000; předtisk arXiv cs/0011047). Samotnou techniku vyjímání a vracení prvků obousměrného seznamu připisuje Hiroši Hitotsumatsuovi a Kóhei Noshitovi, kteří ji v roce 1979 použili pro úlohu N dam. Pentomina jsou v Knuthově článku hlavním příkladem.

Pozor

Výběr sloupce s nejméně možnostmi nesnižuje počet řešení, jen počet slepých uliček. U úlohy L, T, Y do 5 × 3 obě pravidla prohledají 15 uzlů – na malých úlohách rozdíl být nemusí. Na velkých rozhoduje o sekundách proti hodinám.

10.6Procvičení

1
Kolik sloupců má matice pro krychli ze sedmi kusů?
27 kostek + 7 kusů = 34.
2
Sloupec má 0 jedniček. Co algoritmus udělá?
Pokud ho vybere (s pravidlem nejmenšího sloupce vždy), větev okamžitě vzdá a vrátí se – pole nebo kus už nejde pokrýt.
3
Proč stačí vracet prvky v opačném pořadí, než se vyjímaly?
Vyjmutý prvek si pamatuje své sousedy z okamžiku vyjmutí. Když se vrací v opačném pořadí, jsou ti sousedé zase na svém místě, takže dvě přiřazení obnoví seznam přesně.
4
Kolik řádků má matice sudoku a proč?
9 číslic · 81 polí = 729 – každý řádek je volba „číslice d do pole p“.
5
Proč obdélník 2 × 3 s domino má 3 řešení, i když řádků je 7?
Řešení potřebuje 3 disjunktní řádky, které pokryjí všech 6 polí. Většina trojic řádků se překrývá nebo nechá díru. Projdou jen 3: tři svislá domina; svislé vlevo a dvě vodorovná vpravo; dvě vodorovná vlevo a svislé vpravo. Tři vodorovná nejdou – v obdélníku 2 × 3 by třetí nemělo kam.
Co si odnést
  • Přesné pokrytí: sloupce = co musí být pokryté právě jednou, řádky = možnosti; pentomina, krychle i sudoku.
  • Algoritmus X: vyber sloupec s nejméně možnostmi, zkoušej jeho řádky, zanoř se a vrať.
  • Tanec odkazů vyjímá a vrací prvky dvěma přiřazeními – návrat je zadarmo.
Část IIIMistr a věda
11

Složitost: proč jsou blokové hlavolamy těžkémistr a věda

Pentomina do 6 × 10 vyřeší počítač za pár sekund. S rostoucí oblastí a počtem kusů ale každý známý algoritmus v nejhorším případě zpomalí exponenciálně – a matematici dokázali, že to nejspíš jinak nejde. Skládání polyomin do oblasti je NP-úplné: kdyby existoval rychlý algoritmus pro něj, existoval by pro tisíce dalších úloh od rozvrhů po šifry. Totéž platí pro padající kostky se známou řadou kusů: Demaine, Hohenberger a Liben-Nowell (2003) dokázali NP-úplnost převodem z úlohy 3-dělení – rozdělit čísla do trojic se stejným součtem. Tu si zahrajete v minihře.

⚖️

Dvanáct závaží rozdělit na čtyři hromádky po třech tak, aby všechny vážily stejně. S dvanácti závažími to zvládnete. Se stovkou už ne – a počítač, který zkouší naslepo, také ne. Rychlý postup, který by fungoval na každé zadání, nikdo nezná.

3-dělení
Rozdělte čísla do trojic tak, aby každá měla předepsaný součet. Klepněte postupně na tři čísla – vytvoří trojici. Zpět zruší poslední klepnutí. Vyhodnotit zkontroluje všechny trojice a ukáže, kolik uzlů by potřebovaly dva řešiče. Tlačítkem Změřit řešiče porovnáte jejich rychlost na náhodných zadáních.
MINIHRA
Jak to funguje: zadání se vyrábí jako náhodné trojice čísel mezi čtvrtinou a polovinou součtu, které se pak zamíchají – řešení tedy vždy existuje. Naivní řešič přiřazuje čísla od největšího do skupin jedno po druhém, řešič po skupinách bere největší zbylé číslo a k němu hledá dvojici, která součet doplní. Oba prohledávají s návratem; měření běží na zadáních se součtem 1 000.
+Teorie: P a NP, převod a NP-úplnost, 3-dělení, padající kostky, skládání polyomin a co z toho plyne pro hráče

11.1P, NP a převody

Úloha je ve třídě P, když ji jde rozhodnout algoritmem, jehož čas roste nejvýš polynomiálně s velikostí zadání. Je ve třídě NP, když jde navržené řešení rychle (polynomiálně) ověřit. Skládání polyomin je v NP: kdo dostane rozložení kusů, zkontroluje ho jedním průchodem. Převod úlohy A na úlohu B je rychlý postup, který z každého zadání A vyrobí zadání B se stejnou odpovědí. Úloha je NP-úplná, když je v NP a dá se na ni převést každá úloha z NP. Richard Karp v roce 1972 ukázal NP-úplnost 21 známých úloh; dnes jich jsou tisíce. Zda P = NP, je otevřená otázka – jedna ze sedmi „problémů tisíciletí“.NP-completeness, reduction

NP-úplnost\[ B \in \mathrm{NP} \ \wedge\ \forall A \in \mathrm{NP}: \ A \le_p B \quad\Longrightarrow\quad B \text{ je NP-úplná}; \qquad B \in \mathrm{P} \Rightarrow \mathrm{P} = \mathrm{NP} \]

11.23-dělení

Dáno 3m kladných celých čísel se součtem m · T, každé ostře mezi T/4 a T/2. Lze je rozdělit do m skupin se součtem T? Podmínka na velikost čísel zaručí, že každá skupina má přesně tři čísla (dvě jsou málo, čtyři moc). Michael Garey a David Johnson v roce 1975 dokázali, že úloha je NP-úplná v silném smyslu: zůstává těžká, i když jsou čísla malá (zapsaná čárkami, ne ciframi). To je pro převody na hlavolamy zásadní – číslo a se dá „postavit“ z a kostek a deska zůstane polynomiálně velká.

3-dělení\[ a_1, \dots, a_{3m} \in \mathbb{N}, \quad \tfrac{T}{4} < a_i < \tfrac{T}{2}, \quad \sum_i a_i = mT: \qquad \exists\, \text{rozklad na } m \text{ trojic se součtem } T\,? \]
součet 308814trojice 112108trojice 210128trojice 3101010trojice 4
Obr. 11.1Zadání 3-dělení se 12 čísly (8, 12, 10, 10, 8, 8, 10, 10, 12, 14, 10, 8) a součtem trojice T = 30 a jeho řešení: 8 + 8 + 14, 12 + 10 + 8, 10 + 12 + 8 a 10 + 10 + 10. V převodu na padající kostky jsou trojice „šachty“ na desce a čísla skupiny kusů, které je musí přesně zaplnit.

11.3Těžké v nejhorším případě, ne vždy

110010 0001 mil.100 mil.2468101214počet trojic m (čísel je 3m)uzlů prohledávání (medián z 10 zadání, log. osa)číslo po číslepo skupináchm = 7: polovina zadání nad 20 mil. uzlů
Obr. 11.2Medián počtu uzlů dvou řešičů na náhodných řešitelných zadáních se součtem T = 1 000 (10 zadání pro každé m). Naivní řešič roste s každou trojicí čím dál rychleji – mezi 4 a 6 trojicemi asi dvacetinásobně; při m = 7 nedoběhla polovina zadání do 20 milionů uzlů. Řešič po skupinách vystačí s desítkami uzlů i při 14 trojicích.

Obrázek ukazuje dvě věci. Za prvé, způsob prohledávání rozhoduje o řádech – stejně jako výběr sloupce v kapitole 10. Za druhé, náhodná zadání bývají snadná: NP-úplnost mluví o nejhorším případě. Těžká zadání se dají sestrojit (třeba z převodů jiných úloh) a na ně zatím žádný známý algoritmus nemá polynomiální čas.

11.4Padající kostky

Erik Demaine, Susan Hohenberger a David Liben-Nowell (2003) zkoumali „offline“ verzi padajících kostek: celá řada kusů je známá předem a deska může být zčásti zaplněná. Dokázali, že je NP-úplné rozhodnout, zda jde vymazat aspoň daný počet řad, dosáhnout daného počtu vymazání čtyř řad naráz, položit všechny kusy bez prohry nebo udržet maximální výšku pod mezí. Převod staví z 3-dělení desku se šachtami, do kterých se kusy pro každé číslo vejdou jen jedním způsobem; některé cíle jsou navíc těžké i na přibližné řešení. Rozšířená verze vyšla v roce 2004 (Breukelaar a kol.). Asif a kolegové (2020) ukázali, že úloha zůstává NP-těžká i na desce s konstantním počtem řádků nebo sloupců.

11.5Skládání polyomin

Úloha „dá se oblast vyplnit danými kusy?“ je NP-úplná už pro jednoduché kusy. Cristopher Moore a John Michael Robson (2001) dokázali NP-úplnost pokrytí oblasti malými rohy (trimino L) – jediným typem kusu. Erik a Martin Demaineovi (2007) ukázali, že skládačky typu puzzle, skládání polyomin do čtverce a hlavolamy se shodou hran jsou navzájem převoditelné a všechny NP-úplné. Pro hráče z toho plyne, že žádný univerzální trik „vždy najdi řešení rychle“ neexistuje (pokud P ≠ NP) – úzké místo, parita a dobré pořadí jsou heuristiky, ne zázračné algoritmy.

Příklad Proč 6 × 10 není „těžké“

NP-úplnost se týká rostoucích zadání. Obdélník 6 × 10 je jedno pevné zadání – řešič ho celé projde za 4 056 445 uzlů. Těžkost znamená, že s každým zvětšením (oblast 6 × 100, sto kusů) může čas některých zadání vyletět exponenciálně a žádný známý algoritmus to nezastaví.

Pozor

Výsledky o složitosti padajících kostek se týkají známé řady kusů a desky libovolné velikosti. Skládačka na desce 8 × 8 s mizením řádků i sloupců je jiná hra: deska je malá a pevná, kusy přicházejí náhodně. Rozbor jednoho zásobníku je pro počítač snadný (kapitola 12). Přímý výsledek o složitosti skládaček s mizením řádků i sloupců na rostoucí desce jsme v literatuře neověřili.

Z historie

Článek Demaineho, Hohenberger a Liben-Nowellové „Tetris is Hard, Even to Approximate“ (konference COCOON 2003) nese v názvu jméno hry, ze které vychází; jde o věcný historický název článku, průvodce jinak obchodní názvy her nepoužívá. Rozšířená časopisecká verze vyšla v roce 2004 v International Journal of Computational Geometry and Applications.

11.6Procvičení

1
Proč podmínka T/4 < ai < T/2 vynutí trojice?
Dvě čísla menší než T/2 dají méně než T; čtyři čísla větší než T/4 dají víc než T. Skupina se součtem T má tedy právě tři čísla.
2
Čísla 9, 11, 10, 12, 8, 10 a T = 30. Jde to?
Součet je 60 = 2 · 30. Trojice: 12 + 8 + 10 = 30 a 9 + 11 + 10 = 30 – jde.
3
Co znamená „silně NP-úplná“ a proč je to pro převod na hlavolam důležité?
Úloha zůstává těžká, i když jsou čísla malá (velikost čísel polynomiální v počtu čísel). Převod pak může každé číslo vyjádřit kusem nebo šachtou o tolika polích – deska nebude exponenciálně velká.
4
Je ověření navrženého rozložení pentomin rychlé?
Ano – stačí projít kusy a zkontrolovat, že každé pole je pokryté právě jednou. Proto je úloha v NP. Těžké je řešení najít, ne ověřit.
5
Naivní řešič 3-dělení potřeboval při 6 trojicích medián 498 045 uzlů, řešič po skupinách 6. Proč takový rozdíl?
Naivní řešič zkouší každé číslo v každé skupině, i když skupina ještě nemůže být hotová – chyba se ukáže pozdě. Řešič po skupinách hned sestaví celou trojici s přesným součtem a špatné kombinace vůbec nevytvoří. Na náhodných zadáních je trojic se správným součtem málo, takže skoro nevrací.
Co si odnést
  • Skládání polyomin i padající kostky se známou řadou kusů jsou NP-úplné; rychlý algoritmus pro všechna zadání nejspíš neexistuje.
  • 3-dělení: čísla mezi T/4 a T/2 do trojic se součtem T; silně NP-úplné, proto vhodné pro převody na hlavolamy.
  • NP-úplnost je o nejhorším případě – náhodná a malá zadání bývají snadná.
Část IIIMistr a věda
12

Počítač hraje a vyrábí úlohymistr a věda

Jak naučit počítač hrát skládačku na desce? Stačí mu dát hodnoticí funkci – číslo, které řekne, jak dobrá je deska po tahu – a nechat ho vyzkoušet všechna místa a vybrat nejlepší. Hodnocení z této kapitoly sčítá vymazané řady, trestá osamělá pole a rozbitost desky a odměňuje místo pro čtverec 3 × 3 a pětici. Na obtížnosti 4 s ním počítač vydrží v průměru 64 tahů, kdežto hladový hráč, který jen sbírá body, 18 a náhodný 12. Stejné nástroje vyrábějí hru: férový zásobník, který jde vždy položit, a pentominové úlohy s jediným řešením.

🤖

Šachový program také „nevidí“ celou partii. Ohodnotí pozici – materiál, bezpečí krále, aktivitu figur – a vybere tah, po kterém je číslo nejlepší. Skládačka na desce je jednodušší: soupeř je jen náhoda zásobníku.

Počítač hraje s vašimi vahami
Nastavte váhy hodnoticí funkce a nechte počítač odehrát 20 her. Porovnejte průměrný počet tahů s výchozími vahami. Deska dole ukazuje konec poslední hry.
LABORATOŘ
Model: v každém tahu počítač zkusí všechny kusy zásobníku na všech místech a vybere tah s nejvyšším hodnocením H = wk · řady − wi · osamělá + ws · [3 × 3] + wl · [pětice] − wr · rozbitost (shody rozhoduje los). Neplánuje pořadí celého zásobníku – proto je to rychlé. Hra má limit 400 zásobníků. Obtížnost 3 má férový zásobník, 4 a 5 náhodný.
Výroba pentominové úlohy
Generátor složí náhodné řešení obdélníku, odebere zvolený počet kusů a řešičem spočítá, kolika způsoby jde úlohu dokončit. Úloha s jediným dokončením je „poctivá“ – hráč nemůže skončit jiným správným řešením, než jaké zná trenér.
LABORATOŘ
Model: náhodné řešení = první řešení řešiče s náhodně zamíchanými řádky matice. Dokončení se počítají Algoritmem X na zbylé oblasti s odebranými kusy (všechna natočení, každý kus jednou). Hra ve 3D má obtížnosti se 6, 4 a 2 ležícími kusy a pak prázdné desky.
+Teorie: hodnoticí funkce a její části, porovnání strategií, férový zásobník, denní výzva a tvorba úloh s jediným řešením

12.1Hodnoticí funkce

Výchozí hodnocení tahu (průvodce, hero a minihry)\[ H = 12\,k \;-\; 2\cdot\text{osamělá} \;+\; 4\cdot[\,3{\times}3 \text{ se vejde}\,] \;+\; 2\cdot[\,\text{pětice se vejde}\,] \;-\; 1\cdot\text{rozbitost} \]

Váhy jsme hledali simulací: výchozí volba vydrží na obtížnosti 4 v průměru 62,4 ± 4,4 tahu (400 her). Každou část jsme pak vypnuli a sledovali, kolik tahů počítač ztratí – takzvaná ablace (obr. 12.1). Největší díl práce dělá rozbitost: bez ní (jen řady, osamělá pole a místo pro velké kusy) vydrží počítač kolem 19 tahů, s ní samotnou přes 58. Osamělá pole a místo pro velké kusy pak přidají každé pár tahů navíc.

010203040506070jen vymazání řad15,3+ bez osamělých polí15,8+ místo pro velké kusy18,2+ obojí19,4jen rozbitost (bez řad)58,3vše kromě místa pro velké kusy59,0vše kromě osamělých polí60,8výchozí hodnocení (vše)62,4průměrný počet tahů do konce hry (obtížnost 4, 400 her, úsečka = 95% interval)
Obr. 12.1Kolik tahů vydrží počítač podle toho, které části hodnocení používá (obtížnost 4, 400 her pro každý řádek). „Jen vymazání řad“ je hladový hráč, který se o desku nestará. Samotná rozbitost dá skoro čtyřnásobek tahů; teprve všechno dohromady je nejlepší.

12.2Tři strategie

Tab. 12.1Tahy a body tří strategií (200 her pro každou obtížnost, limit 900 tahů)
ObtížnostNáhodně: medián tahů / bodůHladově: medián tahů / bodůHodnocení desky: medián tahů / bodů
1 Pohodová29 / 561308 / 10 596900+ / 35 548
2 Lehká20 / 30995 / 3 966900+ / 45 009
3 Střední13 / 13244 / 1 800164 / 10 370
4 Těžká11 / 11316 / 39050 / 2 765
5 Mistrovská10 / 4614 / 38529 / 1 757
Náhodně = náhodný kus na náhodné místo; hladově = tah, který vymaže nejvíc řad (při shodě větší kus); hodnocení desky = výchozí H. „900+“: všech 200 her dosáhlo limitu, hra by pokračovala. Na obtížnosti 3 se do limitu dostaly 2 hry z 200, hladová strategie na obtížnosti 1 30 her. Průměry tahů na obtížnosti 4: 11,5, 17,8 a 64,0.

Na obtížnostech 1 a 2 (malé kusy, otáčení, férový zásobník) počítač s hodnocením desky prakticky neprohrává. Od obtížnosti 3 rozhodují velké kusy bez otáčení a na obtížnosti 4 a 5 náhodný zásobník, který jednou přinese tři kusy bez místa.

12.3Férový zásobník

Hra na obtížnostech 1 až 3 skládá zásobník postupně: vylosuje první kus a položí ho na kopii desky na nejlépe hodnocené místo, pak losuje druhý kus, který se na takto upravenou desku musí vejít, a stejně třetí. Kus, který se nevejde, se losuje znovu. Hráči pak hra nabídne všechny tři v náhodném pořadí. Zásobník tak jde vždy položit celý – aspoň jedním pořadím a na místa, která našel počítač.

Tab. 12.2Jak často by náhodný zásobník obtížnosti 4 nešel položit celý (v žádném pořadí ani na žádná místa)
Plných polí0–1516–2324–3132–3940–47
Nepoložitelných zásobníků0,0 %0,7 %2,8 %12,1 %18,1 %
Desky z partií počítače, pro každou byl vylosován náhodný zásobník a úplným prohledáním šesti pořadí a všech míst zjištěno, zda jde položit. Férový zásobník tyto případy vylučuje.
Příklad Denní výzva

Denní výzva ve 3D hře je 20 zásobníků obtížnosti 3. Řada kusů se vylosuje z data, takže v daný den je pro všechny stejná. Počítač ji odehraje předem stejným druhem prohledávání jako trenér a jeho skóre je laťka: ★ za 30 % jeho bodů, ★★ za 60 %, ★★★ za vyrovnání.

12.4Tvorba pentominových úloh

Úloha = rozpracovaný obdélník, na kterém leží několik kusů, a zbylé kusy k doplnění. Generátor vezme náhodné řešení, odebere k kusů a spočítá dokončení. Čím víc kusů odebere, tím častěji existuje víc dokončení a tím je úloha těžší pro člověka i pro řešič.

Tab. 12.3Podíl úloh s jediným dokončením (obdélník 6 × 10, 60 úloh pro každé k, u k = 7 a 8 40 úloh)
Odebráno kusů k2345678
jediné dokončení98 %100 %93 %93 %73 %88 %63 %
průměr dokončení1,01,01,11,11,31,21,9
průměr uzlů řešiče2358143292
U 5 × 12 a 4 × 15 vychází podobně: s 8 odebranými kusy má jediné dokončení 53 %, resp. 55 % úloh. Kolísání mezi sousedními k (73 % a 88 %) je náhoda malého vzorku.
Mistrovská pomůcka

Úlohu s jedním řešením řešte jako logickou hru: hledejte vynucené tahy (pole s jedinou možností, kapitola 5) a kusy, které se vejdou jen na jedno místo. Úloha s více dokončeními dovolí i „jiné“ správné řešení – trenér ve 3D hře přijme každé, které řešič potvrdí.

Pozor

Simulace měří počítačového hráče, ne člověka. Člověk vidí desku jinak – rychle pozná vzor, ale nepočítá rozbitost na jednotky. Čísla v tabulkách jsou proto srovnání strategií, ne předpověď vašeho skóre.

12.5Procvičení

1
Tah vymaže 1 řadu, vytvoří 1 osamělé pole, zachová místo pro 3 × 3 i pětici a rozbitost po něm je 20. Jaké má hodnocení H?
12 · 1 − 2 · 1 + 4 + 2 − 20 = −4. Hodnocení je záporné kvůli rozbitosti – důležité je jen srovnání s ostatními tahy.
2
Proč hladová strategie vydrží na obtížnosti 1 tak dlouho (medián 308 tahů), ale na obtížnosti 4 jen 16?
Na obtížnosti 1 jsou kusy malé, jdou otáčet a zásobník je férový – skoro vždy se něco vejde. Na obtížnosti 4 přicházejí velké kusy bez otáčení a náhodný zásobník; kdo nehlídá desku, brzy nemá místo pro čtverec 3 × 3.
3
Proč férový zásobník neprozradí hráči, kam kusy patří?
Hra kusy po výběru zamíchá a místa, která počítač při výběru použil, neukazuje. Hráč ví jen, že nějaké řešení existuje.
4
Generátor odebral 8 kusů a řešič našel 3 dokončení. Co s takovou úlohou?
Buď ji přijmout jako úlohu s více řešeními (trenér pak uzná každé správné), nebo vrátit jeden kus na desku a počítat znovu – s méně odebranými kusy je jediné dokončení mnohem častější (tab. 12.3).
5
Výchozí váhy vydrží 62,4 ± 4,4 tahu. Jak poznáte, že nové váhy jsou opravdu lepší?
Rozdíl musí být větší než nejistota obou odhadů. S 20 hrami je nejistota velká (desítky procent); spolehlivé srovnání potřebuje stovky her se stejnými zásobníky. Proto laboratoř ukazuje i interval a výchozí hodnotu.
Co si odnést
  • Hodnoticí funkce: řady, osamělá pole, místo pro velké kusy, rozbitost; nejvíc pomáhá hladká deska.
  • Na obtížnosti 4 vydrží hodnocení desky 64 tahů, hladová strategie 18, náhodná 12 (průměry).
  • Férový zásobník = kusy vybírané postupně na kopii desky; úlohy z pentomin se ověřují počtem dokončení.
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
Dokončit řadupoložit kus tak, aby doplnil řádek nebo sloupec a uvolnil místo3
Místo pro velké kusynechat volný blok 3 × 3 a úsek pro pětici3
Dvojité vymazánívymazat dvě a víc řad jedním kusem (bonus × k²)4
Pořadí kusůzvolit pořadí tří kusů tak, aby se vešly všechny4
Úzké místou pentomin začít polem, kam se vejde nejméně kusů5
Bez osamělých polínevytvářet volná pole bez volného souseda7

Vzorce na jednom místě

Body za tah (kap. 3, 4)\[ \text{body} = n + 10 \cdot N \cdot k^2 \cdot \Big(1 + \tfrac{1}{2}(s-1)\Big) \]
Polohy kusu na prázdné desce (kap. 3)\[ \#\text{poloh} = \sum_{\text{natočení}} (N - w + 1)(N - h + 1) \]
Natočení a souměrnosti (kap. 2, 8)\[ \#\text{natočení} \cdot \#\text{souměrností} = |G|, \qquad |G| = 8 \ (\text{čtverec}), \ 24 \ (\text{otočení krychle}), \ 48 \ (\text{shodnosti krychle}) \]
Různá řešení skládání (kap. 5, 8)\[ \#\text{různých} = \frac{\#\text{všech}}{|G|} \quad \text{(když žádné řešení není samo souměrné)} \]
Paritní podmínka (kap. 6)\[ \sum_i \varepsilon_i\, d_i = D_{\text{oblast}}, \qquad \varepsilon_i = \pm 1 \]
Hodnocení desky (kap. 12)\[ H = 12\,k - 2\cdot\text{osamělá} + 4\cdot[3{\times}3] + 2\cdot[\text{pětice}] - \text{rozbitost} \]
Růst počtu polyomin (kap. 9)\[ A(n) \sim C\,\frac{\lambda^n}{n}, \qquad 4{,}00253 \le \lambda \le 4{,}5252, \qquad \lambda \approx 4{,}0626 \]
Tanec odkazů (kap. 10)\[ L[R[x]] \leftarrow L[x],\ R[L[x]] \leftarrow R[x] \quad\longleftrightarrow\quad L[R[x]] \leftarrow x,\ R[L[x]] \leftarrow x \]
3-dělení (kap. 11)\[ \tfrac{T}{4} < a_i < \tfrac{T}{2}, \quad \sum_{i=1}^{3m} a_i = mT \]

Čísla z kapitol

Tab. B.2Přehled spočítaných údajů
ÚdajHodnotaKde
volná polyomina n = 1…81, 1, 2, 5, 12, 35, 108, 369kap. 2, 9
pevná tetromina / pentomina / hexomina19 / 63 / 216kap. 2
řešení 6 × 10 / 5 × 12 / 4 × 15 / 3 × 202 339 / 1 010 / 368 / 2kap. 5
řešení šachovnice 8 × 8 bez středu 2 × 265kap. 5
uzly k prvnímu řešení 3 × 20: úzké místo / první pole238 / 868 699 875kap. 5, 10
řešení krychle ze sedmi kusů: různých / v pevné krychli240 / 11 520kap. 8
polykostky n = 1…6 (jen otočení)1, 1, 2, 8, 29, 166kap. 8
pevná polyomina n = 14 / 157 204 874 / 27 394 666kap. 9
náhodný kus se nevejde, obtížnost 4, 32–39 plných polí9,7 %kap. 7
čtverec 3 × 3 se nevejde, 32–39 / 40–47 plných polí52,5 / 92,1 %kap. 7
průměr tahů na obtížnosti 4: náhodně / hladově / hodnocení desky11,5 / 17,8 / 64,0kap. 12
náhodný zásobník nejde položit, 32–39 plných polí12,1 %kap. 12
PřílohaC

Zdroje a předpoklady

Historie a výsledky výzkumu

  • H. E. Dudeney: The Canterbury Puzzles and Other Curious Problems, Londýn 1907, úloha č. 74 „The Broken Chessboard“ – šachovnice z dvanácti pentomin a čtverce 2 × 2. Ověřeno 9. 11. 2026.
  • S. W. Golomb: Checker Boards and Polyominoes. American Mathematical Monthly 61 (10), 1954, s. 675–682; kniha Polyominoes, Scribner 1965, 2. vydání Princeton University Press 1994. Ověřeno 9. 11. 2026.
  • M. Gardner: sloupek Mathematical Games, Scientific American, prosinec 1957 (podle seznamu sloupků); o prořezané šachovnici únor 1957. Ověřeno 9. 11. 2026.
  • D. S. Scott: Programming a combinatorial puzzle. Technical Report No. 1, Department of Electrical Engineering, Princeton University, 10. 6. 1958 – 65 řešení šachovnice bez středu, počítač IAS v Princetonu. Ověřeno 9. 11. 2026.
  • C. B. Haselgrove, J. Haselgrove: A computer program for pentominoes. Eureka 23, říjen 1960, s. 16–18 – 2 339 řešení obdélníku 6 × 10. Ověřeno 9. 11. 2026.
  • J. H. Conway, R. K. Guy: 240 řešení krychle ze sedmi kusů (1961); E. R. Berlekamp, J. H. Conway, R. K. Guy: Winning Ways for Your Mathematical Plays, Academic Press 1982. Piet Hein a krychle ze sedmi kusů, 1933. Ověřeno 9. 11. 2026.
  • A. Pažitnov, Výpočetní centrum Dorodnicyna Akademie věd SSSR, počítač Elektronika 60, 1984; hrací plocha 10 × 20, jméno z tetra a tenisu. Ověřeno 9. 11. 2026.
  • M. Black: Critical Thinking, 1946; G. Gamow, M. Stern: Puzzle-Math, 1958 – úloha o prořezané šachovnici. Ověřeno 9. 11. 2026.
  • D. W. Walkup: Covering a rectangle with T-tetrominoes. American Mathematical Monthly 72 (9), 1965, s. 986–988. Ověřeno 9. 11. 2026.
  • D. E. Knuth: Dancing Links. In: Millennial Perspectives in Computer Science, Palgrave 2000, s. 187–214; arXiv cs/0011047. H. Hitotumatu, K. Noshita: A technique for implementing backtrack algorithms and its application. Information Processing Letters 8 (4), 1979, s. 174–175. Ověřeno 9. 11. 2026.
  • D. H. Redelmeier: Counting polyominoes: yet another attack. Discrete Mathematics 36 (2), 1981, s. 191–203. Ověřeno 9. 11. 2026.
  • D. A. Klarner: Cell growth problems. Canadian Journal of Mathematics 19, 1967, s. 851–863 (existence růstové konstanty); D. A. Klarner, R. L. Rivest, 1973 (horní mez 4,6496). Ověřeno 9. 11. 2026.
  • I. Jensen: počty pevných polyomin do n = 46 (2001) a 56 (2003), odhad λ = 4,0625696 ± 0,0000005 (LNCS 2659, 2003). G. Barequet, G. Ben-Shachar: do n = 70 (ALENEX 2024). Ověřeno 9. 11. 2026.
  • G. Barequet, G. Rote, M. Shalah: λ > 4: an improved lower bound on the growth constant of polyominoes. Communications of the ACM 59 (7), 2016 (dolní mez 4,00253); G. Barequet, M. Shalah: Algorithmica 84 (12), 2022 (horní mez 4,5252). Ověřeno 9. 11. 2026.
  • OEIS: A000105 (volná polyomina), A000988 (jednostranná), A001168 (pevná), A001419 (s dírou), A000162 a A038119 (polykostky). Ověřeno 9. 11. 2026.
  • R. M. Karp: Reducibility among combinatorial problems. In: Complexity of Computer Computations, Plenum 1972, s. 85–103. M. R. Garey, D. S. Johnson: SIAM Journal on Computing 4 (4), 1975 (silná NP-úplnost 3-dělení); Computers and Intractability, Freeman 1979. Ověřeno 9. 11. 2026.
  • E. D. Demaine, S. Hohenberger, D. Liben-Nowell: Tetris is Hard, Even to Approximate. COCOON 2003, LNCS 2697, s. 351–363; R. Breukelaar a kol.: International Journal of Computational Geometry and Applications 14 (1–2), 2004, s. 41–68. Ověřeno 9. 11. 2026.
  • S. Asif, M. Coulombe, E. D. Demaine, M. L. Demaine, A. Hesterberg, J. Lynch, M. Singhal: Tetris is NP-hard even with O(1) rows or columns. Journal of Information Processing 28, 2020, s. 942–958. Ověřeno 9. 11. 2026.
  • E. D. Demaine, M. L. Demaine: Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity. Graphs and Combinatorics 23 (Suppl. 1), 2007, s. 195–208. C. Moore, J. M. Robson: Hard tiling problems with simple tiles. Discrete & Computational Geometry 26 (4), 2001, s. 573–590. Ověřeno 9. 11. 2026.

Názvy článků s obchodním názvem hry jsou uvedené jen jako věcný bibliografický údaj.

Co spočítal průvodce sám

Počty polyomin (volných do 12, jednostranných do 10, pevných do 15) a polykostek do 6, počty řešení pentominových obdélníků, šachovnice bez středu a krychle ze sedmi kusů, všechny úlohy „Jde, nebo nejde?“, počty uzlů v tab. 5.3 a 10.1, polohy kusů, situace v minihrách, simulace v kapitolách 7 a 12 i tabulky tvorby úloh spočítal vlastní řešič průvodce – stejný kód, který běží v laboratořích (skripty v pomocné složce průvodce). Počty se shodují s literaturou výše; kde literatura počet neuvádí (uzly, simulace), jde o vlastní výsledky průvodce.

Předpoklady

Skládačka na desce v průvodci a ve 3D hře je vlastní hra průvodce: deska 8 × 8, zásobník tří kusů, současné mizení plných řádků a sloupců, body podle vzorce v kapitole 3, 21 typů kusů a váhy losování podle obtížnosti. Jiné hry tohoto žánru mohou mít jiné kusy, body i pravidla zásobníku. Simulace používají počítačové hráče z kapitoly 12 (náhodný, hladový, hodnocení desky s výchozími vahami), pevná semínka náhody a počty her uvedené u tabulek; čísla jsou odhady s náhodnou chybou řádu jednotek procent. „Uzel“ je jedno položení řádku matice v Algoritmu X; časy jsou z běžného notebooku. Situace v minihrách jsou vybrané automaticky podle pravidel uvedených v popisech laboratoří a jejich správné odpovědi počítá stejný kód při vyhodnocení.

Co zůstává nejisté

Golomb uváděl, že slovo polyomino zavedl v přednášce v roce 1953; tiskem je doložené až v roce 1954. Anekdota, že Piet Hein vymyslel krychli při Heisenbergově přednášce, i přesné datum dánského patentu (uvádí se prosinec 1933) pocházejí z pozdějších vyprávění. Měsíc Gardnerova sloupku o polyominech uvádějí zdroje různě (nejčastěji prosinec 1957, sběratelský zdroj květen 1957). Datum 6. června 1984 je oficiální datum dokončení hry s padajícími kostkami; první verze mimo SSSR se objevily od roku 1985. Rozšíření mobilních skládaček s mizením řádků i sloupců „kolem let 2014–2016“ je přibližné a průvodce záměrně nejmenuje konkrétní aplikace. Podrobnost, jak Scott ve svém programu zacházel s polohou kříže X, známe jen ze sekundárních popisů. Kdo jako první vyřešil prořezanou šachovnici obarvením, není jisté. Pro skládačky s mizením řádků i sloupců na rostoucí desce jsme přímý výsledek o složitosti v literatuře neověřili.

Interaktivní průvodce Blokové 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ů.