Pentomino ( muista kreikkalaisista sanoista πέντα viisi ja domino ) - viisisoluiset polyominot , eli litteät hahmot, joista jokainen koostuu viidestä identtisestä neliöstä, jotka on yhdistetty sivuilla (" tornin siirto "). Samaa sanaa kutsutaan joskus palapeliksi, jossa tällaiset hahmot on asetettava suorakulmioon tai muihin muotoihin.
Yhteensä pentominoja on 12 erilaista hahmoa (elementtiä), jotka on merkitty latinalaisin kirjaimin ja jotka muistuttavat muodoltaan [1] (katso kuva). Uskotaan, että peilisymmetria ja kiertosymmetria eivät luo uusia hahmoja. Mutta jos laskemme myös peilatut luvut, niin niiden määrä kasvaa 18:aan. Tällä erolla on merkitystä esimerkiksi tietokonepelissä " Tetris " - " Pentix " muunnelmissa.
Jos tarkastelemme kuvien kiertoa 90 °, on olemassa seuraavat symmetrialuokat:
Tästä syystä kiinteiden pentominojen määrä on 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.
Tässä on esimerkiksi kahdeksan mahdollista tapaa suunnata pentominoja L, F, P, N ja Y:
Yleisin tehtävä pentominossa on taittaa kaikki hahmot ilman päällekkäisyyksiä ja aukkoja suorakulmioksi. Koska jokainen 12 hahmosta sisältää 5 ruutua, suorakulmion pinta-alan on oltava 60 neliöyksikköä. Suorakulmiot 6x10, 5x12, 4x15 ja 3x20 ovat mahdollisia. Jokainen näistä arvoimista voidaan ratkaista käsin, mutta vaikeampi tehtävä on laskea mahdollisten ratkaisujen kokonaismäärä kussakin tapauksessa (ilmeisesti 2 × 30 ja 1 × 60 suorakulmiota ei voida tehdä pentominoista, koska monet muodot eivät yksinkertaisesti sovi leveyteen).
6 × 10 -tapauksessa tämän ongelman ratkaisi ensimmäisen kerran vuonna 1965 John Fletcher [2] . 6×10 suorakulmiossa on 2339 erilaista pentomino-asettelua, kun ei lasketa koko suorakulmion kierroksia ja heijastuksia, vaan lasketaan sen osien kierrokset ja heijastukset (joskus suorakulmion sisään muodostuu symmetrinen muotoyhdistelmä, jota kiertämällä voit saada lisäratkaisuja; kuvassa annetulle 3×20 suorakulmiolle toinen ratkaisu saadaan kiertämällä 7 hahmon lohkoa tai toisin sanoen vaihtamalla neljä hahmoa, äärivasen ja yksi äärioikea ).
5 × 12 suorakulmiossa on 1010 ratkaisua, 4 × 15 - 368 ratkaisua, 3 × 20 - vain 2 ratkaisua (jotka eroavat edellä kuvatun kierron suhteen). Erityisesti on olemassa 16 tapaa lisätä kaksi 5 × 6 suorakulmiota yhteen, mikä voi tehdä sekä 6 × 10 suorakulmion että 5 × 12 suorakulmion.
Suorakulmioiden pinoaminen yksipuolisista pentominoistaJos täydennät pentominosarjaa peilikopioilla hahmoista, jotka eivät ole yhtäpitäviä niiden heijastusten kanssa (F, L, P, N, Y ja Z), niin täydellisestä 18 yksipuolisen pentominon sarjasta voit lisätä suorakulmioita 90 yksikköneliön pinta-ala (kun taas kuvioita ei saa kääntää) 3×30 suorakaidetehtävässä on 46 ratkaisua, 5×18:ssa yli 600 000 ratkaisua, 6×15:ssä yli 2 miljoonaa ratkaisua ja 9×10:ssä yli 10 miljoonaa ratkaisua [3] .
Dana Scott [4] (matematiikan jatko-opiskelija Princetonissa) ratkaisi jossain määrin yksinkertaisemman (symmetrisemmän) ongelman 8×8 neliölle, jonka keskellä on 2×2 reikä . Tähän tapaukseen on 65 ratkaisua. Scottin algoritmi oli yksi varhaisimmista backtracking -tietokoneohjelman sovelluksista .
Toinen tämän palapelin muunnos on asettaa 8 × 8 neliö, jossa on 4 reikää mielivaltaisiin paikkoihin. Suurimpaan osaan näistä ongelmista on ratkaisu. Poikkeuksena ovat kaksi paria reikiä laudan kahden kulman lähelle siten, että jokaiseen kulmaan voidaan sijoittaa vain P-pentamino, tai kaikki neljä reikää yhden kulman lähelle niin, että kulmakennon mahdollinen täyttö (käyttämällä U- tai T-pentomino) taulusta leikataan vielä yksi solu (katso kuva).
Näiden ongelmien ratkaisemiseksi tehokkaita algoritmeja kuvaili esimerkiksi Donald Knuth [5] [6] . Nykyaikaisessa tietokoneessa tällaiset palapelit voidaan ratkaista muutamassa sekunnissa.
Eläinhahmojen, esineiden ja laitteiden muniminenPalapelistä voit asettaa eläimiä, lintuja ja kaloja sekä kasveja, erilaisia esineitä ja laitteita. Tässä tapauksessa käytetään sekä kaikkia 12 pentominoelementtiä että osaa niistä.
Tämän ongelman ehdotti professori R. M. Robinson Kalifornian yliopistosta. Kun olet valinnut yhden 12 pentominohahmosta, on tarpeen rakentaa mistä tahansa 9:stä jäljellä olevista 11 pentominosta samanlainen hahmo kuin valittu, mutta 3 kertaa pidempi ja leveämpi. Ratkaisu on olemassa mille tahansa 12 pentominosta, eikä ainoa (15 ratkaisusta X: lle 497 P: lle) [3] . Tästä tehtävästä on olemassa muunnos, jossa on sallittua käyttää itse alkuperäistä kuviota kolminkertaisen hahmon rakentamiseen. Tässä tapauksessa liuosten lukumäärä on 20 X:n kohdalla 9144 P-pentaminolle [7] .
Kuvassa [8] esitetyllä ratkaisulla , jonka on löytänyt A. van de Wetering, on mielenkiintoinen ominaisuus: jokaista pentominoa käytetään kolminkertaistamaan yhdeksän muuta, kerran kussakin. Siten yhdeksästä alkuperäisen pentominofiguurisarjasta kaikki 12 kolminkertaista pentominoa voidaan lisätä samanaikaisesti.
Pentominoa voidaan käyttää myös kahden pelaajan lautapelinä [9] . Pelataksesi tarvitset 8×8 shakkilaudan ja sarjan pentominonappuloita, joiden solut ovat samankokoisia kuin laudan solut. Pelin alussa lauta on tyhjä. Pelaajat asettavat vuorotellen yhden nappulan laudalle peittäen 5 vapaata laudan solua. Kaikki esillä olevat nappulat pysyvät paikoillaan pelin loppuun asti (ne eivät poistu laudalta eivätkä liiku). Häviäjä on pelaaja, joka ei voi tehdä siirtoa ensin (joko koska mikään jäljellä olevista nappuloista ei mahdu laudan vapaille alueille tai koska kaikki 12 nappulaa on jo asetettu laudalle).
Pelin analyysi on melko monimutkaista (esim. alussa mahdollisia ensisiirtoja on jopa enemmän kuin shakissa). Golomb ehdotti seuraavaa strategiaa: yritä jakaa laudalla oleva vapaa tila kahteen yhtä suureen alueeseen (ja estää vastustajaa tekemästä tätä). Tämän jälkeen jokaisen vastustajan siirtoon yhdessä osiossa tulee vastata siirrolla toisessa.
Esimerkki pentominopelistä on esitetty kuvassa. Liikkeiden numerointi on päästä päähän (parittomat siirrot kuuluvat ensimmäiselle pelaajalle, parilliset numerot toiselle). Aluksi pelaajat tekevät liikkeitä laudan keskelle (siirrot 1-3), estäen toisiaan jakamasta lautaa yhtä suuriin alueisiin. Mutta sitten toinen pelaaja tekee epäonnistuneen liikkeen (4), jolloin vastustaja voi jakaa vapaan tilan kahteen 16 solun osaan (siirto 5). (Tässä esimerkissä vapaat osat eivät ole vain pinta-alaltaan samanlaisia, vaan myös muodoltaan yhteneväisiä - ne ovat symmetrisiä laudan diagonaaliin nähden, mutta tämä ei tietenkään ole strategian kannalta välttämätöntä.) toisen pelaajan (6) siirto yhdellä näistä osista, ensimmäinen pelaaja vastaa liikkua toisella (7) ja voittaa. Vaikka laudalla on vielä kolme vapaata viiden tai useamman solun aluetta, kaikki sopivat nappulat (I, P, U) on jo käytetty.
Tässä peliversiossa pelaajat valitsevat ensin vuorotellen yhden nappulan kerrallaan, kunnes kaikki nappulat on jaettu heidän kesken. Lisäksi peli etenee tavallisen pentominon sääntöjen mukaan sillä erolla, että jokainen pelaaja saa liikkua vain valitsemillaan nappuloilla. Se, joka ottaa viimeisen palan, tekee ensimmäisen liikkeen.
Tämän Golombin ehdottaman peliversion strategia eroaa merkittävästi tavallisen pentominon strategiasta. Sen sijaan, että pelaaja jakaisi laudan samankokoisiin osiin, pelaaja pyrkii luomaan laudalle osia, jotka voidaan täyttää vain hänen nappuloillaan, mutta ei vastustajan nappuloilla. (Golomb viittaa sellaisiin alueisiin "pakolaisiksi".)
Kuvassa on esimerkki pentominopelistä, jossa on esivalittuja nappuloita. Ensimmäisen ja toisen pelaajan valitsemat nappulat on listattu laudan vasemmalla ja oikealla puolella. Yliviivattu kirjain osoittaa, että nappulaa on käytetty siirtoon. Ensin pelaajat pääsevät eroon "epämukavimmista" nappuloista X ja W (siirrot 1 ja 2). Sitten ensimmäinen pelaaja luo "suojan" Y-nappulle (siirrot 3), toinen - U- ja P-nappulaille (siirrot 4 ja 6). Pelin lopussa (siirrot 8-10) nämä "suojat" täyttyvät ja peli päättyy toisen pelaajan voittoon - ensimmäiselle pelaajalle jää T-muotoinen pentomino, jolle ei ole sopivaa paikkaa. muualla laudalla.
Muut vaihtoehdot1980-luvun lopulta lähtien erilaisia pentomino-pohjaisia tietokonepelejä on julkaistu useita kertoja. Tunnetuin on Tetris -ideaan perustuva Pentix-peli . Yksi uusimmista esimerkeistä on peli Dwice, jonka Tetrisin keksijä Aleksey Pajitnov kehitti vuonna 2006 .
Kaikista pentominoista R-pentominolla on pisin kehitys. Tämän pentominon evoluutio muuttuu triviaaliksi vasta 1103 sukupolven jälkeen [10] [11] . 1103 sukupolven R-pentaminokehityksen jälkeen populaatio koostuu 25 esineestä: 8 lohkosta , 6 purjelentokoneesta , 4 mehiläispesästä , 4 vilkkusta , 1 veneestä, 1 leivästä ja 1 laivasta [10] [12] .
Ensimmäinen kuudesta purjelentokoneesta muodostuu 69 sukupolven evoluution jälkeen. Richard Guy näki sen vuonna 1970, ja se oli ensimmäinen äänitetty purjelentokone [10] [11] [12] .
| Polyformit | |
|---|---|
| Polyformien tyypit | |
| Polyomino solujen lukumäärän mukaan | |
| Palapelit polycubeilla | |
| Pinoamistehtävä |
|
| Persoonallisuudet |
|
| liittyvät aiheet | |
| Muita pulmia ja pelejä | |
| Tetris | |
|---|---|
| Main |
|
| Pelin jälkeläisiä |
|
| Kannettavat pelit |
|
| Pelivaihtoehdot |
|
