Newsgroup: it.hobby.enigmi
Titolo: Quadrati di polimini

Nel 2004, in uno di quei percorsi di follia che non so neanche piu'
ricostruire, riuscii a tassellare di decamini il piu' grande quadrato che
si possa coprire con questi polimini. Aveva il lato di 210. Prima o poi lo
ritrovo in qualche HD nell'armadio.
Ora, piu' modestamente, provavo con i polimini di ordine inferiore. 
Per N=1 e' facile. Lui stesso e' un quadrato ed e' la soluzione al tempo
stesso.
Per N=2,3,4 niente da fare.
Per N=5 c'e' un facile quadrato di lato 5 tassellato da 5 pentamini. Ci
sono 107 soluzioni possibili.
Per N=6 si puo' coprire un quadrato di lato 12.
Per N=7 si puo' fare il lato 21.
In allegato metto la figura riassuntiva.
Non ho soluzioni per N=8, 9 e >10
Il gioco potrebbe generare una nuova sequenza per l'Enciclopedia Online
delle sequenze dei numeri interi, che avrebbe questa forma:
1,0,0,0,5,12,21,?,?,210,...
Il problema non e' concettualmente difficile perche' i quadrati sono
normalmente ricopribili con un sub-set di polimini, scartando a posteriori
quelli che non servono. Al piu', all'aumentare di N, cresce la
complessita' di gestire la cosa.
Per N>=8 alcuni polimini hanno dei buchi. Direi che questi si possono
scartare a priori.
Non so se continuero' questa ricerca. Molto dipendera' anche se qualcuno
raccoglie la sfida.
Fatemi sapere.
Ciao
Livio
Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=OTkzNQ
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=OTkzNQ
In questa figura c'e' gia' un errore: gli anglofoni dicono "polyominoes"
non polimini come facciamo noi. Questo perche' coniarono il termine
pensando che l'antico gioco del domino avesse etimologia di-omino.
Yankees! :o)
Intanto ho trovato la figura del quadrato di lato 210 tassellato dai
decamini.
Ciao
Livio
Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=OTkzNg


 decamini.
Orpo, ma e' mostruoso (me lo sono salvato, a futura memoria).
Posso provare con gli octomini senza buchi, col quadrato, mi sembra,
da 52 x 52,
ma la vedo dura. In teoria ci starebbe anche il quadrato 53x53, usando
un polimino
(la ciambella) col buco che quindi occupa 3 caselle.Quello da 54x54
non mi sembra
si possa fare.
Credo che il mio misero programma non ce la faccia con quadrati cosi'
larghi...
ciao,
g.

 larghi...
David Bird ha riempito degli schemi completi gia' molti anni orsono.
Es:
http://recmath.org/PolyPages/PolyPages/Pictures1/octom1.gif
Non escluderei che li abbia fatti a mano. Guarda come sono raggruppati
i pezzi "piu' facili" che probabilmente si e' tenuto per ultimi. Io mi
ero ispirato a questo concetto per fare il quadrato di decamini.
Purtroppo 1) non ricordo quasi niente, 2) ho documentato pochissimo,
3) il programma era affatto generico, molto tagliato per risolvere
quello specifico problema e difficilmente modificabile per gli altri
polimini.
Ciao
Livio

 i pezzi "piu' facili" che probabilmente si e' tenuto per ultimi.
Si, mi sembrava di aver letto qualcosa a quel proposito, tipo prima
fase
a mano e fase finale con un programma (ma forse era un altro
problema...)
Comunque ho modificato il mio programma in modo radicale
e pur con qualche aiutino ha tirato fuori uno schema 52 x 52 per
gli ottomini
http://www.iread.it/polpic/squa/octoquad.png
In realta' il programma ha un qualche baco che spero
riguardi solo la fase di output, ma ora e' tardi e non ce la faccio
a controllare. Comunque per il momento questo e' il meglio
che ho ottenuto.
Magari poi potrei fare una paginetta per questi risultati, compreso,
se permetti, il tuo schema megagalattico.
'notte.
g.

 se permetti, il tuo schema megagalattico.
