Newsgroup: it.hobby.enigmi
Titolo: Divisione massima di scacchiera

Spesso ci e' capitato di proporre e/o risolvere problemi riguardanti
divisioni di scacchiere. Se consideriamo la scacchiera 8x8, nella sua
norrmale colorazione bianco/nero, questa puo essere divisa in miliardi
di modi in N pezzi diversi. (ricordiamo che due pezzi sono diversi se
hanno forma e/o colorazione diversa). In generale gli N pezzi possono
formare la scacchiera in molti modi differenti, ogni tanto mi sono
trovato davanti ad un insieme di pezzi che possono formare la
scachiera in un solo modo.
Mi chiedevo quale sia il massimo N per cui la scachiera puo' essere
costruita in un solo modo.
Un saluto a tutti,
Gabriele
(GaS)

 costruita in un solo modo.
Grazie GaS per questo problema interessante.
Ci sono 3 casi distinti da considerare:
a) Scacchiera colorata solo su un lato.
b) Scacchiera colorata su entrambi i lati con colori opposti uguali (sotto 
                     il nero c'e' il nero)
c) Scacchiera colorata su entrambi i lati con colori opposti differenti 
(sotto il nero c'e' il bianco e viceversa)
Pezzi disponibili:
Caso a)
2 monomini
1 domino
4 triomini
10 tetramini
36 pentamini
Il massimo teorico e' di 18 pezzi.
Caso b)
2 monomini
1 domino
4 triomini
7 tetromini
24 pentamini
Il massimo teorico e' di 18 pezzi.
Caso c)
1 monomino
1 domino
2 triomini
6 tetramini
18 pentamini
Il massimo teorico e' di 16 pezzi.
A occhio dubito che si possano trovare assemblaggi con il massimo teorico 
di pezzi e con soluzione unica, per la grande mobilita'dei pezzi piccoli.
Per i casi a) e b)  conoscono soluzioni in 15.
Appena ho un po' di tempo ci lavoro su'.
ciao

 Per i casi a) e b)  conoscono soluzioni in 15.
A mano, per il caso a, sono arrivato a 13 ma spulciando su qualche libro ne'
ho trovata una da 14. Per ora non riesco a trovare di meglio anche data la
difficcolta di verificare l'unicita'.
Per la verifica io uso il programma di Gerard (with a little help from Livio
Zucca :o) usando quadrati 3x3 per ogni blocco, pieno per le caselle bianche
e bucato per le caselle nere poi imposto una scacchiera 24x24 (8x3.8x3) con
gli opportuni quadratini pieni al centro delle future caselle nere. Esiste
un modo migliore per implementare una scacchiera o mi tocca impazzire per
disegnare tutti i pezzi triplicati?
Gabriele

 disegnare tutti i pezzi triplicati?
Per carita' ! non c'e' niente da disegnare.
MOPS gestisce gia' pezzi "scacchierizzati" e non solo, ma
il migliore e' senz'altro FlatPoly2 scaricabile da qui:
http://home.planet.nl/~avdw3b/aad.html
Ha un numero notevole di opzioni, non e' difficile da utilizzare in ogni 
caso una volta che lo hai attivato puoi chiedermi lumi.
Per prima cosa vai in "Polyominoes -> Open Polyomino File ->12345.fpo"
In questo modo carichi tutti i polimini da 1 a 5.
"Polyominoes -> Properties" accedi alla lista dei pezzi.
Ora per ciascun pezzo hai un numero notevole di scelte, difatti puoi:
Stabilire la quantita' da 0...
Scegliere quali rotazioni o riflessioni tenere e quali eliminare.
Stabilire se il dato pezzo deve o non deve toccare il bordo.
Se ci sono piu' coppie dello stesso pezzo puoi imporre delle restrizioni 
tipo si devono toccare o non si devono toccare.
Cliccando al centro di una casella puoi praticarne un "foro" rosso, blu o 
azzurro che e' obbligato ad infilarsi in un "piolo" dello stesso colore 
presente su caselle dell'area da coprire, rispettando i colori, questo ti 
da un considerevole numero di possibilita'.
Per stabilire l'area di lavoro, vai in "Field -> Properties" crea un 
rettangolo abbastanza grande da contenere l'area voluta.
Colora le caselle da eliminare di grigio. Le caselle bianche sono 
considerate libere ed il programma puo' utilizzarle o no, quelle colorate 
in celeste invece devono essere coperte. Queste opzioni sono fondamentali 
per risolvere problemi tipo ponti con area massima ecc..
Nel caso della scacchiera devi semplicemente mettere un "piolo" diciamo 
rosso per ogni casella nera, e un "foro" dello stesso colore sui pezzi, 
come ho detto prima.
ciao

Visto che non riesco a fare meglio di 14 mi posteresti la soluzione da 15?
Grazie mille,
Gabriele


Scusami Gabriele, ma ho commesso un errore.
Fra i miei pezzi mi ricordavo di una sol. unica in 15, che in realta' c'e', 
ma da una verifica, ho scoperto che c'e' un vincolo; i pezzi non possono 
essere ruotati. Ho trovato alcune sol. in 13.
La tua in 14 per il momento, sembra essere la migliore.

Sembra che questa questione sia stata affrontata e risolta in uno dei numeri
di "Games and Puzzles" edito da G P Jelliss (Ed Pegg dixit), forse Dario
possiede i numeri della rivista in questione?
 Ormai a mano non riesco a trovare niente pero' la questione mi sembra
interessante, cosi' sono disposto a qualche trucco(per esempio copiare la
soluzione :o)
Un saluto,
Gabriele

 possiede i numeri della rivista in questione?
Jellis pubblica delle ottime pagine con materiale ricercato, e' uno dei 
maggiori esperti sulla storia dei percorsi del cavallo sulla scacchiera.
Alcuni numeri di Games and Puzzles li ha pubblicati qui:
http://www.gpj.connectfree.co.uk/index.htm
vedi se c'e' il problema che ti interessa.
Piu' tardi eventualmente guardo sul cartaceo (dovrei avere tutti i numeri)
ciao

 ciao
Te ne sarei molto grato, grazie mille per la solita disponibilita'.
Gabriele
 (GaS)

 n'e'traccia
Ho guardato, ma anch'io sono carente, mi manca tutto il primo volume da 1 a 
13 e parte del secondo. Mi dispiace.
ciao