Newsgroup: it.hobby.enigmi
Titolo: Polimini percorribili

Andiamo a definire una sottoclasse dell'insieme dei polimini. Disegniamo un
polimino qualsiasi indicando tutti i quadrati che lo compongono; diciamo che
un polimino è "Percorribile" se è possibile tracciare la sua figura con un
unico tratto di penna (senza staccarla dal foglio).
 Ecco i polimini percorribili fino ad N=6
N=1
 _
|_|
N=2
 _ _
|_|_|
N=3
 _
|_|_
|_|_|
N=4
 _     _
|_|_  |_|_
|_|_| |_|_|
  |_| |_|
N=5
 _ _       _     _
|_|_|_   _|_|_  |_|_
  |_|_| |_|_|_| |_|_|_
  |_|     |_|     |_|_|
N=6
   _     _   _   _         _     _
 _|_|_  |_|_|_| |_|_      |_|_  |_|_     _ _
|_|_|_| |_|_|_| |_|_|_   _|_|_| |_|_|_  |_|_|_
  |_|     |_|     |_|_| |_|_|     |_|_| |_|_|_|
  |_|               |_|   |_|     |_|     |_|
N=7
     _       _         _       _
   _|_|_   _|_|_     _|_|_   _|_|
 _|_|_|_| |_|_|_|  _|_|_|_| |_|_|_
|_|_| |_|   |_|_| |_|_|     |_|_|_|
              |_|   |_|       |_|
   _       _ _        _ _      _
 _|_|_   _|_|_|     _|_|_|   _|_|_
|_|_|_| |_|_|_    _|_|_|   _|_|_|_|
 _|_|     |_|_|  |_|_|    |_|_|
|_|_|     |_|    |_|      |_|
(Non ne vedo altre per N=7 ma non sono troppo sicuro)
Non è difficile, dato un polimino qualsiasi, verificare se sia o meno
percorribile: basta contare il numero dei vertici in cui convergono solo 3
segmenti, se non ne esistono o ne esistono solo 2 allora è percorribile
altrimenti niente.
Vediamo un paio di domande, d'ora in poi definiamo PP i Polimini
Percorribili:
1) Secondo voi è possibile trovare una formula che ci dia il numero di PP in
funzione di N?
2) Esistoni PP con N>4 che tassellano un rettangolo?
Che ne dite?
Gabriele

 Che ne dite?
Potevi cominciare con domande piu' facili?  :o)
Se, ad es., chiedevi: Quanti sono i decAmini percorribili?
Io rispondevo:  60
... e facevo la mia porca figura!
Ciao!!!  (^__^))'
Livio
 1
XX.X......
XXXXX.....
.X.X......
..........
..........
 2
X.XX......
XXXXX.....
.X.X......
..........
..........
 3
.XXX......
XXXXX.....
.X.X......
..........
..........
 4
X.X.X.....
XXXXX.....
.X.X......
..........
..........
 5
.X..XX....
XXXXX.....
.X.X......
..........
..........
 6
..X.XX....
XXXXX.....
.X.X......
..........
..........
 7
.X.X......
XXXXXX....
.X.X......
..........
..........
 8
.X..X.....
XXXXXX....
.X.X......
..........
..........
 9
..X.X.....
XXXXXX....
.X.X......
..........
..........
 10
XX.X......
.XXXX.....
XX.X......
..........
..........
 11
..X.XX....
.XXXX.....
XX.X......
..........
..........
 12
.X..X.....
XXXXXX....
.X..X.....
..........
..........
 13
.X.X......
.XXXX.....
XX.X......
X.........
..........
 14
..XX......
.XXXX.....
XX.X......
X.........
..........
 15
..X.X.....
.XXXX.....
XX.X......
X.........
..........
 16
.X.XX.....
XXXX......
.XX.......
.X........
..........
 17
.X.X......
XXXXX.....
.XX.......
.X........
..........
 18
XXX.......
.XXX......
XXX.......
.X........
..........
 19
XX.X......
.XXX......
XXX.......
.X........
..........
 20
.X.XX.....
.XXX......
XXX.......
.X........
..........
 21
..XXX.....
.XXX......
XXX.......
.X........
..........
 22
.XX.......
XXXX......
XXX.......
.X........
..........
 23
.X.X......
XXXX......
XXX.......
.X........
..........
 24
.X.X......
.XXXX.....
XXX.......
.X........
..........
 25
