Pentamino
Un pentamino (din grecescul πέντε , cinci ) este un polimino compus din cinci pătrate identice, conectate între ele de-a lungul laturilor.
Există douăsprezece pentominoe diferite, numite în mod convențional cu literele alfabetului cu care se aseamănă. De obicei, doi pentominoi obținuți unul de la altul cu izometrie sunt considerați la fel.
Pentominoii F, L, N, P, Y și Z sunt chirali în două dimensiuni; dacă luăm în considerare și simetricele lor (F ', J, N', Q, Y ', S), numărul total de pentominoi ajunge la 18. Pentru fiecare dintre celelalte (I, T, U, V, W și X) acolo există în schimb o rotație care o face să se potrivească cu imaginea reflectată. Acest lucru capătă o anumită importanță în anumite jocuri în care este posibil să se rotească, dar să nu se răstoarne piesele, cum ar fi unele derivate ale Tetris sau Rampart .
Cu fiecare dintre cele 12 pentominoe puteți face o teselare a vârfului . În special, este posibil să se realizeze teselări ale planului pornind de la orice pentomino chiral chiar și fără a-l utiliza pe cel simetric.
John Horton Conway a folosit o convenție de denumire diferită pentru pentominoe: O în loc de I, Q în loc de L, R în loc de F și S în loc de N. Asemănarea cu literele este mult mai vagă, dar acest model are avantajul de a utiliza 12 consecutive. literele alfabetului. Când ne referim la jocul vieții , este, prin urmare, obișnuit să vorbim despre pentamino-R în loc de pentamino-F .
Dacă luăm în considerare numai rotațiile unghiurilor multiple de 90 de grade, putem recunoaște următoarele categorii de simetrie :
- L, N, P, F și Y pot fi orientate în 8 moduri: 4 prin rotație și alte 4 prin adăugarea unei simetrii
- Z poate fi orientat în 4 moduri: 2 prin rotație și alte 2 prin adăugarea unei simetrii
- T, V, U și W pot fi orientate în 4 moduri prin rotație
- Pot fi orientat în 2 moduri prin rotație
- X poate fi orientat doar într-un fel
În general, în contextul figurilor plane există o categorie suplimentară: cea a figurilor orientabile în 2 moduri, oglindindu-se reciproc (un exemplu este dat de zvastică ); nu există pentomino în această categorie și s-a verificat că nu este posibil să se găsească acest tip de simetrie în poliominoii cu mai puțin de 8 pătrate.
De exemplu, raportăm cele opt orientări posibile ale pentamino Y:
Teselarea dreptunghiurilor
Un exemplu tipic de joc pentomino este umplerea (fără suprapuneri sau găuri goale) a unei cutii dreptunghiulare cu un set complet. Acest dreptunghi trebuie să conțină în mod evident pătrate. Prin urmare, dreptunghiurile posibile sunt cele cu dimensiunile 6 × 10, 5 × 12, 4 × 15 și 3 × 20. O soluție pentru fiecare dintre aceste cazuri poate fi găsită manual în câteva ore. O problemă mai dificilă și care nu poate fi rezolvată fără sprijinul unui computer este totuși câte soluții există pentru fiecare alegere a dreptunghiului.
Cazul 6 × 10 a fost rezolvat pentru prima dată de CB Haselgrove și Jenifer Haselgrove în 1960. [1] Soluțiile sunt exact 2339, dacă nu luăm în considerare variațiile banale care constau în rotirea sau reflectarea întregului dreptunghi, ci în schimb permit rotirea un subset al pentominoilor (acest lucru este uneori posibil și este o modalitate ușoară de a găsi o nouă soluție; de exemplu, pornind de la soluția raportată a dreptunghiului 3 × 20, este posibil să se obțină altul pur și simplu prin rotirea unui bloc de șapte pentominoe sau, cu alte cuvinte, prin rotirea celor 4 pentominoe din stânga și schimbarea acestora cu cel din dreapta).
Există 1010 soluții pentru dreptunghiul 5 × 12, 368 pentru cel 4 × 15 și doar 2 pentru cel 3 × 20.
Un puzzle mai simplu (pentru că mai simetric), pătratul de 8 × 8 cu o gaură de 2 × 2 în mijloc, a fost rezolvat de Dana Scott încă din 1958 [2] : există 65 de soluții. Algoritmul cu care Scott a obținut acest rezultat a fost una dintre primele aplicații informatice de backtracking . Alte variante ale puzzle-ului vă permit să schimbați poziția celor patru pătrate lipsă. Multe dintre aceste configurații sunt rezolvabile; excepțiile sunt cele în care sunt plasate găurile:
- în perechi în corespondența a două colțuri și în așa fel încât în ambele să fie necesară utilizarea unui pentomino P
- în vecinătatea unui colț în așa fel încât doar un pentomino T sau U să poată fi plasat acolo, dar creând o gaură nouă.
S-au găsit algoritmi eficienți pentru a rezolva aceste probleme, de exemplu de Donald Knuth [3] . Pe un computer modern, aceste puzzle-uri pot fi rezolvate acum în câteva secunde.
Umplerea cutiilor
Un pentacub este un policub format din cinci cuburi. Doisprezece din cele 29 de pentacuburi corespund celor 12 pentominoe, în sensul că acestea sunt proiecția pe plan. Există puzzle-uri bazate pe umplerea unei cutii tridimensionale cu aceste pentacube plate. Fiecare dintre cele 12 pentacuburi este alcătuit din 5 cuburi, deci, evident, cutia trebuie să conțină 60 de cuburi; dimensiunile posibile sunt 2 × 3 × 10, 2 × 5 × 6 și 4 × 3 × 5; Iată câteva soluții.
Caseta 2 x 3 x 10
Caseta 5 x 2 x 6
Caseta 4 x 3 x 5
Dacă luăm în considerare și pentacuburile neplate (și, prin urmare, adăugăm la cele 12 doar considerate 6 perechi de pentacuburi chirale și 5 pentacuburi necirale), obținem un total de 29 de bucăți, sau 145 de cuburi; cu toate acestea, nu există nicio cutie paralelipipedică care să conțină un astfel de număr de cuburi.
Jocul de societate
Există un joc de societate bazat pe pentominoe și numit pentominoe .
Terenul de joc este o tablă de șah pe care se confruntă doi sau trei jucători, adăugând la rândul lor un pentomino; câștigă ultimul jucător care reușește să aranjeze o piesă în așa fel încât să nu se suprapună cu cele anterioare.
În versiunea cu doi jucători, primul jucător a demonstrat că are o tactică câștigătoare.
Pentominoe, precum și alte forme similare, stau la baza multor alte jocuri și puzzle-uri. De exemplu, un joc de masă francez numit Blokus este jucat cu 4 adversari, fiecare cu un set de pentominoe (12), unul de tetrominoi (5), unul de triomine (2) și unul de domenii (1) de o anumită culoare. Din nou, obiectul jocului este să îți poți aranja toate piesele, încercând să lași domino-ul pentru final.
Frații Parker au produs un joc de societate numit Univers în 1966, bazat pe pentominoe, din decorul bazat pe filmul 2001: O odisee spațială : astronautul joacă un joc de pentomino împotriva computerului (cel care în film este un joc de șah ). Coperta jocului prezintă scene din film, precum și o legendă care îl descrie ca „jocul viitorului”. Jocul conține 4 seturi complete de pentominoe și o zonă de joacă formată dintr-o bază plus 25 de pătrate suplimentare de adăugat pentru încă doi jucători.
Jocuri video
- Tetris a fost inspirat de puzzle-uri pentomino, deși cărămizile sale sunt tetrominoe.
- Jocul Daedalian Opus conține diverse puzzle-uri pentomino .
- Yohoho! Puzzle Pirates conține un mini-joc ( Carpentry ) format dintr-un puzzle cu pentominoe.
Notă
- ^ CB Haselgrove, Jenifer Haselgrove, A Computer Program for Pentominoes , în Eureka , vol. 23, octombrie 1960, pp. 16-18.
- ^ Dana S. Scott (1958). "Programarea unui puzzle combinator". Raport tehnic nr. 1, Departamentul de Inginerie Electrică, Universitatea Princeton.
- ^ Donald E. Knuth. „Linkuri de dans” (Postscript, 1,6 megabyți). Include un rezumat al articolelor lui Scott și Fletcher.
Elemente conexe
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere despre Pentamino
linkuri externe
- ( EN ) Chasing Vermeer , cu informații despre cartea „Chasing Vermeer” și o tablă de joc interactivă pentru pentominoe.
- (EN) Pentominoes: Un prim jucător câștigat , de HILARIE K. ORMAN
- (EN) „Pentamino for Pocket PC” este o implementare GPL a puzzle-ului cu configurații distractive, în plus față de „casetele” normale.
- (EN) Pentas , un mic teaser (cu resolver).
- ( EN ) Pentas , Pzntamino
- Inspirat de jocurile online Pentomino. Trageți, rotiți și întoarceți țiglele pentomino pentru a pune împreună imagini sau rezolva puzzle-uri numerice, jucați Tetromino sau găsiți o soluție Peg Solitaire. , pe pentomino-puzzles.com . Adus la 30 aprilie 2019 (arhivat din original la 5 martie 2016) .
