Newsgroup: it.hobby.enigmi
Titolo: La scacchiera colorata

Vi invio un problema che mi ha perseguitato per anni e del quale sono poi
venuto a capo un po' con un ragionamento che non ricordo e un po' per
tentativi: avevo anche fatto un programma che passasse in rassegna le
combinazioni, ma le potenzialità elaborative di allora erano un po' limitate
...
La scacchiera colorata.
Abbiamo una scacchiera 6x8. Se consideriamo i possibili quadrati di 2x2
tracciabili sulla scacchiera, questi sono ovviamente 5x7=35. Prendiamo 48
tessere gialle, rosse, verdi e blu, 12 per ciascun colore.
Prendendo le possibili combinazioni di 4 di queste tessere, si vede
facilmente che esse sono 35.
La domanda sorge spontanea: come si devono mettere le 48 tessere sulla
scacchiera in modo che i 35 quadrati 2x2 contengano le 35 combinazioni
possibili?
Ripeto: ho la soluzione, ma non il metodo per ottenerla.

possibili?
________________________________________________________________
                  N i c o l a   G a u d e n z i
 /\  /            E-mail ---> 
gaud...@cs.unibo.it
/  \/ I C R O S   
http://www.cs.unibo.it/~gaudenzi


Scusate, sono stato lungi dal NG per qualche tempo (crash del mio HD, sob!).
Rispondo. Le combinazioni valide sono solo quelle non ripetute; cioè
supposto che i colori siano BRVG, la combinazione BBRR è equivalente a BRBR
e a RBBR e a quelle simili. In questo modo restano solo queste 35:
BBBB, RRRR, VVVV, GGGG,
BBBR, BBBV, BBBG,
RRRB, RRRV, RRRG,
VVVB, VVVR, VVVG,
GGGB, GGGR, GGGV,
BBRR, BBVV, BBGG, RRVV, RRGG, VVGG,
BBRV, BBRG, BBVG,
RRBV, RRBG, RRVG,
VVBR, VVBG, RRVG,
GGBR, GGBV, GGRV,
BRGV
(Spero di non aver fatto errori di battitura, ma il concetto è chiaro, no?)
Saluti
Gianni.
(Se qualcuno volesse la soluzione, mi mandi un e-mail)

Dunque, la prima cosa che mi è venuta in mente e' stato un algoritmo (magari
in
PROLOG) che passasse in rassegna tutte le possibili disposizioni delle
tessere.
Pero' ho realizzato subito che questo sono 4^48 cioè 2^96.
In realta' l'algoritmo non le passerebbe in rassegna tutte perche' molti
rami
dell'albero delle scelte vengono potati.
(ad esempio: dopo aver disposto le prime n tessere mi accorgo che la
n+1-esima
non puo' essere rossa, altrimenti formo un quadrato gia' utilizzato. In
questo caso
si potano tutte le 4^(48-n-1) disposizioni che presentano le prime n tessere
disposte
in quel modo e la n+1-esima rossa).
Non sono pero' in grado di fare una stima di quanto sia l'ordine di
grandezza delle
disposizioni generate in questo modo, ma l'impressione e' che sia necessaria
una
potatura ancora piu' drastica se si vuole che l'algoritmo termini in tempi
ragionevoli.
L'idea successiva che ho avuto e' che ci sia una forma di simmetria nella (o
nelle)
soluzione(i) del problema, cioe':
Se noi dividiamo la scacchiera in 4 parti uguali (che chiameremo quadranti,
anche se
sono rettangolari) allora dobbiamo provare solo 4^12 disposizioni, che con
la potatura di
cui sopra diventano ancora meno.
Inoltre si ha che le 4 tessere centrali quelle cioe' il cui quadrato e'
formato da tessere
appartenenti ognuna ad un quadrante diverso sono ognuna di un colore diverso
dalle
altre 3. Quindi rimangono 4^11 = 2^22 = 4.194.304 soluzioni che con la
potatura si
riducono ancora piu' drasticamente.
Se tu, che hai la soluzione, mi confermi che essa e' simmetrica rispetto ai
4 quadranti
allora questa strada e' percorribile, altrimenti sono molto tentato
dall'arrendermi
data l'esplosione combinatoria che si verificherebbe.
Non so pero' se tu eri interessato ad un metodo per risolvere il problema
che facesse
uso del calcolatore (per provare qualche migliaio di disposizioni possibili)
o se invece
cercassi addirittura un metodo per risolvere il tutto a mano.
P.s. Mi appassionano molto questo genere di giochi, non capisco perche' fino
ad
ora io sia stato l'unico a risponderti sul NG.


La mia ipotesi sulla simmetria delle soluzioni era
errata, infatti costruendo soluzioni simmetriche mi
trovo in difficolta' a disporre i quadrati contenenti
due coppie di tessere uguali.
Ho voluto invece tentare ugualmente di scrivere un
semplice programmino che generasse lo spazio delle
disposizioni legali delle tessere, pur sapendo che
tutte le disposizioni (anche quelle non legali) sono
4^48 cioe' un numero di 28 cifre!
Il problema ammette moltissime soluzioni ed infatti
il mio programma comincia a sputarne fuori a raffica
e continua ad andare avanti finche' non lo termino
con metodi drastici.
Ecco la prima soluzione:
 R R R R R R
 R R V V G R
 R B R V V V
 V V G V V B
 V B G G B G
 B B G R B B
 B B V G G B
 G B V G G G
Dopo piu' di 2000 soluzioni le prime 16 tessere
rimanevano ancora invariate rispetto alla prima soluzione.
A chi e' interessato posso spedire il sorgente in C del
programma.
Ciao.


Ci deve essere qualche problema nel tuo programma. Mi aveva messo in allarme
la frase "moltissime soluzioni" e allora non mi sono fidato. Se non ho
controllato male, nella *presunta* soluzione precedente:
1. mancano BBBR, RRGG, RRBB, RRGB, GGRV, BBRV
2. VVVB, BBGV, VVRG, RBGV compaiono 2 volte
3. BBBG compare 3 volte.
Visto che siamo gli unici ad interessarci a questo problema, puoi mandarmi
una mail.
Ciao.
Gianni.