..XX......
.XXXX.....
XXX.......
.X........
..........
 26
..X.X.....
.XXXX.....
XXX.......
.X........
..........
 27
.X.X......
XXXXX.....
.X.X......
.X........
..........
 28
.X.X......
.XXXX.....
XX.X......
.X........
..........
 29
..XX......
.XXXX.....
XX.X......
.X........
..........
 30
..X.X.....
.XXXX.....
XX.X......
.X........
..........
 31
..XX......
.X.XX.....
XXXX......
.X........
..........
 32
....XX....
.X.XX.....
XXXX......
.X........
..........
 33
...X......
X.XXX.....
XXXX......
.X........
..........
 34
..X.......
.XXXX.....
XXXX......
.X........
..........
 35
...X......
.XXXX.....
XXXX......
.X........
..........
 36
....X.....
.X.XXX....
XXXX......
.X........
..........
 37
...X......
X.XXX.....
XXX.X.....
.X........
..........
 38
..X.......
.XXXX.....
XXX.X.....
.X........
..........
 39
...X......
..XXXX....
XXX.X.....
.X........
..........
 40
..X.......
.XXX......
XXXXX.....
.X........
..........
 41
...X......
..XXX.....
XXX.XX....
.X........
..........
 42
.X.X......
XXXX......
.XX.......
XX........
..........
 43
...X......
..XXXX....
.XX.X.....
XX........
..........
 44
...X......
..XXX.....
.XX.XX....
XX........
..........
 45
.X.XX.....
XXXX......
.XX.......
..X.......
..........
 46
.X.X......
XXXXX.....
.XX.......
..X.......
..........
 47
.XX.......
XX.XX.....
.XXX......
..X.......
..........
 48
X..X......
XX.XX.....
.XXX......
..X.......
..........
 49
.X.X......
XX.XX.....
.XXX......
..X.......
..........
 50
X...X.....
XX.XX.....
.XXX......
..X.......
..........
 51
..X.......
XXXXX.....
.XXX......
..X.......
..........
 52
..XX......
.X.XX.....
XXXX......
..X.......
..........
 53
..X.......
.XXXX.....
XXXX......
..X.......
..........
 54
...X......
..XXX.....
.XXX......
XX........
X.........
 55
...X......
..XXX.....
.XX.X.....
XX........
X.........
 56
...X......
..XXX.....
.XXX......
XX........
.X........
 57
...X......
..XXX.....
.XX.X.....
XX........
.X........
 58
....XX....
...XX.....
..XX......
XXX.......
.X........
 59
....X.....
...XXX....
..XX......
XXX.......
.X........
 60
....XX....
...XX.....
..XX......
.XX.......
XX........

>> Che ne dite?
1,1,1,2,3,6,8,?,?,60,...
Cmq direi che ti stai guadagnando un posticino nell'Enciclopedia
delle Sequenze di Interi.
Ciao!!!  ((^__^))'
Livio

 1,1,1,2,3,6,8,?,?,60,...
Mi dici come fai a tirare fuori i decamini percorribili mentre non dai
risultati per N=8,9 ?
Sopratutto: li hai fatti a mano o tramite apposito programmino?
Per ora aggiorno la casella per N=8, dovremmo avere 19 PP
Un saluto,
Gabriele
  X
 XXX
XX XX
   X
XXXXX
 X X
 XX
XX
 XX
XX
XX
 XX
  XX
   XX
 X
 XX
XX
 XX
 X
  XX
 XX
XX
 XX
  X
 XX
 X
XXX
 X
   X
  XXX
XXX
 X
 XX
XX
 XXX
  X
X X
XXXX
 XX
 X
XX
 XX
  XX
   X
 X
 XX
XX
 XX
  X
 X
XXX
XXX
 X
 X
 XXX
XXX
 X
  XX
 XX
XXX
 X
X X
XXXX
X X
  X
 XXX
XXX
 X
 X
XXXX
 XX
 X
   X
 XXX
 XX
XX

