Pentomino ( más görög πέντα öt és dominó szóból ) - ötsejtű poliominók , azaz lapos figurák, amelyek mindegyike öt azonos négyzetből áll, amelyeket oldalak kötnek össze (" bástyás mozdulat "). Ugyanezt a szót néha rejtvénynek is nevezik, amelyben az ilyen figurákat téglalapba vagy más alakzatba kell rakni.
Összesen 12 különböző, latin betűkkel jelölt pentominó-figura (elem) található, amelyek alakja hasonlít [1] (lásd az ábrát). Úgy tartják, hogy a tükörszimmetria és a forgásszimmetria nem hoz létre új figurákat. De ha a tükrözött figurákat is megszámoljuk, akkor számuk 18-ra nő. Ilyen különbség számít például egy számítógépes játékban, a " Tetris " - " Pentix " variációinál.
Ha figyelembe vesszük az ábrák 90 ° -os elforgatását, akkor a következő szimmetriakategóriák vannak:
Ezért a rögzített pentominók száma 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.
Például itt van nyolc lehetséges módja az L, F, P, N és Y pentominók tájolásának:
A pentominóban a leggyakoribb feladat az összes figura átfedések és hézagok nélkül téglalappá hajtogatása. Mivel mind a 12 figura 5 négyzetet tartalmaz, a téglalap területe 60 egységnyi négyzet kell legyen. 6x10, 5x12, 4x15 és 3x20 téglalapok lehetségesek. Ezek a rejtvények mindegyike kézzel is megoldható, de a nehezebb feladat minden esetben a lehetséges megoldások számának kiszámítása (nyilván a 2 × 30 és 1 × 60 téglalapok nem készíthetők pentominóból, mivel sok alakzat egyszerűen nem fér el a szélességben).
A 6 × 10 esetnél ezt a problémát először 1965-ben John Fletcher oldotta meg [2] . Egy 6×10-es téglalapban 2339 különböző pentominó-elrendezés található, nem a teljes téglalap forgását és visszaverődését számolva, hanem a részeinek elfordulását és visszaverődését (a téglalap belsejében esetenként szimmetrikus alakzat-kombináció alakul ki, amelyet elforgatva) további megoldásokat kaphat, az ábrán megadott 3×20-as téglalap esetén a második megoldást egy 7 figurából álló blokk elforgatásával, vagyis négy figura, a bal szélső és egy jobb szélső felcserélésével kaphatjuk meg. ).
Egy 5 × 12-es téglalaphoz 1010 megoldás létezik, 4 × 15 - 368 megoldás, 3 × 20 - csak 2 megoldás (amelyek a fent leírt elforgatásban különböznek). Konkrétan 16 módja van két 5 × 6-os téglalap összeadásának, amely 6 × 10-es és 5 × 12-es téglalapokat is létrehozhat.
Téglalapok egymásra rakása egyoldalas pentominóbólHa kiegészíti a pentominó készletet olyan figurák tükörmásolatával, amelyek nem esnek egybe a tükröződésükkel (F, L, P, N, Y és Z), akkor a 18 egyoldalú pentominó teljes készletéből téglalapokat adhat hozzá 90 egységnégyzet terület (miközben a figurákat nem szabad megfordítani). A 3×30-as téglalap feladatnak 46 megoldása van, az 5×18-nak több mint 600 000, a 6×15-nek több mint 2 millió, a 9×10-nek pedig több mint 10 millió megoldása [3] .
Bizonyos mértékig egy egyszerűbb (szimmetrikusabb) problémát, egy 8×8-as négyzetre, amelynek közepén egy 2×2-es lyuk van, még 1958-ban megoldott Dana Scott [4] (egy végzős matematikus hallgató a Princetonban). Erre az esetre 65 megoldás létezik. Scott algoritmusa volt az egyik legkorábbi alkalmazása a visszafelé haladó számítógépes programoknak .
Ennek a kirakós játéknak egy másik változata egy 8×8-as négyzet tetszőleges helyeken történő elhelyezése 4 lyukkal. Ezeknek a problémáknak a többségére van megoldás. Kivételt képeznek, ha két pár lyukat helyeznek el a tábla két sarka közelében úgy, hogy csak a P-pentamino helyezhető el minden sarokba, vagy mind a négy lyuk az egyik sarok közelében, így a sarokcella esetleges kitöltéséhez (U- ill. T- pentomino) még egy cellát levágunk a tábláról (lásd a képet).
E problémák megoldására hatékony algoritmusokat írt le például Donald Knuth [5] [6] . Egy modern számítógépen pillanatok alatt meg lehet oldani az ilyen rejtvényeket.
Állatfigurák, tárgyak és felszerelések fektetéseA rejtvényből állatokat, madarakat és halakat, valamint növényeket, különféle tárgyakat és felszereléseket rakhatsz ki. Ebben az esetben mind a 12 pentominó elemet és azok egy részét is felhasználják.
Ezt a problémát R. M. Robinson professzor, a Kaliforniai Egyetem professzora javasolta. A 12 pentominó egyikének kiválasztása után a fennmaradó 11 pentominó közül bármelyik 9-ből a kiválasztotthoz hasonló, de háromszor hosszabb és szélesebb figurát kell építeni. A 12 pentominó bármelyikére létezik megoldás, és nem az egyetlen (15 megoldástól X-ig 497 P-ig) [3] . Ennek a feladatnak van egy olyan változata, amelyben megengedett, hogy magát az eredeti figurát használjuk fel egy háromszoros figura megalkotásához. Ebben az esetben az oldatok száma 20-tól X-től 9144-ig a P-pentamino esetében [7] .
A [8] ábrán látható megoldásnak , amelyet A. van de Wetering talált meg, van egy érdekes tulajdonsága: minden pentominó a többi közül kilenc háromszorozására szolgál, mindegyikben egyszer. Így 9 kezdeti pentominó készletből mind a 12 háromszoros pentominó hozzáadható egyszerre.
A Pentomino társasjátékként is használható két játékos számára [9] . A játékhoz egy 8×8-as sakktábla és egy sor pentominó kell, amelyek cellái akkorák, mint a tábla cellái. A játék elején a tábla üres. A játékosok felváltva helyeznek el egy darabot a táblára, lefedve a tábla 5 szabad celláját. Minden kitett bábu a helyén marad a játék végéig (nem távolítják el a tábláról és nem mozdulnak el). A vesztes az a játékos, aki nem tud először lépést tenni (vagy azért, mert a megmaradt bábu egyike sem fér el a tábla szabad területein, vagy azért, mert mind a 12 bábu már felkerült a táblára).
A játék elemzése meglehetősen bonyolult (például az elején még több első lépés lehetséges, mint a sakkban). Golomb a következő stratégiát javasolta: próbálja meg két egyenlő területre osztani a táblán lévő szabad helyet (és akadályozza meg az ellenfelet ebben). Ezt követően minden ellenfél lépésére az egyik szakaszban egy lépéssel kell válaszolni a másikban.
A pentomino játék példája látható az ábrán. A lépések számozása végponttól-végig történik (a páratlan számú lépés az első játékosé, a páros szám a másodiké). Kezdetben a játékosok a tábla közepén mozognak (1-3 lépések), megakadályozva egymást abban, hogy a táblát egyenlő területekre osztsák fel. Ekkor azonban a második játékos sikertelen mozdulatot hajt végre (4), így az ellenfél feloszthatja a szabad helyet két 16 cellából álló részre (5. lépés). (Ebben a példában a szabad szakaszok nemcsak területükben egyenlőek, hanem alakjukban is egybeesnek - szimmetrikusak a tábla átlójához képest, de ez természetesen nem szükséges a stratégiához.) Továbbá a a második játékos lépése (6) az egyik szakaszon, az első játékos válaszol a másikra (7) és nyer. Bár még van három szabad terület öt vagy több cellából a táblán, az összes megfelelő elemet (I, P, U) már felhasználták.
A játéknak ebben a változatában a játékosok először felváltva választanak ki egy-egy darabot, amíg az összes darabot szét nem osztják közöttük. Továbbá a játék a szokásos pentomino szabályai szerint zajlik, azzal a különbséggel, hogy minden játékos csak az általa kiválasztott figurákkal mozoghat. Az első lépést az teszi meg, aki elveszi az utolsó darabot.
A Golomb által javasolt játék ezen változatának stratégiája jelentősen eltér a szokásos pentomino stratégiájától. Ahelyett, hogy a táblát egyenlő méretű részekre osztaná, a játékos olyan részeket igyekszik létrehozni a táblán, amelyeket csak az ő bábujával lehet megtölteni, az ellenfél bábuival nem. (Golomb az ilyen területeket "menekülteknek" nevezi.)
Az ábrán látható egy példa egy pentomino játékra előre kiválasztott darabokkal. Az első és a második játékos által választott bábu a tábla bal és jobb oldalán található. Az áthúzott betű azt jelzi, hogy a darabot mozgáshoz használták. Először a játékosok megszabadulnak a „legkényelmetlenebb” X és W daraboktól (1. és 2. lépés). Ezután az első játékos „menedéket” hoz létre az Y bábu számára (3. lépés), a második pedig az U és P figurák számára (4. és 6. lépés). A játék végén (8-10. lépések) ezek a "menedékek" megtelnek, és a játék a második játékos győzelmével ér véget - az első játékosnak marad egy T-alakú pentomino, amihez nincs megfelelő hely. a tábla többi részén.
Egyéb lehetőségekAz 1980-as évek vége óta számos pentominó-alapú számítógépes játékot adtak ki. A leghíresebb a Tetris ötletén alapuló Pentix játék . Az egyik legújabb példa a Dwice játék, amelyet 2006-ban a Tetris feltalálója , Aleksey Pajitnov fejlesztett ki .
Az összes pentominó közül az R-pentominónak van a leghosszabb fejlődése. Ennek a pentominónak az evolúciója csak 1103 generáció után válik triviálissá [10] [11] . 1103 generációs R-pentamino fejlesztés után a populáció 25 objektumból áll: 8 blokkból , 6 siklóból , 4 méhkasból , 4 villogóból , 1 csónakból, 1 cipóból és 1 hajóból [10] [12] .
A hat sikló közül az első 69 generációnyi fejlődés után jött létre. Richard Guy látta 1970-ben, és ez volt az első sikló, amelyet rögzítettek [10] [11] [12] .
| Poliformok | |
|---|---|
| A poliformok fajtái | |
| Polyomino a sejtek száma szerint | |
| Rejtvények polikockákkal | |
| Halmozási feladat |
|
| Személyiségek |
|
| Kapcsolódó témák | |
| Egyéb rejtvények és játékok | |
| Tetris | |
|---|---|
| Fő |
|
| A játék leszármazottai |
|
| Hordozható játékok |
|
| Játéklehetőségek |
|
