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.
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
| Kapitola | Úroveň | Co se naučíte |
|---|---|---|
| 1 Kostky, tvary a historie | základy | co 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 polyomin | základy | volné, jednostranné a pevné tvary, dvanáct pentomin a jejich písmena, souměrnosti, zrcadlové dvojice |
| 3 Deska, řady a body | základy | pravidla 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érie | základy | proč záleží na pořadí tří kusů, Dvojité vymazání, série a bonus, kalkulačka bodů |
| 5 Pentomina na obdélníku | pokroč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á pole | pokroč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 polyomin | mistr a věda | počí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žitost | mistr a věda | NP-ú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í úlohy | mistr a věda | hodnoticí 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.
| Obtížnost | Kusy a zásobník | Kapitoly |
|---|---|---|
| 1 Pohodová | malé kusy do čtyř kostek, otáčení klepnutím, férový zásobník | 3 |
| 2 Lehká | kusy do čtyř kostek, otáčení, férový zásobník | 3, 4 |
| 3 Střední | pentomina a čtverec 3 × 3, bez otáčení, férový zásobník | 3, 4, 7 |
| 4 Těžká | jako 3, ale náhodný zásobník – nemusí jít položit všechny tři | 4, 7 |
| 5 Mistrovská | náhodný zásobník a víc velkých kusů | 7, 12 |
Čtyři druhy rámečků
Konkrétní deska, tvar nebo výpočet, který si můžete ověřit v laboratoři.
Kdo hlavolam vymyslel, kdo spočítal jeho řešení a co o něm dokázali matematici.
Rychlé pravidlo, zkratka nebo návyk, který používají zkušení hráči.
Častá chyba, mýtus nebo past, do které se snadno spadne.
Studijní materiál o hře. Hrajte pro radost a s mírou – bez sázek a peněz. Průvodce nejmenuje ani nedoporučuje žádné aplikace ani hry; obchodní názvy se objevují jen ve věcné historii. 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.
Skládačka z kostek ve 3D
🎮 Zpět ke hře Hra je nahoře na této stránce. Tlačítkem 📲 v její liště si ji nainstalujete do telefonu nebo počítače a hrajete i bez připojení.
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.
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.
+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
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“.
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).
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
| Rok | Událost |
|---|---|
| 1907 | Henry 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. |
| 1933 | Dá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–1954 | Solomon 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). |
| 1957 | Martin Gardner píše o polyominech ve sloupku Mathematical Games v Scientific American (podle seznamu sloupků v prosinci 1957). |
| 1958 | Dana 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. |
| 1960 | C. B. a Jenifer Haselgroveovi publikují 2 339 řešení obdélníku 6 × 10. |
| 1961 | John H. Conway a Richard K. Guy určí 240 řešení krychle ze sedmi kusů. |
| 1965 | Golombova kniha Polyominoes (2. vydání 1994). |
| 1984 | Alexej 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ě. |
| 2000 | Donald E. Knuth popisuje Algoritmus X s tancem odkazů (kapitola 10). |
| 2003 | Demaine, Hohenberger a Liben-Nowell dokazují, že padající kostky se známou řadou kusů jsou NP-úplné (kapitola 11). |
| kolem 2014–2016 | Na mobilních telefonech se rozšiřují skládačky na desce bez padání, ve kterých mizí plné řádky i sloupce. |
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.
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í
- 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.
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.
+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
| Kostek n | Volné | Jednostranné | Pevné | Volné s dírou |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 2 | 0 |
| 3 | 2 | 2 | 6 | 0 |
| 4 | 5 | 7 | 19 | 0 |
| 5 | 12 | 18 | 63 | 0 |
| 6 | 35 | 60 | 216 | 0 |
| 7 | 108 | 196 | 760 | 1 |
| 8 | 369 | 704 | 2 725 | 6 |
| 9 | 1 285 | 2 500 | 9 910 | 37 |
| 10 | 4 655 | 9 189 | 36 446 | 195 |
2.2Dvanáct pentomin
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).
| Pentomina | Natočení | Souměrností | Chirální |
|---|---|---|---|
| F, L, N, P, Y | 8 | 1 | ano |
| Z | 4 | 2 (otočení o 180°) | ano |
| T, U, V, W | 4 | 2 (osa) | ne |
| I | 2 | 4 | ne |
| X | 1 | 8 | ne |
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.
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í
- 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.
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.
+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á:
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.
Řá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.
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.
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í.
| Kus | Poloh | Otočení | Kus | Poloh | Otočení |
|---|---|---|---|---|---|
| jedna kostka | 64 | 1 | Z | 84 | 2 |
| domino | 112 | 2 | pětice | 64 | 2 |
| rovné trimino | 96 | 2 | velký roh | 144 | 4 |
| malý roh | 196 | 4 | dlouhé L / J | 140 | 4 |
| čtverec 2 × 2 | 49 | 1 | P / zrcadlové P | 168 | 4 |
| rovná čtveřice | 80 | 2 | velké T | 144 | 4 |
| T | 168 | 4 | U | 168 | 4 |
| L / J | 168 | 4 | kříž | 36 | 1 |
| S | 84 | 2 | čtverec 3 × 3 | 36 | 1 |
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í
- 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.
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.
+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.
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í.
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
| Řad naráz k | s = 1 | s = 2 | s = 3 | s = 4 |
|---|---|---|---|---|
| 1 | 80 | 120 | 160 | 200 |
| 2 | 320 | 480 | 640 | 800 |
| 3 | 720 | 1 080 | 1 440 | 1 800 |
| 4 | 1 280 | 1 920 | 2 560 | 3 200 |
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.
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í
- Ř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.
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ů.
+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í
| Oblast | Různých řešení | Všech řešení | Řádků matice | Uzlů prohledávání | Čas |
|---|---|---|---|---|---|
| 6 × 10 | 2 339 | 9 356 | 2 056 | 4 056 445 | 7,9 s |
| 5 × 12 | 1 010 | 4 040 | 1 936 | 2 488 525 | 5,2 s |
| 4 × 15 | 368 | 1 472 | 1 696 | 933 288 | 1,9 s |
| 3 × 20 | 2 | 8 | 1 236 | 35 725 | 0,07 s |
| 8 × 8 bez středu 2 × 2 | 65 | 520 | 1 568 | 319 074 | 0,6 s |
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.
| F | I | L | N | P | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 256 | 56 | 248 | 248 | 304 | 128 | 152 | 128 | 128 | 32 | 248 | 128 |
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).
| Oblast | Pole s nejméně možnostmi | Vždy první volné pole |
|---|---|---|
| 6 × 10 | 862 | 301 017 |
| 5 × 12 | 1 071 | 485 230 |
| 4 × 15 | 216 | 64 105 |
| 3 × 20 | 238 | 868 699 875 |
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.
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í
- 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.
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ší.
+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
Ú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.
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í.
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.
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.
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.
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í
- 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í.
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.
+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í
| Plných polí | Stavů | Náhodný kus | 3 × 3 | Pětice | Velký roh | Kříž | 2 × 2 | Rovná čtveřice | Malý roh |
|---|---|---|---|---|---|---|---|---|---|
| 0–15 | 4 245 | 0,0 | 0,1 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 |
| 16–23 | 7 019 | 0,2 | 2,8 | 0,7 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 |
| 24–31 | 6 633 | 1,7 | 15,5 | 5,0 | 1,7 | 2,1 | 0,0 | 0,3 | 0,0 |
| 32–39 | 2 385 | 9,7 | 52,5 | 19,9 | 16,6 | 22,0 | 2,4 | 3,3 | 0,1 |
| 40–47 | 302 | 32,9 | 92,1 | 47,0 | 57,4 | 67,2 | 21,5 | 21,4 | 3,6 |
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ř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
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.
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.
„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í
- 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.
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ř.
+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
| Kostek | Jen otočení | I zrcadlení | Pevné |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 3 |
| 3 | 2 | 2 | 15 |
| 4 | 8 | 7 | 86 |
| 5 | 29 | 23 | 534 |
| 6 | 166 | 112 | 3 481 |
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).
| Kus | Natočení (24 otočení) | Se zrcadlením | Umístění v krychli | Šachovnicová nerovnováha |
|---|---|---|---|---|
| V malý roh | 12 | 12 | 144 | 1 |
| L | 24 | 24 | 144 | 0 |
| T | 12 | 12 | 72 | 2 |
| Z | 12 | 12 | 72 | 0 |
| A šroub | 12 | 24 (s B) | 96 | 0 |
| B šroub | 12 | 24 (s A) | 96 | 0 |
| P trojnožka | 8 | 8 | 64 | 2 |
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í.
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:
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ů.
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“.
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í
- 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.
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.
+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.
| n | Volná | Volná s dírou | Pevná | Poměr pevných A(n)/A(n−1) |
|---|---|---|---|---|
| 7 | 108 | 1 | 760 | 3,5185 |
| 8 | 369 | 6 | 2 725 | 3,5855 |
| 9 | 1 285 | 37 | 9 910 | 3,6367 |
| 10 | 4 655 | 195 | 36 446 | 3,6777 |
| 11 | 17 073 | 979 | 135 268 | 3,7115 |
| 12 | 63 600 | 4 663 | 505 861 | 3,7397 |
| 13 | – | – | 1 903 890 | 3,7637 |
| 14 | – | – | 7 204 874 | 3,7843 |
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í.
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.
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
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.
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.
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í
- 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.
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.
+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
10.2Algoritmus X
- Nezbývá-li žádný sloupec, je vybraná množina řádků řešení.
- Vyber sloupec c (deterministicky – nejlépe ten s nejméně jedničkami). Má-li 0 jedniček, tato větev řešení nemá.
- 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:
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í
| Úloha | Různých řešení | Nejméně možností | Vždy první sloupec |
|---|---|---|---|
| L, T, Y do 5 × 3 (všechna řešení) | 1 | 15 | 15 |
| N, T, V, Y do 5 × 4 (všechna) | 1 | 56 | 100 |
| F, L, P, U, X do 5 × 5 (všechna) | 1 | 49 | 410 |
| L, P, T, V, W, X do 6 × 5 (všechna) | 1 | 66 | 1 412 |
| všech 12 do 6 × 10 (první řešení) | 2 339 | 862 | 301 017 |
| všech 12 do 3 × 20 (první řešení) | 2 | 238 | 868 699 875 |
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.
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.
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í
- 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.
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á.
+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
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á.
11.3Těžké v nejhorším případě, ne vždy
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.
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í.
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.
Č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í
- 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á.
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.
+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á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.
12.2Tři strategie
| Obtížnost | Náhodně: medián tahů / bodů | Hladově: medián tahů / bodů | Hodnocení desky: medián tahů / bodů |
|---|---|---|---|
| 1 Pohodová | 29 / 561 | 308 / 10 596 | 900+ / 35 548 |
| 2 Lehká | 20 / 309 | 95 / 3 966 | 900+ / 45 009 |
| 3 Střední | 13 / 132 | 44 / 1 800 | 164 / 10 370 |
| 4 Těžká | 11 / 113 | 16 / 390 | 50 / 2 765 |
| 5 Mistrovská | 10 / 46 | 14 / 385 | 29 / 1 757 |
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č.
| Plných polí | 0–15 | 16–23 | 24–31 | 32–39 | 40–47 |
|---|---|---|---|---|---|
| Nepoložitelných zásobníků | 0,0 % | 0,7 % | 2,8 % | 12,1 % | 18,1 % |
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č.
| Odebráno kusů k | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| jediné dokončení | 98 % | 100 % | 93 % | 93 % | 73 % | 88 % | 63 % |
| průměr dokončení | 1,0 | 1,0 | 1,1 | 1,1 | 1,3 | 1,2 | 1,9 |
| průměr uzlů řešiče | 2 | 3 | 5 | 8 | 14 | 32 | 92 |
Ú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í.
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í
- 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í.
Slovníček
Česká hesla s anglickým termínem. Hledat lze v obou jazycích.
Vzorce a přehledy
Techniky trenéra
| Technika | Co dělá | Kapitola |
|---|---|---|
| Dokončit řadu | položit kus tak, aby doplnil řádek nebo sloupec a uvolnil místo | 3 |
| Místo pro velké kusy | nechat volný blok 3 × 3 a úsek pro pětici | 3 |
| 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šechny | 4 |
| Úzké místo | u pentomin začít polem, kam se vejde nejméně kusů | 5 |
| Bez osamělých polí | nevytvářet volná pole bez volného souseda | 7 |
Vzorce na jednom místě
Čísla z kapitol
| Údaj | Hodnota | Kde |
|---|---|---|
| volná polyomina n = 1…8 | 1, 1, 2, 5, 12, 35, 108, 369 | kap. 2, 9 |
| pevná tetromina / pentomina / hexomina | 19 / 63 / 216 | kap. 2 |
| řešení 6 × 10 / 5 × 12 / 4 × 15 / 3 × 20 | 2 339 / 1 010 / 368 / 2 | kap. 5 |
| řešení šachovnice 8 × 8 bez středu 2 × 2 | 65 | kap. 5 |
| uzly k prvnímu řešení 3 × 20: úzké místo / první pole | 238 / 868 699 875 | kap. 5, 10 |
| řešení krychle ze sedmi kusů: různých / v pevné krychli | 240 / 11 520 | kap. 8 |
| polykostky n = 1…6 (jen otočení) | 1, 1, 2, 8, 29, 166 | kap. 8 |
| pevná polyomina n = 14 / 15 | 7 204 874 / 27 394 666 | kap. 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í desky | 11,5 / 17,8 / 64,0 | kap. 12 |
| náhodný zásobník nejde položit, 32–39 plných polí | 12,1 % | kap. 12 |
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.