Questi dati vanno presi con beneficio d'inventario.
Io sono uno che si sbaglia.  :o)
Quelli di ordine superiore al 10 sono ancora alla nostra portata.
Bisogna imho cambiare strategia. Data la loro bassa densita',
si potrebbe, ad es., generare i polimini senza preoccuparsi delle
R&R, vedere se sono percorribili e solo allora preoccuparsi
delle R&R rispetto a quelli gia' trovati.
A proposito delle domande di Gabriele, io scommetterei NO & NO.
Ma niente di piu' di una scommessa. Potrebbero invece essere
buoni per i rettangoli jagged .
Alla prossima!!!  ((^__^))'
Livio
Sequenza:
1, 1, 1, 2, 3, 6, 8, 18, 28, 60, ...
Densita':
1, 1, 0.5, 0.4, 0.25, 0.171, 0.074, 0.049, 0.022, 0.013, ...
Ottomini percorribili:
 1
XXX.....
.X......
XXX.....
.X......
 2
XX.XX...
.XXX....
..X.....
........
 3
XX.X....
.XXXX...
..X.....
........
 4
XX.X....
.XXXX...
...X....
........
 5
XX......
.XX.....
XXX.....
.X......
 6
XX......
.XX.....
XX......
.XX.....
 7
XX......
.XX.....
.XXX....
..X.....
 8
XX......
.XX.....
..XXX...
...X....
 9
XX......
.XX.....
..XX....
.XX.....
 10
XX......
.XX.....
..XX....
...XX...
 11
.XX.....
XXXX....
.XX.....
........
 12
.XX.....
XX......
.XXX....
..X.....
 13
.X.X....
XXXXX...
.X......
........
 14
.X.X....
XXXXX...
..X.....
........
 15
.X......
XXXX....
.XX.....
.X......
 16
.X......
XXXX....
.XX.....
..X.....
 17
.X......
XXX.....
.XXX....
..X.....
 18
.X......
XXX.....
..XXX...
...X....
Ennomini percorribili:
 1
XX.X.....
.XXXX....
.X.X.....
.........
.........
 2
XX.X.....
.XXXX....
..XX.....
.........
.........
 3
XX.X.....
.XXXX....
..X.X....
.........
.........
 4
XX.......
XXX......
.XXX.....
..X......
.........
 5
XX.......
.XXX.....
XXX......
.X.......
.........
 6
XX.......
.XXX.....
..XXX....
...X.....
.........
 7
XX.......
.XX.X....
..XXX....
...X.....
.........
 8
XX.......
.XX......
XXXX.....
.X.......
.........
 9
XX.......
.XX......
XXXX.....
..X......
.........
 10
XX.......
.XX......
XX.......
.XX......
.X.......
 11
XX.......
.XX......
.X.......
XXX......
.X.......
 12
XX.......
.XX......
..XX.....
.XX......
.X.......
 13
XX.......
.XX......
..XX.....
.XX......
..X......
 14
XX.......
.XX......
..XX.....
...XX....
...X.....
 15
XX.......
.XX......
..XX.....
...XX....
....X....
 16
XX.......
.XX......
..X......
.XXX.....
..X......
 17
.XX......
XXXXX....
.X.X.....
.........
.........
 18
.XX......
XXXX.....
.XX......
.X.......
.........
 19
.XX......
XXX......
.XXX.....
..X......
.........
 20
.XX......
XX.X.....
.XXX.....
..X......
.........
 21
.XX......
XX.......
.XX......
..XX.....
..X......
 22
.X.X.....
XXXXX....
.X.X.....
.........
.........
 23
.X.......
XXXX.....
.X.XX....
...X.....
.........
 24
.X.......
XXXX.....
..XXX....
...X.....
.........
 25
.X.......
XXX......
.XXXX....
..X......
.........
 26
.X.......
XXX......
..XX.....
.XX......
.X.......
 27
.X.......
XXX......
..XX.....
.XX......
..X......
 28
.X.......
XXX......
..XX.....
...XX....
...X.....

 Per ora aggiorno la casella per N=8, dovremmo avere 19 PP
Oh, la prima discrepanza! Ne ho appena postati 18.
Ora mi toccherra' verificare, verificare...
Per gli ottomini e gli ennomini mi sono basato su files pescati
in rete, ahime!
Ciao!!!  ((^__^))'
Livio

 in rete, ahime!
Come era prevedibile l'errore č da imputare alla ricerca umana (mia) e non a
quella del computer (di Livio). Ho scorso a mano una figura composta da
ottomini trovata in rete e ci si č infilato un errore.
Come era altresi prevedibile la legge di Murphy ha messo il suo zampino: la
soluzione errata č l'ultima da me presentata (le ho dovute ricontrollare
tutte una per una prima di arrivare all'errore).
Livio: mi sai dire dove trovare, in rete, un catalogo di poliforme piů
completo possibile? Per esempio non sono riuscito a trovare il catalogo dei
singoli ottomini ma solo figure composte, per gli ennomini niente da fare.
Gabriele

 Potrebbero invece essere buoni per i rettangoli jagged .