Complimenti, sei stato velocissimo.
Non e' casuale, vero, quella linea che lo divide in due rettangoli?
Naturalmente hai tutti i permessi di pubblicare, anzi mi farebbe
piacere, anche perche' non lo pubblico' nessuno. Lo segnalai solo su
"Polyforms", insieme ad uno schema rettangolare 235x199 con buchi
simmetrici che avevo intenzione di risolvere con tutti i decomini.
Poi, in altre faccende affaccendato, sospesi i lavori. Alcuni mesi
piu' tardi Peter Esser lo risolse e fu pubblicato da Ed Pegg e da
Andrew Clarke e ancora li' lo trovi. Del quadrato si perse la
storia :o)
Ciao
Livio

 Non e' casuale, vero, quella linea che lo divide in due rettangoli?
Eh, no. Il programma riusciva a tirar fuori delle soluzioni fino a
44x44 in pochi secondi,
ma per cose piu' grandi si arenava, allora gli ho fatto risolvere due
schemi rettangolari
e in un ora o due ce l'ha fatta. Potrei provare a fargli risolvere due
rettangoli con
il bordo un po' piu' frastagliato, visto che quella riga in mezzo urta
un po' il mio senso estetico
(probabilmente ruotandola di 90gradi mi darebbe meno noia).
Sta continuando a girare la ricerca del 52x52 intero, ma
non ho molte speranze. Probabilmente dovrei implementare un altra
(potenziale) miglioria
al programma. Quando avro' tempo... magari il prossimo week-end provo
ad attaccare
quello con gli enneomini...
ciao,
g.

 quello con gli enneomini...
Mi piacerebbe mostrarti il sistema che avevo messo a punto per
risolvere i decamini. Sono riuscito a riaviarlo perche' e' piu'
rifinito e dodumentato di quel che pensassi. Evidentemente volevo
renderlo pubblico ma poi ho interrotto il lavoro. Ho fatto uno zip di
circa 3MB con il file di SETUP per ambiente Windows.
I decamini sono classificati pre "tassellanza". Non ricordo ancora
come ho fatto, evidentemente avevo visto da poco il film Shining e mi
sono ispirato alla luminanza :o). Il programma tenta di piazzare il
pezzo con la piu' bassa tassellanza nel punto piu' lontano all'angolo
in basso a destra dello shape. Deve essere possibile interrompere il
lavoro, fare modifiche manualmente e farlo ripartire. Ad un certo
punto restera' un angolo irrisolto e i pezzi tra i piu' facili da
piazzare. Il finale e' esplorato in modo esaustivo dal solito solver
di Gerard per il quale il programma fornisce il file gia' pronto
all'uso.
Se mi autorizzi, te lo spedirei.
Ciao
Livio

 Se mi autorizzi, te lo spedirei.
Manda manda, son sempre curioso, anche se non posso garantire che lo
esaminero'
immediatamente. Il mio indirizzo e'  g.resta LUMACA 
iit.cnr.it
Nel frattempo mi sono accorto che un programma mi aveva sputato
un quadrato 31x31 fatto con tutti gli esamini, tutti gli eptamini non
bucati (cioe' tutti meno 1)
e il domino:
http://www.iread.it/polpic/squa/hephex31.png
ciao,
g.

 e il domino:
http://www.iread.it/polpic/squa/hephex31.png
Ma pensa, ci stavo lavorando!
L'idea era quella di fare quadrati usando somme di serie complete di
polimini senza buchi.
1) Il primo e' il monomino, non ci piove.
2) Lato 3: monomino+domino+trimini.
3) Lato 9: monomino+tetramini+pentamini
4) Lato 31: domino+esamini+eptamini (che e' il tuo)
5) ?????????
Ciao
Livio
PS Ora ti spedisco.lo zip.

 5) ?????????
