Pentamino

Un pentamino (dal greco πέντε, cinque) è un polimino composto di cinque quadrati identici, connessi tra di loro lungo dei lati.

Esistono dodici diversi pentamini, convenzionalmente chiamati con le lettere dell'alfabeto a cui assomigliano. Di solito, due pentamini ottenibili l'uno dall'altro con un'isometria si considerano lo stesso.

I pentamini F, L, N, P, Y e Z sono chirali in due dimensioni; se consideriamo anche i loro simmetrici (F', J, N', Q, Y', S), il numero totale di pentamini arriva a 18. Per ognuno degli altri (I, T, U, V, W e X) esiste invece una rotazione che lo fa combaciare con la sua immagine riflessa. Questo assume una certa importanza in certi giochi in cui è possibile ruotare ma non ribaltare i pezzi, come alcuni derivati di Tetris o Rampart.

Con ognuno dei 12 pentamini si può realizzare una tassellazione del piano. In particolare, si può realizzare tassellazioni del piano a partire da un qualsiasi pentamino chirale anche senza utilizzare il suo simmetrico.

John Horton Conway ha utilizzato una diversa convenzione per attribuire i nomi ai pentamini: O invece di I, Q invece di L, R invece di F e S invece di N. La somiglianza con le lettere è molto più vaga, ma questo schema ha il vantaggio di utilizzare 12 lettere consecutive dell'alfabeto. Quando ci si riferisce al gioco della vita, si è soliti quindi parlare di pentamino-R invece che pentamino-F.

Se consideriamo solo le rotazioni di angoli multipli di 90 gradi, possiamo riconoscere le seguenti categorie di simmetria:

L, N, P, F e Y si possono orientare in 8 modi: 4 tramite rotazione ed altri 4 aggiungendo una simmetria
Z si può orientare in 4 modi: 2 tramite rotazione ed altri 2 aggiungendo una simmetria
T, V, U e W si possono orientare in 4 modi tramite rotazione
I si può orientare in 2 modi tramite rotazione
X si può orientare in un solo modo

In generale, nell'ambito delle figure piane esiste un'ulteriore categoria: quella delle figure orientabili in 2 modi, tra di loro speculari (un esempio è dato dalla svastica); non esiste nessun pentamino in questa categoria, ed è stato verificato che non è possibile riscontrare tale tipo di simmetria in polimini con meno di 8 quadrati.

Come esempio, riportiamo le otto possibili orientazioni del pentamino Y:

Tassellazione di rettangoli

[modifica | modifica wikitesto]

Un tipico esempio di gioco con i pentamini è il riempimento (senza sovrapposizioni né buchi vuoti) di una scatola rettangolare con un set completo. Tale rettangolo deve ovviamente contenere $12\times 5=60$ quadratini. I possibili rettangoli sono quindi quelli di dimensioni 6×10, 5×12, 4×15 e 3×20. Si può trovare a mano una soluzione per ognuno di questi casi probabilmente in un paio d'ore. Un problema più impegnativo, e non affrontabile senza il supporto di un computer, è però quante soluzioni esistono per ogni scelta del rettangolo.

Il caso 6×10 fu risolto per primo da C. B. Haselgrove e Jenifer Haselgrove nel 1960.^[1] Le soluzioni sono esattamente 2339, se non consideriamo le variazioni banali che consistono nel ruotare o riflettere l'intero rettangolo, ma permettiamo invece la rotazione di un sottoinsieme dei pentamini (ciò è talvolta possibile ed è un modo semplice per trovare una nuova soluzione; ad esempio, partendo dalla soluzione riportata del rettangolo 3×20, è possibile ottenerne un'altra semplicemente ruotando un blocco di sette pentamini, o, in altri termini, ruotando i 4 pentamini più a sinistra e scambiandoli di posto con quello più a destra).

Ci sono 1010 soluzioni per il rettangolo 5×12, 368 per quello 4×15 e solo 2 per quello 3×20.