Dunque, se gli ottomini percorribili sono 18, 18x8=144 e
il quadrato jagged 9x9 con il buco centrale ha proprio l'area
di 144. Gli eptomini e gli ottomini percorribili insieme fanno
un'area di 200, quella del rettangolo jagged 10x11.
Vuoi vedere che...   :o))
Proprio cosi'!!!
Guardate qua:
http://www.geocities.com/liviozuc/images/7e8perc.gif
Ciao!!!  ((^__^))'
Livio

 singoli ottomini ma solo figure composte, per gli ennomini niente da fare.
Io mi sono servito qua:
http://www.asahi-net.or.jp/~uy7t-isn/Puzzle/Polyominoes/
Per i decamini, invece, erano venuti fuori da idee di questo ng
un paio di annetti fa, pero' ci sono anche qua.
Sono comodi i file testo, organizzabili in semplici matrici.
Ciao!!!  ((^__^))'
Livio

"Gabriele Carerlli"
Who's that guy?
--
Silv:o)

 ...
Bisogna fare subito le macro dei polimini percorribili!!!
Ciao!!!  ((^__^))'
Livio

Dunque, sono arrivato qua:
1,1,1,2,3,6,8,18,28,60,102,206,...
I 102 endecamini e i 206 dodecamini percorribili li ho
ancora estratti con lo stesso programma dai files giapponesi.
Quello dei dodecamini, una volta unzippato, era abbastanza
pesante: 63600 righe da 84 caratteri = 5,4 MBytes, WordPad
ha la lingua fuori, ma il mio programma impiega ancora pochi
secondi. Il metodo andrebbe ancora bene per i successivi,
solo che non abbiamo i files.  :o(
EndecAmini o EndecamIni? A me ricordano gli endecasIllabi.
E one-line-polyominoes andra' bene per gli anglofoni?
Dalle mie reminescenze scolastiche, direi che se un grafo
puo' essere "percorso", allora puo' essere percorso anche
senza incroci. E' sempre vero?
Per i 13-omini farei cosi':
1) Muoverei, con un for/next concatenato, 13 bit dentro una
matrice booleana da 13x7.
2) Escluderei al volo tutte quelle che hanno almeno un bit isolato.
3) Escluderei al volo tutte quelle che non hanno 0 o 2 nodi dispari.
4) Le rimanenti non dovrebbero essere piu' di 3000.
5) Tra queste eliminerei le R&R.
Ma magari qualcuno ci arriva prima in altro modo.
Per adesso buona notte!!!  ((^__^))'
Livio

 Ma magari qualcuno ci arriva prima in altro modo.
Io sicuramente no, non saprei da che parte cominciare :o(
Gabriele


Mmm...  e come fai a garantire che slegando un nodo non si formino
anelli chiusi mai?
    _ _
   |   |
_ _|_ _|
   |
   |
    _ _
   |   |
_  \_ _|
  \
   |
   |
Ciao!!!  ((^__^))'
Livio

    |
Non succede se lo sleghi nel modo che io ho indicato, seguendo il verso
delle frecce come segue:
    a
    |
    |
b -------> c
    |
    |
    V d
     a
     |
    _|
b<--  _----> c
     |
     |
     d
Puoi vedere che non si formano modi rileggiendo bene la mia mail, ho
indicato bene i tratti percorsi.
Gabriele

 indicato bene i tratti percorsi.
Oh, l'ho capito adesso. (meglio tardi...:o))
Quello che non capivo e' che non puoi aprire tutti i nodi
in un colpo, ma apri un nodo, poi ricalcoli il percorso,
poi ne apri un altro e cosi' via. Se li apri tutti in base al
primo senso di percorrenza tracciato, vengon fuori gli
anelli.
Ciao e grazie!!!  ((^__^))'
Livio

 1,1,1,2,3,6,8,18,28,60,102,206,...
Ciao Livio, potresti mandarmi i risultati che hai ottenuto per i polimini
percorribili, magari in privato per non appesantire il ng.
Grazie mille e complimenti dei risultati ottenuti,
Gabriele