Pentomino (fra andre græske πέντα fem og dominoer ) - femcellede polyominoer , det vil sige flade figurer, som hver består af fem identiske firkanter forbundet med siderne (" tårnets træk "). Det samme ord kaldes nogle gange et puslespil, hvor sådanne figurer skal lægges i et rektangel eller andre former.
I alt er der 12 forskellige figurer (elementer) af pentominoer, betegnet med latinske bogstaver, hvis form de ligner [1] (se figur). Det menes, at spejlsymmetri og rotationssymmetri ikke skaber nye figurer. Men hvis vi også tæller de spejlede figurer, vil deres antal stige til 18. En sådan forskel har betydning, for eksempel i et computerspil, variationer af " Tetris " - " Pentix ".
Hvis vi betragter rotationen af figurer med 90 °, så er der følgende kategorier af symmetri:
Derfor er antallet af faste pentominoer 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.
For eksempel er her otte mulige måder at orientere pentominoer L, F, P, N og Y på:
Den mest almindelige opgave i pentomino er at folde alle figurerne, uden overlapninger og mellemrum, til et rektangel. Da hver af de 12 figurer omfatter 5 kvadrater, skal rektanglet have et areal på 60 enhedskvadrater. Rektangler 6x10, 5x12, 4x15 og 3x20 er mulige. Hver af disse gåder kan løses i hånden, men den sværeste opgave er at beregne det samlede antal mulige løsninger i hvert tilfælde (naturligvis kan 2 × 30 og 1 × 60 rektangler ikke laves af pentominoer, da mange af formerne passer simpelthen ikke i bredden).
For 6 × 10 tilfældet blev dette problem først løst i 1965 af John Fletcher [2] . Der er 2339 forskellige arrangementer af pentominoer i et 6×10 rektangel, der ikke tæller rotationerne og refleksionerne af hele rektanglet, men tæller rotationerne og refleksionerne af dets dele (nogle gange dannes en symmetrisk kombination af former inde i rektanglet, ved at rotere som du kan få yderligere løsninger; for et 3×20 rektangel angivet i figuren, kan den anden løsning opnås ved at rotere en blok med 7 figurer, eller, med andre ord, ved at bytte fire figurer, den yderste venstre og en yderst til højre ).
For et 5 × 12 rektangel er der 1010 løsninger, 4 × 15 - 368 løsninger, 3 × 20 - kun 2 løsninger (som adskiller sig i rotationen beskrevet ovenfor). Der er især 16 måder at lægge to 5×6 rektangler sammen på, hvilket kan lave både et 6×10 rektangel og et 5×12 rektangel.
Stabling af rektangler fra ensidede pentominoerHvis du supplerer sættet af pentominoer med spejlkopier af figurer, der ikke falder sammen med deres refleksioner (F, L, P, N, Y og Z), så kan du fra et komplet sæt af 18 ensidede pentominoer tilføje rektangler med et areal på 90 enhedskvadrater (mens figurerne ikke må vendes). 3×30 rektangelproblemet har 46 løsninger, 5×18 har over 600.000 løsninger, 6×15 har mere end 2 millioner løsninger, og 9×10 har mere end 10 millioner løsninger [3] .
Til en vis grad blev et enklere (mere symmetrisk) problem, for en 8×8 kvadrat med et 2×2 hul i midten, løst tilbage i 1958 af Dana Scott [4] (en kandidatstuderende i matematik ved Princeton). Der er 65 løsninger til denne sag. Scotts algoritme var en af de tidligste anvendelser af et backtracking -computerprogram .
En anden variant af dette puslespil er at lægge en 8×8 firkant med 4 huller på vilkårlige steder. De fleste af disse problemer har en løsning. Undtagelserne er, når man placerer to par huller i nærheden af to hjørner af brættet, således at kun P-pentamino kan placeres i hvert hjørne, eller alle fire huller nær det ene hjørne, således at der for eventuel udfyldning af hjørnecellen (ved hjælp af U- eller T- pentomino) skæres en celle mere af fra brættet (se billede).
For at løse disse problemer blev effektive algoritmer beskrevet af for eksempel Donald Knuth [5] [6] . På en moderne computer kan sådanne gåder løses på få sekunder.
Lægning af dyrefigurer, genstande og udstyrFra puslespillet kan du lægge dyr, fugle og fisk ud, samt planter, forskellige genstande og udstyr. I dette tilfælde bruges både alle 12 pentomino-elementer og en del af dem.
Dette problem blev foreslået af professor R. M. Robinson fra University of California. Efter at have valgt en af de 12 pentomino-figurer, er det nødvendigt at bygge en figur ud fra en hvilken som helst 9 af de 11 resterende pentominoer en figur, der ligner den valgte, men 3 gange længere og bredere. Der findes en løsning for enhver af de 12 pentominoer, og ikke den eneste (fra 15 løsninger for X til 497 for P) [3] . Der er en variant af dette problem, hvor det er tilladt at bruge selve originalfiguren til at konstruere en tredoblet figur. I dette tilfælde er antallet af opløsninger fra 20 for X til 9144 for P-pentamino [7] .
Løsningen vist i figuren [8] , fundet af A. van de Wetering, har en interessant egenskab: hver pentomino bruges til at tredoble ni af de andre, én gang i hver. Fra 9 sæt indledende pentomino-figurer kan alle 12 tredobbelte pentominoer tilføjes samtidigt.
Pentomino kan også bruges som et brætspil for to spillere [9] . For at spille skal du bruge et 8×8 skakbræt og et sæt pentominobrikker, hvis celler har samme størrelse som brættets celler. I starten af spillet er brættet tomt. Spillere placerer skiftevis en brik på brættet, der dækker 5 frie celler på brættet. Alle synlige brikker forbliver på plads indtil slutningen af spillet (de fjernes ikke fra brættet og bevæger sig ikke). Taberen er den spiller, der ikke kan lave et træk først (enten fordi ingen af de resterende brikker passer på de frie områder af brættet, eller fordi alle 12 brikker allerede er placeret på brættet).
Analysen af spillet er ret kompliceret (for eksempel er der i begyndelsen endnu flere mulige første træk end i skak). Golomb foreslog følgende strategi: prøv at dele den frie plads på brættet i to lige store områder (og forhindre modstanderen i at gøre dette). Derefter skal hver modstanders træk i en af sektionerne besvares med et træk i den anden.
Et eksempel på et pentominospil er vist på figuren. Nummereringen af træk er ende-til-ende (ulige antal træk tilhører den første spiller, lige tal tilhører den anden). Indledningsvis foretager spillerne træk i midten af brættet (træk 1-3), hvilket forhindrer hinanden i at dele brættet op i lige store områder. Men så foretager den anden spiller et mislykket træk (4), hvilket giver modstanderen mulighed for at opdele det frie rum i to sektioner af 16 celler (træk 5). (I dette eksempel er de frie sektioner ikke kun lige store i areal, men falder også sammen i form - de er symmetriske i forhold til brættets diagonal, men dette er naturligvis ikke nødvendigt for strategien.) Yderligere, på træk af den anden spiller (6) på en af disse sektioner, den første spiller svarer træk på den anden (7) og vinder. Selvom der stadig er tre frie områder med fem eller flere celler på brættet, er alle de passende brikker (I, P, U) allerede blevet brugt.
I denne variant af spillet skiftes spillerne først til at vælge én brik ad gangen, indtil alle brikkerne er blevet fordelt mellem dem. Yderligere fortsætter spillet i henhold til reglerne for den sædvanlige pentomino, med den forskel, at hver af spillerne kun må bevæge sig med de brikker, han har valgt. Den, der tager den sidste brik, tager det første træk.
Strategien for denne variant af spillet foreslået af Golomb adskiller sig væsentligt fra strategien for den sædvanlige pentomino. I stedet for at opdele brættet i lige store sektioner søger spilleren at skabe sektioner på brættet, der kun kan fyldes med hans brikker, men ikke med modstanderens brikker. (Golomb omtaler sådanne områder som "flygtninge".)
Et eksempel på et pentominospil med forudvalgte brikker er vist på figuren. De brikker, der er valgt af den første og anden spiller, er angivet til henholdsvis venstre og højre på brættet. Et overstreget bogstav angiver, at brikken er blevet brugt til et træk. Først slipper spillerne af med de mest "ubehagelige" brikker X og W (træk 1 og 2). Derefter skaber den første spiller et "ly" for Y-brikken (træk 3), den anden - for U- og P-brikkerne (træk 4 og 6). I slutningen af spillet (træk 8-10) fyldes disse "shelters" og spillet slutter med den anden spillers sejr - den første spiller står tilbage med en T-formet pentomino, som der ikke er nogen passende plads til på resten af bestyrelsen.
Andre mulighederSiden slutningen af 1980'erne er forskellige pentomino-baserede computerspil blevet udgivet adskillige gange. Det mest berømte er Pentix-spillet baseret på ideen om Tetris . Et af de nyeste eksempler er spillet Dwice, som blev udviklet i 2006 af Tetris - opfinderen Aleksey Pajitnov .
Af alle pentominoer har R-pentomino den længste udvikling. Udviklingen af denne pentomino bliver triviel først efter 1103 generationer [10] [11] . Efter 1103 generationer af R-pentamino-udvikling består befolkningen af 25 objekter: 8 blokke , 6 svævefly , 4 bistader , 4 blinker , 1 båd, 1 brød og 1 skib [10] [12] .
Det første af seks svævefly er dannet efter 69 generationers evolution. Det blev set i 1970 af Richard Guy og var det første svævefly, der blev optaget [10] [11] [12] .
| Polyformer | |
|---|---|
| Typer af polyformer | |
| Polyomino efter antal celler | |
| Puslespil med polykuber | |
| Stable opgave |
|
| Personligheder |
|
| relaterede emner | |
| Andre puslespil og spil | |
| Tetris | |
|---|---|
| Hoved |
|
| Efterkommere af spillet |
|
| Bærbare spil |
|
| Spilmuligheder |
|
