Pentomino (z jiného řeckého πέντα pět a domino ) - pětičlánkové polyomino , tedy ploché figury, z nichž každá sestává z pěti stejných čtverců spojených stranami („ tah věže “). Stejné slovo se někdy nazývá puzzle, ve kterém se vyžaduje, aby takové postavy byly položeny do obdélníku nebo jiných tvarů.
Celkem se jedná o 12 různých figurek (prvků) pentominoes, označovaných latinskými písmeny, jejichž tvarem se podobají [1] (viz obrázek). Předpokládá se, že zrcadlová symetrie a rotační symetrie nevytvářejí nové postavy. Pokud ale započítáme i zrcadlené figurky, pak se jejich počet zvýší na 18. Na takovém rozdílu záleží například v počítačové hře, variace " Tetris " - " Pentix ".
Pokud vezmeme v úvahu otočení obrázků o 90 °, pak existují následující kategorie symetrie:
Počet pevných pentomin je tedy 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.
Zde je například osm možných způsobů, jak orientovat pentomina L, F, P, N a Y:
Nejčastějším úkolem v pentominu je složit všechny figurky, bez přesahů a mezer, do obdélníku. Protože každá z 12 figurek obsahuje 5 čtverců, musí mít obdélník plochu 60 jednotkových čtverců. Jsou možné obdélníky 6x10, 5x12, 4x15 a 3x20. Každý z těchto hlavolamů lze vyřešit ručně, ale obtížnějším úkolem je vypočítat celkový počet možných řešení v každém případě (obdélníky 2 × 30 a 1 × 60 samozřejmě nelze vytvořit z pentomina, protože mnoho tvarů prostě se nevejdou na šířku).
Pro případ 6 × 10 byl tento problém poprvé vyřešen v roce 1965 Johnem Fletcherem [2] . V obdélníku 6×10 je 2339 různých uspořádání pentomina, přičemž se nepočítají rotace a odrazy celého obdélníku, ale započítávají se rotace a odrazy jeho částí (někdy se uvnitř obdélníku vytvoří symetrická kombinace tvarů, jejichž otáčením můžete získat další řešení; pro obdélník 3×20 uvedený na obrázku lze druhé řešení získat otočením bloku 7 figurek, nebo jinými slovy, prohozením čtyř postav, krajní levice a jedné krajní pravé ).
Pro obdélník 5 × 12 existuje 1010 řešení, 4 × 15 - 368 řešení, 3 × 20 - pouze 2 řešení (která se liší výše popsanou rotací). Konkrétně existuje 16 způsobů, jak sečíst dva obdélníky 5×6, což může vytvořit jak obdélník 6×10, tak obdélník 5×12.
Skládání obdélníků z jednostranných pentominPokud sadu pentomin doplníte zrcadlovými kopiemi postav, které se neshodují s jejich odrazy (F, L, P, N, Y a Z), pak z kompletní sady 18 jednostranných pentomin můžete doplnit obdélníky s plocha 90 jednotkových čtverců (zatímco figurky se nesmí obracet) . Úloha obdélníku 3×30 má 46 řešení, 5×18 má přes 600 000 řešení, 6×15 má více než 2 miliony řešení a 9×10 má více než 10 milionů řešení [3] .
Do jisté míry jednodušší (symetričtější) problém, pro čtverec 8×8 s otvorem 2×2 uprostřed, vyřešila v roce 1958 Dana Scott [4] (postgraduální studentka matematiky na Princetonu). Pro tento případ existuje 65 řešení. Scottův algoritmus byl jednou z prvních aplikací zpětného počítačového programu .
Další variantou tohoto puzzle je rozložení čtverce 8×8 se 4 otvory na libovolných místech. Většina těchto problémů má řešení. Výjimkou je umístění dvou párů otvorů blízko dvou rohů desky tak, že do každého rohu lze umístit pouze P-pentamino, nebo všechny čtyři otvory blízko jednoho rohu tak, aby pro případné vyplnění rohové buňky (pomocí U- popř. T-pentomino) je z desky odříznuta ještě jedna buňka (viz obrázek).
Pro řešení těchto problémů popsal efektivní algoritmy např. Donald Knuth [5] [6] . Na moderním počítači lze takové hádanky vyřešit během několika sekund.
Pokládání zvířecích figurek, předmětů a vybaveníZ puzzle můžete vyskládat zvířata, ptáky a ryby, stejně jako rostliny, různé předměty a vybavení. V tomto případě je použito všech 12 prvků pentomino a jejich část.
Tento problém navrhl profesor R. M. Robinson z Kalifornské univerzity. Po výběru jedné z 12 figurek pentomina je nutné sestavit z libovolných 9 z 11 zbývajících pentomin figurku podobnou vybrané, ale 3x delší a širší. Řešení existuje pro kterékoli z 12 pentomino, a ne jediné (od 15 řešení pro X po 497 pro P) [3] . Existuje varianta tohoto problému, ve které je dovoleno použít samotnou původní figuru ke konstrukci trojité figury. V tomto případě je počet roztoků od 20 pro X do 9144 pro P-pentamino [7] .
Řešení znázorněné na obrázku [8] , které našel A. van de Wetering, má zajímavou vlastnost: každé pentomino se používá ke ztrojnásobení devíti ostatních, jednou v každém. Z 9 sad počátečních figur pentomina lze tedy přidat všech 12 ztrojených pentomin současně.
Pentomino lze využít i jako deskovou hru pro dva hráče [9] . Ke hře potřebujete šachovnici 8×8 a sadu figurek pentomino, jejichž buňky mají stejnou velikost jako buňky šachovnice. Na začátku hry je hrací plocha prázdná. Hráči střídavě pokládají jednu figurku na hrací desku a zakryjí 5 volných buněk hrací desky. Všechny odkryté figurky zůstávají na svém místě až do konce hry (neodstraňují se z hrací desky a nehýbou se). Poraženým je hráč, který nemůže provést tah jako první (buď proto, že se žádná ze zbývajících figurek nevešla na volná místa na desce, nebo protože všech 12 figurek již bylo umístěno na desku).
Rozbor hry je poměrně složitý (např. na začátku je ještě více možných prvních tahů než v šachu). Golomb navrhl následující strategii: pokuste se rozdělit volné místo na herním plánu na dvě stejné oblasti (a zabránit v tom protivníkovi). Poté by měl být každý soupeřův tah v jedné z sekcí zodpovězen tahem v druhé.
Příklad hry pentomino je znázorněn na obrázku. Číslování tahů je od začátku do konce (lichý počet tahů patří prvnímu hráči, sudá čísla patří druhému). Zpočátku hráči dělají tahy ve středu desky (tahy 1-3), čímž si navzájem brání v rozdělení desky na stejné části. Pak ale druhý hráč provede neúspěšný tah (4), čímž umožní soupeři rozdělit volné místo na dvě části po 16 buňkách (tah 5). (V tomto příkladu jsou volné úseky nejen plošně stejné, ale také se tvarově shodují - jsou symetrické vzhledem k úhlopříčce desky, ale to samozřejmě není pro strategii nutné.) Dále na tah druhého hráče (6) v jedné z těchto sekcí, první hráč odpoví tahem na druhou (7) a vyhrává. Přestože jsou na herním plánu ještě tři volné oblasti po pěti nebo více buňkách, všechny vhodné figurky (I, P, U) již byly použity.
V této variantě hry se hráči nejprve střídají ve výběru jedné figurky, dokud se mezi ně nerozdělí všechny figurky. Dále hra probíhá podle pravidel obvyklého pentomina s tím rozdílem, že každý z hráčů smí hýbat pouze figurkami, které si sám vybral. Ten, kdo vezme poslední dílek, udělá první tah.
Strategie této varianty hry navržená Golombem se výrazně liší od strategie obvyklého pentomina. Namísto dělení hrací desky na stejně velké části se hráč snaží vytvořit na desce části, které lze zaplnit pouze jeho figurkami, ale ne figurkami soupeře. (Golomb takové oblasti označuje jako „uprchlíci“.)
Příklad hry pentomino s předem vybranými figurkami je na obrázku. Figurky vybrané prvním a druhým hráčem jsou uvedeny vlevo a vpravo na desce. Přeškrtnuté písmeno znamená, že figurka byla použita pro tah. Nejprve se hráči zbaví nejvíce „nepohodlných“ kusů X a W (tahy 1 a 2). Poté první hráč vytvoří "úkryt" pro figurku Y (tahy 3), druhý - pro figurky U a P (tahy 4 a 6). Na konci hry (tahy 8-10) se tyto "úkryty" zaplní a hra končí vítězstvím druhého hráče - prvnímu hráči zůstane pentomino ve tvaru T, pro které není vhodné místo na zbytku desky.
Další možnostiOd konce 80. let byly různé počítačové hry založené na pentominu vydány mnohokrát. Nejznámější je hra Pentix založená na myšlence Tetris . Jedním z nejnovějších příkladů je hra Dwice, kterou v roce 2006 vyvinul vynálezce Tetris Aleksey Pajitnov .
Ze všech pentomin má R-pentomino nejdelší vývoj. Evoluce tohoto pentomina se stává triviální až po 1103 generacích [10] [11] . Po 1103 generacích vývoje R-pentamino se populace skládá z 25 objektů: 8 bloků , 6 kluzáků , 4 úly , 4 blikače , 1 člun, 1 bochník a 1 loď [10] [12] .
První ze šesti kluzáků vzniká po 69 generacích evoluce. Viděl ho v roce 1970 Richard Guy a byl to první kluzák, který byl zaznamenán [10] [11] [12] .
| Polyformy | |
|---|---|
| Typy polyformů | |
| Polyomino podle počtu buněk | |
| Puzzle s polycubes | |
| Úkol skládání |
|
| Osobnosti |
|
| související témata | |
| Další hádanky a hry | |
| Tetris | |
|---|---|
| Hlavní |
|
| Potomci hry |
|
| Přenosné hry |
|
| Možnosti hry |
|
