Newsgroup: it.hobby.enigmi
Titolo: A=B

. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
Sostituire 14 puntini con sette "A" e sette "B" in modo tale che su 
ciascuna colonna e ciascuna riga si contino lo stesso numero di A e B.
In altre parole, ogni allineamento deve contenere una A ed una B, oppure 
due A e due B.
Quante soluzioni ci sono?

 Quante soluzioni ci sono?
Con questa condizione *aggiuntiva* trovo (forse) 14400 soluzioni.
[spoiler]
.
.
.
.
.
.
.
.
A . B B A
. B . A .
B . A . .
B A . A B
A . . B .
Considerando che con una inversione di righe e/o colonne la soluzione rimane
valida, posso distribuire le cinque righe in
5!=120 modi differenti.
Per ciascuna distribuzione di righe, posso distribuire le colonne in
altrettanti modi differenti.
Mi risultano quindi 120^2=14400 soluzioni.
Rimerrebbe da verificare se siano tutte diverse, e se ne esistano delle
altre non ottenibile con queste inversioni.
ciao
paolo

altre non ottenibile con queste inversioni.
Credo che ci sia un'altra simmetria: scambiando la A con la B si ottiene 
un'altra soluzione, quindi il numero salirebbe a 14400*2=28800 (o forse 
cosi` si riottiene una di quelle dette in precedenza?)
Usando Constraint Logic Programming con vincoli di ordinamento 
lessicografico sulle righe e sulle colonne, ottengo 178 soluzioni.
Se questo fosse un metodo che elimina tutte le simmetrie, dovrei poi 
moltiplicare per 14400 (perche' il mio programma non elimina la simmetria 
A-B) per avere tutte le soluzioni. Pero` e` noto che cosi` non si 
eliminano tutte le simmetrie, lo ha mostrato una mia amica (Zeynep 
Kiziltan) in un suo articolo.
Quindi posso dire che sono meno di 14400*178=2563200.
Riporto di seguito le prime 10 soluzioni, per controllo (metto sempre 
errori dappertutto ....)
Ciao ciao,
Marco
. . . A B 
. . . A B 
. . . B A 
A A B B . 
B B A . A 
. . . A B 
. . . A B 
. . . B A 
A B B . A 
B A A B . 
. . . A B 
. . . A B 
. . A B . 
A B . B A 
B A B . A 
. . . A B 
. . . A B 
. . A B . 
A B B . A 
B A . B A 
. . . A B 
. . . A B 
. . B . A 
A B . B A 
B A A B . 
. . . A B 
. . . A B 
. . B . A 
A B A B . 
B A . B A 
. . . A B 
. . . A B 
. A B . . 
A B . B A 
B . A B A 
. . . A B 
. . . A B 
. A B B A 
A . . B . 
B B A . A 
. . . A B 
. . . A B 
. A B B A 
A B . . . 
B . A B A 
. . . A B 
. . . A B 
. A B B A 
A B . B A 
B . A . . 
--
http://www.ing.unife.it/docenti/MarcoGavanelli

 B A A B .
Queste sono equivalenti per inversione delle righe 4 e 5 e delle colonne 1 e
3.
Anche le due successive sono equivalenti e sospetto ci siano altri casi.
Per ora ho solo questo da dire :(
--
Ciao, Silv:o)

, 
silvio...@libero.it
 says...

