Pentomino (från annan grekisk πέντα fem , och domino ) - femcelliga polyominoer , det vill säga platta figurer, som var och en består av fem identiska rutor förbundna med sidorna (" tornets drag "). Samma ord kallas ibland ett pussel, där sådana figurer måste läggas i en rektangel eller andra former.
Totalt finns det 12 olika figurer (element) av pentominoer, betecknade med latinska bokstäver, vars form de liknar [1] (se figur). Man tror att spegelsymmetri och rotationssymmetri inte skapar nya figurer. Men om vi också räknar de speglade figurerna, kommer deras antal att öka till 18. En sådan skillnad spelar roll, till exempel i ett datorspel, varianter av " Tetris " - " Pentix ".
Om vi betraktar rotationen av figurer med 90 °, finns det följande kategorier av symmetri:
Därför är antalet fasta pentominoer 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.
Till exempel, här är åtta möjliga sätt att orientera pentomino L, F, P, N och Y:
Den vanligaste uppgiften i pentomino är att vika alla figurer, utan överlappningar och mellanrum, till en rektangel. Eftersom var och en av de 12 figurerna innehåller 5 rutor, måste rektangeln ha en area på 60 enhetsrutor. Rektanglar 6x10, 5x12, 4x15 och 3x20 är möjliga. Var och en av dessa pussel kan lösas för hand, men den svårare uppgiften är att beräkna det totala antalet möjliga lösningar i varje fall (uppenbarligen kan rektanglarna 2 × 30 och 1 × 60 inte göras av pentominoer, eftersom många av formerna passar helt enkelt inte i bredd).
För 6 × 10-fallet löstes detta problem först 1965 av John Fletcher [2] . Det finns 2339 olika arrangemang av pentominoer i en 6×10 rektangel, inte räknar rotationerna och reflektionerna av hela rektangeln, utan räknar rotationerna och reflektionerna av dess delar (ibland bildas en symmetrisk kombination av former inuti rektangeln, genom att rotera vilken du kan få ytterligare lösningar; för en 3×20 rektangel som anges i figuren kan den andra lösningen erhållas genom att rotera ett block med 7 siffror, eller, med andra ord, genom att byta fyra siffror, den extrema vänster och en extremt höger ).
För en 5 × 12 rektangel finns det 1010 lösningar, 4 × 15 - 368 lösningar, 3 × 20 - endast 2 lösningar (som skiljer sig i rotationen som beskrivs ovan). I synnerhet finns det 16 sätt att lägga till två 5×6 rektanglar tillsammans, vilket kan göra både en 6×10 rektangel och en 5×12 rektangel.
Stapla rektanglar från ensidiga pentominoerOm du kompletterar uppsättningen pentominoer med spegelkopior av figurer som inte sammanfaller med deras reflektioner (F, L, P, N, Y och Z), så kan du från en komplett uppsättning av 18 ensidiga pentominoer lägga till rektanglar med en yta på 90 enhetsrutor (medan figurerna inte får vändas) . 3×30 rektangelproblemet har 46 lösningar, 5×18 har över 600 000 lösningar, 6×15 har mer än 2 miljoner lösningar och 9×10 har mer än 10 miljoner lösningar [3] .
Till viss del löstes ett enklare (mer symmetriskt) problem, för en 8×8 kvadrat med ett 2×2 hål i mitten, redan 1958 av Dana Scott [4] (en doktorand i matematik vid Princeton). Det finns 65 lösningar för detta fall. Scotts algoritm var en av de tidigaste tillämpningarna av ett bakåtspårande datorprogram .
En annan variant av detta pussel är att lägga ut en 8×8 kvadrat med 4 hål på godtyckliga platser. De flesta av dessa problem har en lösning. Undantagen är när man placerar två par hål nära två hörn av brädan så att endast P-pentamino kan placeras i varje hörn, eller alla fyra hål nära ett hörn så att för eventuell fyllning av hörncellen (med hjälp av U- eller T- pentomino) en cell till skärs av från tavlan (se bild).
För att lösa dessa problem beskrevs effektiva algoritmer, till exempel av Donald Knuth [5] [6] . På en modern dator kan sådana pussel lösas på några sekunder.
Lägga djurfigurer, föremål och utrustningFrån pusslet kan du lägga ut djur, fåglar och fiskar, samt växter, olika föremål och utrustning. I det här fallet används både alla 12 pentomino-element och en del av dem.
Detta problem föreslogs av professor R. M. Robinson vid University of California. Efter att ha valt en av de 12 pentominofigurerna är det nödvändigt att bygga en figur från vilken som helst av de 11 återstående pentominoerna en figur som liknar den valda, men 3 gånger längre och bredare. En lösning finns för någon av de 12 pentominoerna, och inte den enda (från 15 lösningar för X till 497 för P) [3] . Det finns en variant av detta problem, där det är tillåtet att använda själva originalfiguren för att konstruera en tredubblad figur. I detta fall är antalet lösningar från 20 för X till 9144 för P-pentamino [7] .
Lösningen som visas i figuren [8] , hittad av A. van de Wetering, har en intressant egenskap: varje pentomino används för att tredubbla nio av de andra, en gång i varje. Alltså, från 9 uppsättningar av initiala pentominofigurer, kan alla 12 tredubblade pentominoer läggas till samtidigt.
Pentomino kan också användas som ett brädspel för två spelare [9] . För att spela behöver du ett 8×8 schackbräde och en uppsättning pentominopjäser, vars celler är lika stora som brädets celler. I början av spelet är spelplanen tom. Spelare placerar växelvis en bit på brädet, som täcker 5 fria celler på brädet. Alla exponerade pjäser förblir på plats till slutet av spelet (de tas inte bort från brädet och rör sig inte). Förloraren är den spelare som inte kan göra ett drag först (antingen för att ingen av de återstående pjäserna får plats på brädets fria ytor, eller för att alla 12 pjäser redan har placerats på brädet).
Analysen av spelet är ganska komplicerad (till exempel finns det i början ännu fler möjliga första drag än i schack). Golomb föreslog följande strategi: försök att dela upp det fria utrymmet på brädet i två lika stora områden (och förhindra motståndaren från att göra detta). Därefter ska varje motståndares drag i en av sektionerna besvaras med ett drag i den andra.
Ett exempel på ett pentominospel visas i figuren. Numreringen av drag är från början (udda antal drag tillhör den första spelaren, jämna nummer tillhör den andra). Till en början gör spelarna drag i mitten av brädet (drag 1-3), vilket hindrar varandra från att dela brädet i lika delar. Men sedan gör den andra spelaren ett misslyckat drag (4), vilket låter motståndaren dela upp det fria utrymmet i två sektioner med 16 celler (drag 5). (I det här exemplet är de fria sektionerna inte bara lika i area, utan sammanfaller också i form - de är symmetriska med avseende på brädets diagonal, men detta är naturligtvis inte nödvändigt för strategin.) Vidare, på draget av den andra spelaren (6) på en av dessa sektioner, svarar den första spelaren flytta på den andra (7) och vinner. Även om det fortfarande finns tre fria områden med fem eller fler celler på brädet, har alla lämpliga bitar (I, P, U) redan använts.
I denna variant av spelet turas spelarna först om att välja en pjäs i taget tills alla pjäser har fördelats mellan dem. Vidare fortsätter spelet enligt reglerna för den vanliga pentomino, med skillnaden att var och en av spelarna får flytta endast med de pjäser som han har valt. Den som tar den sista biten gör det första draget.
Strategin för denna variant av spelet som föreslagits av Golomb skiljer sig avsevärt från strategin för den vanliga pentomino. Istället för att dela upp brädet i lika stora sektioner, försöker spelaren skapa sektioner på brädet som bara kan fyllas med hans pjäser, men inte med motståndarens pjäser. (Golomb hänvisar till sådana områden som "flyktingar".)
Ett exempel på ett pentominospel med förvalda pjäser visas i figuren. De pjäser som valts av den första och andra spelaren är listade till vänster respektive höger om brädet. En överstruken bokstav anger att pjäsen har använts för ett drag. Först blir spelarna av med de mest "obekväma" bitarna X och W (drag 1 och 2). Sedan skapar den första spelaren ett "skydd" för Y-pjäsen (drag 3), den andra - för U- och P-pjäserna (drag 4 och 6). I slutet av spelet (drag 8-10) fylls dessa "skydd" och spelet slutar med segern för den andra spelaren - den första spelaren lämnas med en T-formad pentomino, för vilken det inte finns någon lämplig plats på resten av styrelsen.
Andra alternativSedan slutet av 1980-talet har olika pentomino-baserade datorspel släppts ett flertal gånger. Det mest kända är Pentix-spelet baserat på idén om Tetris . Ett av de senaste exemplen är spelet Dwice, som utvecklades 2006 av Tetris - uppfinnaren Aleksey Pajitnov .
Av alla pentominoer har R-pentomino den längsta utvecklingen. Utvecklingen av denna pentomino blir trivial först efter 1103 generationer [10] [11] . Efter 1103 generationer av R-pentamino-utveckling består befolkningen av 25 objekt: 8 block , 6 segelflygplan , 4 bikupor , 4 flashers , 1 båt, 1 limpa och 1 fartyg [10] [12] .
Den första av sex segelflygplan bildas efter 69 generationer av evolution. Den sågs 1970 av Richard Guy och var den första segelflygplan som registrerades [10] [11] [12] .
| Polyformer | |
|---|---|
| Typer av polyformer | |
| Polyomino efter antal celler | |
| Pussel med polykuber | |
| Staplingsuppgift |
|
| Personligheter |
|
| Relaterade ämnen | |
| Andra pussel och spel | |
| Tetris | |
|---|---|
| Main |
|
| Spelets ättlingar |
|
| Bärbara spel | |
| Spelalternativ |
|