Il candidato successivo potrebbe essere quello di lato 56, ma e' somma
delle serie di ordine pari (2+4+6+8)mini, quindi potrebbe, anzi e'
probabile, non esserci la parita' giusta. Conviene calcolarla prima di
tentare.
Ciao
Livio

 5) ?????????
Allora, non posso aiutarvi a tirare fuori soluzioni (leggi: non sono
capace) però il lavoro "sporco" per tirare fuori le possibili
configurazioni lo posso fare.
Le successive soluzioni possibili  fino ai decamini sono:
5) Lato 61: domino+trimini+pentamini+eptamini+ottamini
6) Lato 107: monomino+trimini+esamini+ennamini
7) Lato 213: tetramini+eptamini+decamini
8) Lato 218: tetramini+ottamini+decamini
9) Lato 238: monomino+domino+pentamini+eptamini+ennamini+decamini
Buona fortuna :-)
Ciao,
GaS

Considerando anche gli undecamini (?!?) c'è una decima possibilità:
10) Lato 435: esamini+eptamini+ennamini+undecamini
GaS

 5) Lato 61: domino+trimini+pentamini+eptamini+ottamini
Quello da 56 l'hai gia' scartato per motivi di parita'?

 10) Lato 435: esamini+eptamini+ennamini+undecamini
Pero' prima facciamo quello di lato 418 di soli endecamini con
l'avanzo di 210 pezzi, che e' piu' facile!  :o)
Ciao
Livio

 Quello da 56 l'hai gia' scartato per motivi di parita'?
No, semplicemente perchè l'avevi gia detto te e mi sono scordato di
partire dal numero 6 :-)
Ciao,
GaS

 ad attaccare quello con gli enneomini...
Non dico di accettare la sfida... :o) pero' la tentazione e' forte. Nel
link c'e' un quadrato lato 100 coperto da 1000 decamini. D'accordo, non e'
concettualmente difficile, pero' l'ho fatto in pochi minuti usando il mio
vecchio sw, e anche coi i pezzi piu' difficili, a parte l'angolino in
basso a destra fatto "a mano". Secondo me il principio sarebbe valido per
il quadrato di ennamini (probabilmente di lato 105) e forse, visto che nel
frattempo i pc sono diventati piu' potenti, anche per quello tassellato da
endecamini.
Chissa'...
Ciao
Livio
Guarda l'immagine cliccando 
http://attach.mynl.it/img?id=OTk2NQ


 concettualmente difficile, pero' l'ho fatto in pochi minuti
Che tristezza... il mio programma non e' riuscito nemmeno a trovare
il 61 x 61 (ottomini+eptamini+...).  Umiliazione...
Il massimo che ho ottenuto dopo un giorno di modifiche, di debugging e
di run,
e' stato di replicare il 52x52 di ottomini in un pezzo
solo e il 53x53 di ottomini con un buco al centro:
http://www.iread.it/polpic/squa/octo5253.png
(quello 56x56 mi sembra (?) che non si possa fare a causa parita')
Penso proprio di dover implementare una qualche fase preliminare
tipo quella che usi tu. Magari piu' tardi o domani (adesso ho una
saturazione
da polimini) ti scrivo in privato per chiederti qualche dettaglio sul
tuo mirabile dekominizzatore.
ciao,
g.

 tuo mirabile dekominizzatore.
Sto scrivendo un help corretto, anche per rinfrescarmi la memoria.
Quello allegato si riferisce ad una versione molto precedente. Appena
pronto, te lo mando.
Ciao
Livio

 pronto, te lo mando.
Grazie mille. Al di la dei criteri che hai usato per stabilire il
coefficiente di tassellanza per
ogni dekamino, non mi e' chiaro se applichi una strategia greedy,
tipo:
ad ogni passo determini una ben precisa casella (in base alla
distanza, mi sembra)
e la riempi usando il primo polimino libero che ci sta, scandendoli in
ordine di tassellanza,
oppure se fai anche backtracking nel caso non ce ne stia
nessuno o per eliminare buchi (o se stai attento a non crearli)
etc.etc.
ciao,
g.

 nessuno o per eliminare buchi (o se stai attento a non crearli)