Infatti, come spiegavo il metodo che ho usato elimina separatamente le 
simmetrie di riga e quelle di colonna, ma non toglie le simmetrie in cui 
ci sono uno scambio di riga ed uno di colonna.
Purtroppo ora non ho tempo di provare un metodo piu` selettivo.
Forse si potrebbe provare con GAP o qualche altro software che usa la 
teoria dei gruppi.
Ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli


Ho trovato 32 soluzioni; avendo lavorato a mano non escludo errori in un
senso o nell'altro, cioč potrebbero non essere tutte indipendenti, oppure
potrei averne trascurato qualcuna.
Qualcuno potrebbe verificare con qualche programma?
Sono partito dalla considerazione che devono necessariamente esserci due
righe con quattro segni.
Colloco queste due righe ai primi due posti, e considero che la prima sia
sempre
A A B B *
Per la seconda riga trovo sei possibili distribuzioni:
A A B B *
A B A B *
A A B B *
B B A A *
A A B B *
B * A B A
A A B B *
A B A * B
A A B B *
A * A B B
A A B B *
B * A A B
(ho trascurato gli schemi che contevano i quadrati
A A
A A
oppure
B B
B B
perché non consentono ulteriori sviluppi).
Da queste sei aperture ho generato 32 schemi:
A A B B *
A B A B *
B A * * *
B * * * A
* B * * A
A A B B *
A B A B *
B * A * *
B * * * A
* * B A *
A A B B *
A B A B *
B * A * *
B * * A *
* * B * A
A A B B *
A B A B *
B * * * A
B * * A *
* * * A B
A A B B *
B B A A *
B * * * A
* A * * B
A B * * *
A A B B *
B B A A *
B * * * A
* * A * B
A * B * *
A A B B *
B B A A *
* * B * A
A * * * B
B * A * *
A A B B *
B B A A *
* * B * A
* * * A B
* * A B *
A A B B *
B * A B A
B * * A *
* B * A *
A * * * B
A A B B *
B * A B A
B * * A *
* * * A B
A B * * *
A A B B *
B * A B A
* * B A *
* B * A *
* * A * B
A A B B *
B * A B A
* * B A *
* * * A B
* B A * *
A A B B *
B * A B A
* B * A *
* B * A *
* A * * B
A A B B *
B * A B A
* * * A B
* * * A B
* B * * A
A A B B *
A B A * B
B A * * *
B * * A *
* B * * A
A A B B *
A B A * B
B A * * *
B * * * A
* B * A *
A A B B *
A B A * B
B * A * *
B * * A *
* * B * A
A A B B *
A B A * B
B * A * *
B * * * A
* * B A *
A A B B *
A B A * B
B * * A *
B * * A *
* * * B A
A A B B *
A B A * B
B * * * A
B * * * A
* * * A B
A A B B *
A * A B B
B * * A *
B * * A *
* B * * A
A A B B *
A * A B B
B * * A *
B  * * A
* B * A
A A B B *
B * A A B
A B * * *
B A * * *
* B * * A
A A B B *
B * A A B
A * B * *
B * A * *
* B * * A
A A B B *
B * A A B
A * * * B
B * * * A
* B * * A
A A B B *
B * A A B
A B * * *
B * A * *
* * B * A
A A B B *
B * A A B
A * B * *
B * * * A
* B A * *
A A B B *
B * A A B
* A B * *
* B A * *
* B * * A
A A B B *
B * A A B
* A * * B
* B * * A
* B * * A
A A B B *
B * A A B
* * A B *
* B * A *
* * B * A
A A B B *
B * A A B
* * A B *
* B * * A
* * B A
A A B B *
B * A A B
* * A * B
* * B * A
* B * * A
ciao
paolo

 B * A A B
In un certo senseo, questo metodo e` piuttosto simile a quello che si usa 
in Constraint (Logic) Programming: si eliminano a priori le 
configurazioni in cui non puo` esserci soluzione, poi si fa una scelta 
nondeterministica e si ri-eliminano le configurazioni divenute 
inconsistenti. In backtracking si trovano tutte le soluzioni.
Ciao ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli

 ricerca).
Ho riguardato come si fa; ho trovato una bella spiegazione su 
P. Flener et al., "Breaking Row and Column Symmetries in Matrix Models", 
Principle and Practice of Constraint Programming - CP 2002, 8th 
international conference, Lecture Notes in Computer Science 2470, 
Springer Verlag.
Essenzialmente, si generano tutte le (5!)^2 permutazioni di riga e 
colonna, se ne sceglie una, si "appiattisce" la matrice in un vettore 
monodimensionale di 25 variabili. A questo punto, si impone un 
ordinamento lessicografico fra le variabili del vettore e le 
corrispondenti variabili di tutte le permutazioni del vettore.
Cerco di spiegarmi meglio, mettiamoci in un cso piu` semplice, matrice 
2x3. Ci sono 2! * 3! permutazioni riga/colonna. Chiamiamo gli elementi 
della matrice:
	X1	X2	X3
	X4	X5	X6
Allora creo un vettore di variabili
	[X1,X2,X3,X4,X5,X6]
se scambio le 2 righe ottengo:
	[X4,X5,X6,X1,X2,X3]
impongo allora un odinamento lessicografico:
	[X1,X2,X3,X4,X5,X6] <= [X4,X5,X6,X1,X2,X3].
Analogamente per le altre 2! * 3! -1 permutazioni.
Imponendo tutti questi vincoli di Symmetry Braking, in 56.47 secondi, 
ECLiPSe fornisce 21 soluzioni, che riporto di seguito. Tutte le altre 
dovrebbero essere simmetriche.
Ciao ciao,
Marco
. . . A B 
. . . A B 
. . . B A 
A A B B . 
B B A . A 
. . . A B 
. . . A B 
. . A B . 
A B . B A 
B A B . A 
. . . A B 
. . . A B 
. . B . A 
A B . B A 
B A A B . 
. . . A B 
. . . A B 
. A B . . 
A B . B A 
B . A B A 
. . . A B 
. . . B A 
. . A . B 
A A B B . 
B B . A A 
. . . A B 
. . . B A 
. . A . B 
A B . B A 
B A B A . 
. . . A B 
. . . B A 
. . B . A 
A A . B B 
B B A A . 
. . . A B 
. . . B A 
. . B . A 
A B . A B 
B A A B . 
. . . A B 
. . . B A 
. A A B B 
A . B . . 
B B . A A 
. . . A B 
. . . B A 
. A B . . 
A B . A B 
B . A B A 
. . . A B 
. . A . B 
. . A B . 
A B B . A 
B A B . A 
. . . A B 
. . A . B 
. A . B . 
A . B B A 
B B . A A 
. . . A B 
. . A . B 
. A . B . 
A B . B A 
B . B A A 
. . . A B 
. . A . B 
. A B B A 
A B . B A 
B . . A . 
. . . A B 
. . A B . 
. . B . A 
A A . B B 
B B . A A 
. . . A B 
. . A B . 
. . B . A 
A B . A B 
B A . B A 
. . . A B 
. . A B . 
. A B . . 
A . B B A 
B B A A . 
. . . A B 
. . A B . 
. A B . . 
A B A B . 
B . B A A 
. . . A B 
. . A B . 
. A B . . 
A B B A . 
B . A B A 
. . . A B 
. . A B . 
. A B B A 
A B B A . 
B . A . . 
. . . A B 
. . A B . 
. B A . . 
A A B B . 
B . B A A 
--
http://www.ing.unife.it/docenti/MarcoGavanelli