Newsgroup: it.hobby.enigmi
Titolo: Tetris

Premessa: ho impostato un font non proporzionale nella composizione delle 
news ma a quanto pare mi costringe ad utilizzare il verdana (?) copiate il 
testo sotto nel blocco note o altro.
ciao, ricordate il vecchio gioco? sto cercando di sistemare alcuni pezzi in 
una griglia 8x10 per� voglio mantenere 1 casella di distanza tra un pezzo e 
l'altro, diagonali comprese, riesco a sistemare in questo modo tutti i pezzi 
tranne 1 a questo punto mi chiedo se sia effettivamente possibile vi 
riassumo sotto i pezzi che sto cercando di collocare, non tutti fanno parte 
del tetris classico, la griglia ripeto � 8x10 eccoli:
X XX XXX XXXX
  X
XXX
XXX
  X
 X
XXX
XX
 X
 XX
XX
XX
 XX
XX
XX
--
Stefano Gandolfo
Financial Services Introducer
http://www.giocareinborsa.biz
 


se ho copiato bene i pezzi questa è una soluzione:
x x		x	x	x		x 	x	x
									x
x	x	x	 	x	x	x	x
 	x								x
 				x	x		x	x	x
 	x		x	x
x	x	 	 			x	 	x	x
x	 	 	x		x	x	 	x	x
(fai copia e incolla dentro excel o un altro spreadsheet per
ricostruire la griglia)
bye!


grazie ma intendo lasciare 1 casella di spazio tra ogni blocco non tutti 
attaccati!!

 Financial Services Introducerhttp://
www.giocareinborsa.biz
I pezzi che descrivi sono tutti i polimini non rovesciabili di ordine
1, 2, 3 e 4 che, in tutto, sono 11.
Il problema e' interessante, ma le soluzioni sono tante. Sotto ne
metto una in ascii-art:
X..X.XX.XX
X.XX.XX..X
X.X......X
....XX.X..
X..XX..X.X
XX....XX.X
...X.....X
X.XXX.XX.X
(per vedere l'ascii-art usare caratteri fissi)
Ciao
Livio

 Il problema e' interessante, ma le soluzioni sono tante.
Se non ho sbagliato i conti, le soluzioni sono piu' di 80.000
Invece, se raddoppiamo il monomino (il quadratino da 1) per un totale
di 12 pezzi, allora le soluzioni sono solo tre e forse non sono facili
da trovare!  :o)
Ciao
Livio
PS. Ora faccio un pensierino su soluzioni analoghe coi pentamini.


che conti hai fatto? :O 


caspita che bravo! ci ho provato almeno un'ora e non mi era riuscito, 
addirittura pi� soluzioni!?!
ti/vi propongo il quesito successivo in un altro post 'Tetris 2' ora lo 
preparo... 

 PS. Ora faccio un pensierino su soluzioni analoghe coi pentamini.
Un problema interessante potrebbe essere
Qual e' il rettangolo minimo che puo' contenere i 12 pentamini in modo
che tra loro ci sia sempre uno spazio minimo di un quadretto, anche in
diagonale?
Io una soluzione ce l'avrei.
Ignoro se il problema sia inedito perche' non seguo nel dettaglio
queste cose da un po' d'anni.
Ciao
Livio

 che conti hai fatto? :O
E' soltanto bruteforce.
Si gioca un po' coi solver di polimini.


non ho idea di quello che dici :D cosa sono i polimini e
cos'� un risolutore di dette cose? un programma? si scarica?
grazie ciao, 


esiste un algoritmo che lo possa determinare senza doverlo fare in pratica? 

 cos'è un risolutore di dette cose? un programma? si scarica?
Sì, c'e' tutta una classe di problemi geometrici riguardanti i
polimini per risolvere la quale molti hanno scritto dei programmi.
more info:
http://www2.polito.it/didattica/polymath/htmlS/probegio/GAMEMATH/Polimini/Polimini.htm
Se usi un po' google con "polimini" o "polyminoes" se sei anglofono ti
si aprirà un mondo ;^)
bye!

 attaccati!!
non sono attaccati, lo spazio c'e' :)
Te lo riscrivo nel formato usato da Livio:
xx.xxx.xxx
.........x
xxx.xxxx..
.x.......x
....xx.xxx
.x.xx.....
xx....x.xx
x..x.xx.xx
come ti segnalava lui, di soluzioni ce ne sono parecchie!
bye!


ma come ci riuscite? :( io dubitavo fosse impossibile dopo 1 ora di 
tentativi 

 esiste un algoritmo che lo possa determinare senza doverlo fare in pratica?
Direi proprio di no, ovvero l'algoritmo consiste in genere proprio nel
provare le varie combinazioni. Tutta la tematica delle poliforme e
delle tassellazioni e' difficilmente riducibile a delle formule
sintetiche.

 queste cose da un po' d'anni.
Inedito no, proprio ieri l'ho trovato su una rivista di una decina di
anni fa (solo una coincidenza? noi di voyajer crediamo di no ... :-)
Se vuoi ti/vi faccio sapere la soluzione max. riportata,
ma poi che ci frega se è inedito? :-)
Ciao,
GaS

 ma poi che ci frega se è inedito? :-)