Un rompicapo più semplice (perché più simmetrico), il quadrato 8×8 con un buco 2×2 in mezzo, era stato risolto da Dana Scott già nel 1958^[2]: esistono 65 soluzioni. L'algoritmo con cui Scott raggiunse questo risultato è stato una delle prime applicazioni informatiche del backtracking. Altre variazioni del rompicapo permettono di cambiare la posizione dei quattro quadratini mancanti. Molte di queste configurazioni sono risolvibili; fanno eccezione quelle in cui i buchi vengono messi:

a coppie in corrispondenza di due angoli e in modo tale che in entrambi sia necessario utilizzare un pentamino P
in prossimità di un angolo in modo tale che vi si possa disporre solo un pentamino T o U, creando però un nuovo buco.

Sono stati trovati algoritmi efficienti per risolvere questi problemi, ad esempio da parte di Donald Knuth^[3]. Su un moderno computer, questi rompicapo possono ormai essere risolti in pochi secondi.

Riempimento di scatole

[modifica | modifica wikitesto]

Un pentacubo è un policubo composto di cinque cubi. Dodici dei 29 pentacubi corrispondono ai 12 pentamini, nel senso che questi ne sono la proiezione sul piano. Esistono dei rompicapo basati sul riempimento di una scatola tridimensionale con questi pentacubi piatti. Ognuno dei 12 pentacubi è composto di 5 cubetti, quindi ovviamente la scatola deve contenere 60 cubetti; le possibili dimensioni sono 2×3×10, 2×5×6 e 4×3×5; di seguito sono riportate alcune soluzioni.

Se consideriamo anche i pentacubi non piatti (ed aggiungiamo quindi ai 12 appena considerati 6 paia di pentacubi chirali e 5 pentacubi non chirali), otteniamo un totale di 29 pezzi, ovvero 145 cubetti; non esiste però nessuna scatola di forma parallelepipedale che contenga un tale numero di cubetti.

Il gioco da tavola

[modifica | modifica wikitesto]

Esiste un gioco da tavola basato sui pentamini e chiamato pentominoes.

Il campo di gioco è una scacchiera $8\times 8$ su cui si affrontano due o tre giocatori, aggiungendo a turno un pentamino alla scacchiera; vince l'ultimo giocatore che riesce a sistemare un pezzo in modo tale che non si sovrapponga ai precedenti.

Nella versione a due giocatori, è stato dimostrato che il primo giocatore ha una tattica vincente.

I pentamini, come d'altronde altre forme simili, sono alla base di molti altri giochi e rompicapo. Per esempio, un gioco da tavola francese detto Blokus si gioca con 4 avversari, ognuno con un set pentamini (12), uno di tetramini (5), uno di triomini (2) e uno di domini (1) di un certo colore. Di nuovo, lo scopo del gioco è riuscire a sistemare tutti i propri pezzi, cercando di lasciare per ultimo il domino.

La Parker Brothers ha prodotto un gioco da tavola detto Universe nel 1966, basato sui pentamini, dall'ambientazione basata sul film 2001: Odissea nello spazio: l'astronauta gioca contro il computer una partita a pentomino (quella che nel film è una partita a scacchi). Il coperchio del gioco raffigura scene del film nonché una didascalia che lo descrive come "il gioco del futuro". Il gioco contiene 4 set completi di pentamini ed un'area di gioco composta da una base $10\times 10$ più 25 quadrati addizionali da aggiungere per due giocatori in più.

Video games

[modifica | modifica wikitesto]

Il Tetris è stato ispirato dai rompicapo con pentamini, nonostante i suoi mattoncini siano poi tetramini.
Il gioco Daedalian Opus contiene svariati rompicapo con pentamini.
Yohoho! Puzzle Pirates contiene un mini-game (Carpentry) costituito da un rompicapo con pentamini.

Note

[modifica | modifica wikitesto]

^ C. B. Haselgrove, Jenifer Haselgrove, A Computer Program for Pentominoes, in Eureka, vol. 23, ottobre 1960, pp. 16–18.
^ Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.
^ Donald E. Knuth. "Dancing links" Archiviato il 5 luglio 2017 in Internet Archive. (Postscript, 1.6 megabytes). Include un riassunto degli articoli di Scott e Fletcher.