Newsgroup: it.hobby.enigmi
Titolo: La tassellanza dei polimini

Vorrei "misurare" la tassellanza dei polimini in generale, dei decamini
in particolare perche' ogni tanto dedico un po' di tempo all'idea di
comporre un puzzle con questi 4655 pezzi.
A proposito, gia' nel 2001 li disegnai ad uno ad uno ed il disegno,
per chi volsse ispirarsi, e' qua:
http://www.geocities.com/liviozuc/images/finaldec.gif
(ricordatevi di cercare il tasto di O.E. per ingrandire il disegno)
Dunque, per fare un puzzle tradizionale, prima cerchiamo il contorno,
poi cerchiamo quelli piu' facili, separiamo i colori e ci riserviamo per
ultimi quei pezzi un po' tutti uguali che formano il cielo o un prato...
Per i decamini bisogna fare qualche cosa di analogo, perche' e'
impensabile costruire una macchina, un programma che esamini
tutte le combinazioni. Questi programmi funzionano per poche
decine di pezzi, poi il tempo-macchina diverge verso valori
ultra-cosmici. D'altra parte abbiamo la speranza che le soluzioni
siano molte e che quindi se ne possa trovare almeno una con un
po' di fortuna e un po' di metodo.
Il metodo che appare verosimile e' quello di usare all'inizio i
pezzi "difficili" procedendo dal contorno ad un buco piu' o
meno centrale che probabilmente verra' riempito dai pezzi
piu' "facili" che ci siamo tenuti da parte. Magari per il finale di
20-30 pezzi useremo un solver esaustivo  programmato solo
sul buco e sui pezzi rimasti. Spero di essere stato chiaro.
E' quello che faremmo intuitivamente e che ha consolazione
matematica: all'inizio e' possiblie usare pezzi piu' "difficili"
perche' si puo' scegliere tra tanti pezzi, alla fine ci vogliono
quelli piu' "facili" perche' bisogna sistemarli proprio li'.
La tassellanza e' la proprieta' di tassellare il piano "facilmente".
Ma come valutarla, al di la' di una stima intuitiva, quella che,
giocando con i pentamini ci fa sistemare subito la "X", tenendo
per ultimo il "P"?  [This is the question!]
Abbiamo recentemente visto che il polimi "passeggiabili" hanno
elevata tassellanza. Quelli passeggiabili anche esternamente
ancor di piu'. Quelli "cavalcabili" sono un disastro: i dieci ottomini
cavalcabili si inseriscono a mala pena in un rettangolo 9x10.
(La "X" dei pentamini e' doppiamente non passeggiabile, cioe'
eliminato un omino non si passeggia ancora).
Tra quelli passeggiabili sembrano avere maggior tassellanza quelli
che sono piu' compatti: in termini fisici quelli che hanno minor
momento d'inerzia (sommatoria dei quadrati delle distanze di
ciascun omino dal baricentro del polimino).
(La "P" dei pentamini e' passeggiabile dentro e fuori ed e' il pezzo
che ha il piu' basso momento d'inerzia.).
Tra i polimi ci sono quelli che sono in grado di tassellare il piano
da soli. Essi hanno un'alta tassellanza? Non sempre e' cosi'. Se
e' vero che uno di noi, per andare d'accordo con gli altri, deve
prima di tutto andare d'accordo con se stesso, e' anche vero che
non e' detto che le proprieta' degli uomini siano trasferibili agli
omini! Pensate ad un pezzo a pettine fatto cosi':
 _   _
| | | |
| |_| |_
|_ _ _ _|
esso tassella facilmente il piano ma si sposa mal volentieri con
gli altri.
Che cos'e' dunque, la tassellanza? La capacita' di affiancarsi agli
altri, al maggior numero possibile degli altri? Possiamo trovare
una definizione, una "sostanza", una formalizzazione, un loop, un
accidente che ci possa far dire: "Quel polimino ha tassellanza 3.72" ?
Che ne dite?
Speriamo di non fare la fine del protagonista di "Lo Zen e l'arte
della manutenzione della motocicletta" che impazzi' chiedendosi
cosa fosse la Qualita'.
Ciao!!!  ((^__^))'
Livio

 A proposito, gia' nel 2001 li disegnai ad uno ad uno ed il disegno,
Quanti hanni c'hai messo? :)

 Quanti hanni c'hai messo? :)
Ti confesso che non fu semplice perche' non c'erano i bei files ascii
giapponesi che ora ci sono in rete. Sono andato su google per vedere
come avevo fatto perche' non me lo ricordavo. Fu con l'aiuto di questo
ng, soprattutto di Dario Uri, che definimmo la piu' piccola figura che
contenesse sicuramente tutti i decamini, uno alla volta. Poi si lavoro'
un po' con le matrici binarie...
Ora pero' il problema e' metterli tutti insieme appassionatamente in
un rettangolo o giu' di li'.
Ciao!!!  ((^__^))'
Livio

 Quanti hanni c'hai messo? :)
Son sempre rimasto sbigottito di fronte a chi sui ng sbagliava a mettere l'
"h", mi sembrava un errore cosě banale. E invece ora che mi rileggo...

 "h", mi sembrava un errore così banale. E invece ora che mi rileggo...
Gli antichi Latini impararono a mettere l'acca davanti alle vocali al
posto dell'accento. Lo insegnarono agli Anglosassoni che ancora
lo usano saggiamente. Noi invece mettiamo gli accenti che ci
incasinano le tastiere. Neppure l'esperanto imparho :o) la lezione.
Ciao!!!  ((^__^))'
Livio

 giapponesi che ora ci sono in rete. 
link please :-)
Stok.

 link please :-)
http://www.asahi-net.or.jp/~uy7t-isn/Puzzle/Polyominoes/
Ciao!!!  ((^__^))'
Livio