Beh, effettivamente e' improbabile che esista un gioco sui pentamini
che non sia gia' stato proposto. Pero' qualche volta ci siamo
riusciti, no?  :o)
Ciao GaS!!!  :o)
Livio
PS. Tu lo saprai certamente, ma io l'ho scoperto or ora che condividi
il soprannome niente popodimeno che col grande Charles Darwin.

 il soprannome niente popodimeno che col grande Charles Darwin.
Veramente questa mi giunge nuova, grazie mille!

 Si può fare un po' meglio se per minimo intendi minimo di *area*...
Forse il 18X7 ?
P..Y.TTT.ZZ..W.U.U
PP.Y..T..Z..WW.UUU
PP.YY.T.ZZ.WW.....
...Y..........NN.L
.F...X..VVV.NNN..L
FFF.XXX.V........L
F....X..V.IIIII.LL
Ciao
Livio


 Si può fare un po' meglio se per minimo intendi minimo di *area*
Al momento il minimo di area che sono riuscito ad ottenere e' 120
(salvo errori).
Entro stasera vedo di costruire le figure.
ciao,
g.

 (salvo errori).
Confermo 24x5. Provo ancora.
Ciao
Livio

 Confermo 24x5. Provo ancora.
Ed io confermo i 120 come area massima, se non ricordo male è
fattibile anche con il rettangolo 40x3.
Come al solito grande Livio!
Ciao,
GaS


No no, l'ha detto prima Giovanni Resta!

 fattibile anche con il rettangolo 40x3.
I risultati che ho trovato per le varie lunghezze del lato corto
(3,4,...,11)
li potete visualizzare qui:
http://www.iread.it/pento_pack_it.php
ciao,
giovanni

 li potete visualizzare qui:
http://www.iread.it/pento_pack_it.php
La mia curiosita' e': hai fatto un sw ad hoc ho hai modificato qualche
cosa che gia' avevi?
Ciao
Livio

 cosa che gia' avevi?
Sono riuscito fortunosamente a ritrovare uno dei tanti programmi
per risolvere schemi di polimini che avevo fatto (tutti senza
commenti, tutti con nomi improbabili e sepolti in sottodirectory
che mi sono portato dietro negli ultimi 3 cambi di sistema operativo
e hard disk).
Una volta capito grosso modo cosa facevo ho fatto una modifica
relativamente semplice alla routine ricorsiva: dopo avere inserito
ogni pezzo
gli metto attorno una cornice di riempimento (che mi dovro' ricordare
di togliere
insieme al pezzo quando torno indietro) e vado avanti.
Il problema e' che il programma originario cercava di riempire
uno schema senza lasciare buchi mentre qui, in teoria,
potremmo dover lasciare qualche spazio, che poi magari
sara' riempito dalla cornice di un pezzo messo dopo.
Chiaramente ammettere la presenza di questi buchi
(che ho risolto permettendo al programma di saltare un numero
max di caselle durante il riempimento) fa aumentare
di molto il tempo di ricerca. Per questo non posso
dire che gli schemi che ho trovato siano ottimali: dopo
dieci minuti che il programma girava mi stufavo e provavo
un'altra configurazione. Per gli esamini per esempio ho
provato solo una parte delle combinazioni perche'
i tempi diventano geologici e ho messo in fondo alla pagina
solo due esempi che il programma ha trovato in pochi secondi.
Comunque mi ha fatto piacere perche' almeno cosi' ho
rifatto un po' di pratica sui polimini....
Ciao,
giovanni
--
http://www.iread.it
  anagrammi, criptaritmi, calcoli enigmatici,...

g.r...@iit.cnr.it
 ha scritto:



Innanzitutto complimenti per questa tua capacita' di far risolvere alle
macchine gli enigmi.
Poi volevo raccontarti come ho fatto io, ovviamente con meno efficienza,
ma usando risorse che ormai sono solo sul tuo sito! :o)
http://www.iread.it/lz/pmf4.html
Ho moltiplicato per due sia i pentamini che lo shape, ottenedo cosi' 12
icosamini :o)
Ho quindi potuto accrescere ogni pezzo e lo shape con uno strato di
quadretti. 
A questo punto mi sono accorto che tutti i pezzi erano multipli di
quadrati 2x2, cosi' ho potuto ridividere tutto per due, ottenendo 11
dodecamini e un endecamino. 
Ho dato tutto in pasto al solver di Gerard e voila.
Gli spazi ulteriori sono occupati da un numero opportuno di monomini. La
figura allegata mostra il solver che risolve il rettangolo 14x9.
Ciao
Livio
Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=OTkzMw
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it



Scusa Giovanni!
Ho letto i due messaggi uno di seguito all'altro e mi sembrava che
fossero entrambi di Livio,
allora: come al solito grande Giovanni! Davvero,
Ciao,
GaS


Via, via, in questo campo siamo tutti dei ri-scopritori, visto che di
solito
questi problemi li hanno sempre gia' strastudiati. A me piu' che
arrivare
primo o secondo mi da soddisfazione quando un programma sputa
un disegnino, invece di piantarsi come fa spesso...
Comunque e' curioso che l'approccio usato da Livio e' simile al primo
che mi era venuto in mente. L'ho scartato perche' sarei dovuto
andare a vedere come il mio vecchio programma memorizzava i
pezzi per poi "aumentarli". Non ne avevo proprio la forza...
ciao,
g.

 tentativi
allenamento :)
bye!