Non faccio backtracking in questa fase (ma pensavo di implementarlo).
Se non riesce andare avanti, si stoppa e mi fa un fischio. Io
intervengo manualmente a rimuovere qualche pezzo o a dare una
sistemata intuitiva e poi lo faccio ripartire.
Nel caso del lato 210 e' successo una dozzina di volte. Questa
possibilita' di intervenire manualmente era uno dei miei obiettivi
principali.
Ti metto il file "help.txt" qua sotto, tanto e' ascii. Manca ancora
qualche tasto che non ricordo a che cosa servivano (!).
Ciao
Livio
================================================
GERARD'S SOLVER HELP FOR DECOMINOES
Livio Zucca
R2.7 Auto 210x210
Data 1.a ed.:  6/7/2001
Versione:      2.7 (2004)
Tipo SW:       Freeware
REQUISITI
Pentium.
Windows da 95 in poi con Internet Explorer 5.0 in su. con l'attività
Java abilitata.
SCOPO
Tassellare grandi shapes con i decamini.
METODO
1) <RESET>.
2) Caricare il file "Vuoto.htm" (selezionare - <LOAD>).
3) Sbloccare l'editingt dello shape togliendo la V dal check
"Polyforms".
4) Editare le finestrelle "Shape max X" e "Shape max Y". Aggiungere
caselle grige a piacimento.
5) Vistare il check "Polyforms".
6) Editare il nome del file desiderato come *.htm nella finestrella
sopra <LOAD> e salvare con <SAVE>.
7) Con le frecce nella cornice rossa si possono inserire o togliere
decomini manualmente.
8) Con il tasto <START> inizia la ricerca automatica.
9) Con il tasto <STOP> si arresta e si possono fare correzioni manuali
come al punto 7) e poi riprendere con <START>.
10) Quando mancano pochi pezzi (massimo 30) si stoppa e premendo
<SAVE> si salva la situazione. Premendo <PUTTER> si genera il file
"Finale.htm" adatto ad essere risolto dal Gerard's Solver. (Basta
aprirlo da I.E. od equivalente).
11) Se il Gerard's Solver trova la soluzione. va riportata a mano
nello shape.
Descrizione tasti.
==================
<LOAD>
Carica i files precedentemente salvati, scritti sulla finestrella
sovrastante, selezionabile dalla lista a lato.
<SAVE>
Salva la descrizione in un file HTML (tipo *.HTM), dal nome scritto
sulla finestrella sovrastante.
<FILE PREVEW>
Visualizza il file HTML come verrà salvato. I più esperti potranno
modificarlo anche in ascii.
<HELP>
Visualizza questo testo.
<CANCEL TEXT>
Cancella il testo lasciando la visualizzazione dello shape.
<RESET>
Azzera tutte le variabili in gioco. Attenzione: perderete il vostro
lavoro se non lo avete salvato su file.
<REDRAW>
Ridisegna tutti i pezzi e lo shape in funzione dei parametri
eventualmente corretti. Il rilascio delle finestrelle testo dei
parametri (lost focus) genera comunque un redraw automatico.
<U>
Cancella le linee interne dei polimini.
<SHOW DECOMINOES>
Mostra un foglio con tutti i decomini. Purtroppo la corrispondenza
della numerazione e' andata perduta.
<FIND>
Abilita la finestrella "Find free decomino" per la ricerca rapida del
decomino desiderato.
<PUTTER>
Salva il file Finale.HTM (compatibile con il Gerard's Solver) del solo
"buco" da risolvere e i restanti pezzi non utilizzati.
<Save *.BMP>
Slava il disegno del puzzle allo stato dell'arte. Lo stato dello ZOOM
influenza la scala del disegno.
<START>
Fa partire la ricerca automatica.
<STOP>
Sospende la ricerca automatica e permette di editare manualmente
qualche pezzo. Si puo' ripartire con <START> a piacere.
USO DELLA FINESTRELLA "Find free decomino"
Durante la ricerca automatica e' gestita dal programma e mostra in
rosso il punto di ricerca corrente. In fase di STOP aiuta la ricerca
manuale del decomino da piazzare non ancora utilizzato. con il
seguente metodo:
1) Nel dubbio chiudere la finestrella e riaprirla con il tasto <FIND>.
2) Cliccare lo shape principale in una zona libera da decomini dove
volete sistemare un pezzo. La finestrella si posizionera' nei
dintorni.
3) Cliccare a piacere caselle libere dentro alla finestrella che
diventeranno rosse.
4) Premere "<" o ">" della finestrella per cercare il pezzo che
coprira' le caselle rosse.
5) Trovato il pezzo desiderato dovrete posizionarlo manualmente nello
shape principale.
TAVOLOZZA DEI COLORI
Serve per colorare i decamini o i buchi sullo shape.
FINESTRELLE DEI PARAMETRI
Si possono correggere con il mouse e la tastiera. Saranno utilizzati
anche per la compilazione automatica del file HTML. Vengono limitati
se si superano i limiti di macchina.
CONTATORE INDICE PEZZI E TASTI "<" e ">"
Servono per esplorare la forma di ciascun pezzo.
-------------------------------------------
FINE

 Nel caso del lato 210 e' successo una dozzina di volte.
