Pentomino (din altă greacă πέντα cinci și domino ) - poliomino cu cinci celule , adică figuri plate, fiecare dintre ele constând din cinci pătrate identice conectate prin laturi (" mișcarea turnului "). Același cuvânt este uneori numit puzzle, în care astfel de figuri trebuie să fie așezate într-un dreptunghi sau alte forme.
În total, există 12 figuri (elemente) diferite de pentominoe, notate cu litere latine, a căror formă seamănă cu [1] (vezi figura). Se crede că simetria în oglindă și simetria rotațională nu creează noi figuri. Dar dacă numărăm și cifrele în oglindă, atunci numărul lor va crește la 18. O astfel de diferență contează, de exemplu, într-un joc pe computer, variațiile „ Tetris ” - „ Pentix ”.
Dacă luăm în considerare rotația figurilor cu 90 °, atunci există următoarele categorii de simetrie:
Prin urmare, numărul de pentominoe fixe este 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.
De exemplu, iată opt moduri posibile de a orienta pentominourile L, F, P, N și Y:
Cea mai comună sarcină în pentomino este să pliați toate figurile, fără suprapuneri și goluri, într-un dreptunghi. Deoarece fiecare dintre cele 12 figuri include 5 pătrate, dreptunghiul trebuie să aibă o suprafață de 60 de unități de pătrate. Sunt posibile dreptunghiuri 6x10, 5x12, 4x15 și 3x20. Fiecare dintre aceste puzzle-uri poate fi rezolvată manual, dar sarcina mai dificilă este să se calculeze numărul total de soluții posibile în fiecare caz (în mod evident, dreptunghiurile de 2 × 30 și 1 × 60 nu pot fi făcute din pentominoe, deoarece multe dintre forme). pur și simplu nu se potrivesc în lățime).
Pentru cazul 6 × 10, această problemă a fost rezolvată pentru prima dată în 1965 de John Fletcher [2] . Există 2339 de aranjamente diferite de pentomino într-un dreptunghi de 6×10, fără a număra rotațiile și reflexiile întregului dreptunghi, ci numărând rotațiile și reflexiile părților sale (uneori în interiorul dreptunghiului se formează o combinație simetrică de forme, prin rotirea careia puteți obține soluții suplimentare; pentru un dreptunghi de 3×20 dat în figură, a doua soluție poate fi obținută prin rotirea unui bloc de 7 cifre, sau, cu alte cuvinte, prin schimbarea a patru cifre, extrema stângă și una extremă dreaptă ).
Pentru un dreptunghi de 5 × 12, există 1010 soluții, 4 × 15 - 368 soluții, 3 × 20 - doar 2 soluții (care diferă prin rotația descrisă mai sus). În special, există 16 moduri de a adăuga împreună două dreptunghiuri de 5×6, care pot face atât un dreptunghi de 6×10, cât și un dreptunghi de 5×12.
Stivuirea dreptunghiurilor din pentominouri unilateraleDacă completați setul de pentominoe cu copii în oglindă ale figurilor care nu coincid cu reflexiile lor (F, L, P, N, Y și Z), atunci dintr-un set complet de 18 pentominoe unilaterale, puteți adăuga dreptunghiuri cu o suprafață de 90 de pătrate unitare (în timp ce figurile nu pot fi răsturnate). Problema dreptunghiului 3×30 are 46 de soluții, 5×18 are peste 600.000 de soluții, 6×15 are mai mult de 2 milioane de soluții și 9×10 are mai mult de 10 milioane de soluții [3] .
Într-o oarecare măsură, o problemă mai simplă (mai simetrică), pentru un pătrat de 8×8 cu o gaură de 2×2 în centru, a fost rezolvată încă din 1958 de Dana Scott [4] (o studentă absolventă la matematică la Princeton). Există 65 de soluții pentru acest caz. Algoritmul lui Scott a fost una dintre cele mai timpurii aplicații ale unui program de calculator de backtracking .
O altă variantă a acestui puzzle este așezarea unui pătrat de 8×8 cu 4 găuri în locuri arbitrare. Majoritatea acestor probleme au o soluție. Excepțiile sunt atunci când plasați două perechi de găuri lângă două colțuri ale plăcii, astfel încât numai P-pentamino să poată fi plasat în fiecare colț, sau toate cele patru găuri lângă un colț, astfel încât pentru orice posibilă umplere a celulei de colț (folosind U- sau T-pentomino) încă o celulă este tăiată de pe tablă (vezi imaginea).
Pentru a rezolva aceste probleme, algoritmi eficienți au fost descriși, de exemplu, de Donald Knuth [5] [6] . Pe un computer modern, astfel de puzzle-uri pot fi rezolvate în câteva secunde.
Așezarea figurilor de animale, obiectelor și echipamentelorDin puzzle puteți așeza animale, păsări și pești, precum și plante, diverse obiecte și echipamente. În acest caz, sunt folosite atât toate cele 12 elemente pentomino, cât și o parte din ele.
Această problemă a fost propusă de profesorul R. M. Robinson de la Universitatea din California. După ce ai ales una dintre cele 12 figurine de pentomino, este necesar să construiești din oricare 9 din cele 11 pentominouri rămase o figură similară cu cea aleasă, dar de 3 ori mai lungă și mai largă. Există o soluție pentru oricare dintre cele 12 pentominoe, și nu singura (de la 15 soluții pentru X la 497 pentru P) [3] . Există o variantă a acestei probleme, în care este permisă utilizarea figurii originale în sine pentru a construi o figură triplă. În acest caz, numărul de soluții este de la 20 pentru X la 9144 pentru P-pentamino [7] .
Soluția prezentată în figura [8] , găsită de A. van de Wetering, are o proprietate interesantă: fiecare pentomino este folosit pentru a tripla nouă dintre celelalte, o dată în fiecare. Astfel, din 9 seturi de figuri pentomino inițiale, toate cele 12 pentominouri triplate pot fi adăugate simultan.
Pentomino poate fi folosit și ca joc de societate pentru doi jucători [9] . Pentru a juca, aveți nevoie de o tablă de șah de 8×8 și un set de piese pentomino, ale căror celule au aceeași dimensiune ca și celulele tablei. La începutul jocului, tabla este goală. Jucătorii plasează alternativ o piesă pe tablă, acoperind 5 celule libere ale tablei. Toate piesele expuse rămân pe loc până la sfârșitul jocului (nu sunt scoase de pe tablă și nu se mișcă). Pierzând este jucătorul care nu poate face o mișcare primul (fie pentru că niciuna dintre piesele rămase nu se potrivește pe zonele libere ale tablei, fie pentru că toate cele 12 piese au fost deja plasate pe tablă).
Analiza jocului este destul de complicată (de exemplu, la început există chiar mai multe prime mișcări posibile decât în șah). Golomb a sugerat următoarea strategie: încercați să împărțiți spațiul liber de pe tablă în două zone egale (și împiedicați adversarul să facă acest lucru). După aceea, mișcarea fiecărui adversar într-una dintre secțiuni ar trebui să primească răspuns cu o mutare în cealaltă.
Un exemplu de joc pentomino este prezentat în figură. Numerotarea mutărilor este de la capăt la capăt (numerele impare aparțin primului jucător, numerele pare aparțin celui de-al doilea). Inițial, jucătorii fac mișcări în centrul tablei (mușcări 1-3), împiedicându-se reciproc să împartă tabla în zone egale. Dar apoi al doilea jucător face o mișcare nereușită (4), permițând adversarului să împartă spațiul liber în două secțiuni de 16 celule (mușcarea 5). (În acest exemplu, secțiunile libere nu numai că sunt egale ca suprafață, ci coincid și ca formă - sunt simetrice față de diagonala plăcii, dar acest lucru, desigur, nu este necesar pentru strategie.) Mai mult, pe mutarea celui de-al doilea jucător (6) pe una dintre aceste secțiuni, primul jucător răspunde mișcare pe cealaltă (7) și câștigă. Deși există încă trei zone libere de cinci sau mai multe celule pe tablă, toate piesele potrivite (I, P, U) au fost deja folosite.
În această variantă a jocului, jucătorii aleg pe rând câte o piesă până când toate piesele au fost distribuite între ei. În plus, jocul se desfășoară conform regulilor pentomino-ului obișnuit, cu diferența că fiecare dintre jucători are voie să se miște doar cu piesele pe care le-a ales. Cel care ia ultima piesă face prima mișcare.
Strategia acestei variante a jocului propusă de Golomb diferă semnificativ de strategia pentomino-ului obișnuit. În loc să împartă tabla în secțiuni de dimensiuni egale, jucătorul caută să creeze secțiuni pe tablă care să poată fi umplute doar cu piesele sale, dar nu și cu piesele adversarului. (Golomb se referă la astfel de zone ca „refugiați”.)
Un exemplu de joc pentomino cu piese preselectate este prezentat în figură. Piesele alese de primul și de al doilea jucător sunt listate în stânga și, respectiv, în dreapta tablei. O literă tăiată indică faptul că piesa a fost folosită pentru o mișcare. În primul rând, jucătorii scapă de cele mai „incomode” piese X și W (mutările 1 și 2). Apoi, primul jucător creează un „adăpost” pentru piesa Y (mușările 3), al doilea - pentru piesele U și P (mutările 4 și 6). La sfârșitul jocului (mutările 8-10), aceste „adăposturi” sunt umplute și jocul se termină cu victoria celui de-al doilea jucător - primul jucător rămâne cu un pentomino în formă de T, pentru care nu există un loc potrivit. pe restul tablei.
Alte opțiuniDe la sfârșitul anilor 1980, diferite jocuri pe computer pe bază de pentomino au fost lansate de mai multe ori. Cel mai faimos este jocul Pentix bazat pe ideea de Tetris . Unul dintre cele mai noi exemple este jocul Dwice, care a fost dezvoltat în 2006 de inventatorul Tetris Aleksey Pajitnov .
Dintre toate pentomino-urile, R-pentomino are cea mai lungă evoluție. Evoluția acestui pentomino devine banală abia după 1103 generații [10] [11] . După 1103 generații de dezvoltare R-pentamino, populația este formată din 25 de obiecte: 8 blocuri , 6 planoare , 4 stupi , 4 fulgerătoare , 1 barcă, 1 pâine și 1 navă [10] [12] .
Primul dintre cele șase planoare este format după 69 de generații de evoluție. A fost văzut în 1970 de Richard Guy și a fost primul planor care a fost înregistrat [10] [11] [12] .
| Poliforme | |
|---|---|
| Tipuri de poliforme | |
| Poliomino după numărul de celule | |
| Puzzle-uri cu policuburi | |
| Sarcina de stivuire |
|
| Personalități |
|
| subiecte asemănătoare | |
| Alte puzzle-uri și jocuri | |
| Tetris | |
|---|---|
| Principal |
|
| Descendenții jocului |
|
| Jocuri portabile |
|
| Opțiuni de joc |
|