... un centinaio di volte.
Ciao
Livio

Nel link c'e' un quadrato lato 100 coperto da 1000 decamini.
Livio, mi meraviglio di te: hai sprecato ben 5 (e dico cinque!) colori
per colorarlo, ne bastavano sicuramente meno :-))))
Ciao,
GaS


infatti basta solo un po' di pazienza: :-)
http://www.iread.it/polpic/squa/dekoZucca4.gif
ciao,
g.


:o)
Ho ragionato cosi':
Dal teorema di Fermat sulla mappa a quattro colori (oggi si puo'
chiamare teorema, vero?) si deduce che bastano 4 colori per colorare
quel quadrato. Si', ma a posteriori, a bocce ferme diciamo in queste
valli. Se io voglio colorare la mappa man mano che viene a formarsi,
senza sapere a priori quale sara' il pezzo successivo e dove sara'
sistemato, dico io, ce ne vorra' almeno uno in piu'!?!
E che ne bastino 5 mi sembra un'interessante congettura.
Ciao  :o)
Livio


Posso, GaS, spedirlo anche a te 'sto software, che magari a tre teste
vengono piu' idee?  :o)
Ciao
Livio

 E che ne bastino 5 mi sembra un'interessante congettura.
Ho la sensazione che 5 non bastino, e magari neanche 6...
ciao,
g.

 Ho la sensazione che 5 non bastino, e magari neanche 6...
Beh, pero' potrebbero forse bastare con un certo algoritmo oppure usando
solo decomini, oppure entrambe le cose. Fatto sta che ho fatto girare un
po' il solver con il lato 210 e 5 colori continuano a sembrare
sufficienti... (allego figura)
Ciao
Livio


 > E che ne bastino 5 mi sembra un'interessante congettura.
Mi sa che ce ne vogliono infiniti...
Ma il problema e' simpatico. Apro un nuovo thread.
g.

 (allego figura)
Si', ci provo, almeno...


 Si', ci provo, almeno...
Uffa, proviamo cosi':
http://host.presenze.com/immagini/112009/20091123034430prova210oggigif.gif

 vengono piu' idee?  :o)
Mi vergognavo a chiedertelo... il fatto è che in vita mia ho
programmato veramente poco e, ormai, il massimo che faccio sono solo
semplici macro per excel. Però mi piacerebbe proprio sapere come
lavorate voi "gente seria" :-)
Manda, manda,
però poi ti faccio domande stupide tipo: che linguaggio di
programmazione è? ma come lo posso compilare? Cosa fa il comando
pincopallo?
Ciao,
GaS

 sufficienti... (allego figura)
Si, qualche ipotesi aggiuntiva va fatta, Ad esempio, abbandonando
l'ipotesi di lavorare con i decamini, se alla figura che hai fornito
viene applicata una "cornice" tutto intorno c'è necessità di un sesto
colore.
Ciao,
GaS


Ancora meglio, senza abbandonare l'ipotesi di lavorare con i decamini:
basta aggiungere il decamino I orizontalmente sotto il quadrato,
proprio dove c'è l'unico pezzo celeste che tocca il bordo.
GaS



Visto!
Resta il fatto che il solver continua a riempire lo shape senza mai
ricorrere al sesto colore (che, se non erro, il sw gli consente). Ed
e' un bell'enigma. :o)
Ora ti mando il programma. Non ti preoccupare, per il momento, del
linguaggio (poi, se vuoi, ne parliamo). Io, intanto, ti mando
l'eseguibile per vederlo lavorare e farci qualche riflessione, se ne
hai voglia.
Ciao
Livio

Ho messo i risultati principali (piu' qualche altro) qui:
http://www.iread.it/quadratipolimini.php
Livio, se ti va quarda le due frasi che ho messo
prima e dopo la tua creatura e fammi sapere se vuoi aggiungere
o togliere qualcosa.
Appena posso, voglio provare a programmare
un approccio come quello usato da Livio, ma senza
bisogno di aiuti umani, perche' sono troppo pigro
e comunque incapace di "vedere" i polimini.
Insomma vorrei esplorare un po' di strade alternative
al puro backtracking ricorsivo, che quando si infila
in un vicolo cieco ci rimane praticamente in eterno.
Non so se ce la faccio prima delle vancaze natalize,
ma sti enneomini che non riesco a ficcare da nessuna
parte mi stanno facendo innervosire (per usare un eufemismo...)
ciao,
g.

 o togliere qualcosa.
E' tutto bellissimo.
Interessante per me la ricoloratura del quadratone, che avrai fatto
sicuramente in modo automatico, leggendo il file grafico. Sono
capacita' che ti invidio.
Ciao
Livio

 capacita' che ti invidio.
Sono partito dalla tua immagine gif e siccome non avevo voglia
di imparare a usare librerie varie per leggere immagini o cose
simili, l'ho convertita in un formato super semplice per immagini
in B&N, in pratica nel file c'e' scritto numero di righe, numero di
colonne,
e poi uno 0 o un 1 per ogni pixel, senza nessuna compressione.
Una volta importata l'immagine in memoria ho ricavato il grafo
delle adiacenze. A questo punto avrei potuto cercare in rete
una qualche libreria o software per 4-colorare una mappa, ma sembra
che la cosa non sia cosi' semplice.
Allora per non impazzire troppo, ho
fatto un programmino in due fasi. Nella prima fase ho usato
un programma ricorsivo con backtracking che cercava di colorare
usando solo 3 colori  (lo so che e' impossibile) ma che ogni tot volte
si lasciava andare fino
a 5 colori. Alla fine di questa rapida fase ero riuscito a colorare
usando cinque colori, e il quinto compariva solo circa un centinaio
di volte su 4410. A questo punto ho pensato di usare questo sistema:
partivo da ogni cella colorata col colore 5 (quello da eliminare)
e provavo a vedere se potevo scambiare il colore con una regione
adiacente. Una volta spostato il colore 5 in un altra posizione
controllavo se potevo mutarlo in un colore da 1 a 4 (perche'
ad esempio, i suoi nuovi vicini avevano solo i colori 1 2 e 4.
Ho ripetuto questi movimenti random per un po' e rapidamente
il numero delle zone colorate 5 e' calata drasticamente a poche
unita'. Per eliminare anche le ultime ho fatto degli scambi di colore
random (leciti) tra celle adiacenti a caso e dopo un po' sono riuscito
ad eliminare il quinto colore del tutto.
ciao,
g.


Cosa non si fa pilotando un po' il caso!  :o)
Ciao
Livio