Newsgroup: it.hobby.enigmi
Titolo: Griglia mista (problema combinatorio)

Ho un problemino con cui mi stò arrabbattando senza molto successo. 
Sto cercando un modo per attaccarlo ma con le (poche) armi a mia disposizione non sono riuscito a venirne a capo. 
In generale ho una griglia n*n (n>2) in cui devo disporre secondo alcune regole dei pallini in modo da occupare una una cella della griglia. 
le regole sono semplici: 
1) la diagonale principale (altosinistra-bassodestra) non è "occupabile" dai pallini 
2) ogni riga ed ogni colonna deve avere esattamente 2 pallini 
3) non possono esistere due righe in cui i pallini sono disposti alla stessa maniera e lo stesso per le colonne 
 
La mia domanda è, quante disposizioni "lecite" esistono ? 
Ho come l'impressione che la simmetria abbia a che fare on questo problema ma non riesco a trovare una regola come già scritto.

Addi' 28 ago 2017, Emanuele Bonin scrive:

Per vedere se ho capito, questa (unica!) 3x3 e' ok?
 
| .  *  * |
| *  .  * |
| *  *  . |
 
Se si', allora "Per n = 3, disp = 1", e tu vuoi qualcosa come una
formula che da' il numero delle disp lecite in funzione di n ?
Be' se e' cosi' non e' mica facile, per n=4 ce ne sono gia' molte..
 
-- 
bye, Yoda
 

Esatto. È proprio quello che stavo cercando. Lo so che non è facile ma sospetto che no  siano tanti quanto pensi per 4 se applichi le regole . Come scritto in precedenza penso che ci debba essere una sorta di regola sulla simmetria tra le due parti divise dalla diagonale maggiore.

 Esatto. È proprio quello che stavo cercando. Lo so che non è facile ma sospetto che no  siano tanti quanto pensi per 4 se applichi le regole . Come scritto in precedenza penso che ci debba essere una sorta di regola sulla simmetria tra le due parti divise dalla diagonale maggiore.
 
In effetti nella griglia 4x4 le soluzioni non sono tante: 6 senza contare le simmetrie, 4 se contiamo le simmetrie:
 
1)
XOOX
XXOO
OXXO
OOXX
 
 
2)
XOOX
OXXO
XOXO
OXOX
 
3)
XOXO
OXOX
OXXO
XOOX
 
4)
XOXO
XXOO
OOXX
OXOX
 
5)
XXOO
OXOX
XOXO
OOXX
 
6)
XXOO
OXXO
OOXX
XOOX
 
La 2 e la 3 sono la stessa soluzione ruotata di 180° così come anche la 1 e la 6 (invece la 4 e la 5 "ruotano su se stesse").
 
Non tante soluzioni per la 4x4, in effetti.
 
Ma già per la 5x5 le soluzioni esplodono: a mano ho trovato 27 soluzioni solo per la disposizione della prima riga come
XOOXX
 
e ci sono altre 5 disposizioni possibili per la prima riga. Quindi diverse decine di soluzioni per la 5x5.
 
Penso che per trovarle serva un programmino, non penso infatti che tirare fuori una soluzione analitica per qualsiasi n sia possibile visti i vincoli così particolari (forse rilassando la condizione sulla diagonale...)
 
Ciao
GaS

Addi' 29 ago 2017, GaS scrive:

Commento senza contare le simmetrie.
 
Traduco in termini di 0 e 1.
La diagonale principale e' sempre di tutti zeri per regola di gioco,
dunque uno zero indica posto vuoto, mentre l'uno indica la pallina.
 
Inoltre metto uno spazio che serve per visualizzare a colpo d'occhio
tutte le diagonali secondarie, e quindi vedere gli elementi simmetrici
rispetto alla diagonale principale.
 
1)
0 1 1 0
0 0 1 1
1 0 0 1
1 1 0 0
 
2)
0 1 1 0
1 0 0 1
0 1 0 1
1 0 1 0
 
3)
0 1 0 1
1 0 1 0
1 0 0 1
0 1 1 0
 
4)
0 1 0 1
0 0 1 1
1 1 0 0
1 0 1 0
 
5)
0 0 1 1
1 0 1 0
0 1 0 1
1 1 0 0
 
6)
0 0 1 1
1 0 0 1
1 1 0 0
0 1 1 0
 
Ebbene, tutto questo per dire che NESSUNA delle sei soluzioni presenta
simmetria rispetto alla diagonale principale.. sara' un indizio? - ciao!
 
-- 
bye, Yoda
 

 simmetria rispetto alla diagonale principale.. sara' un indizio?
 
Non penso che sia un "indizio", ma semplicemente perchè la soluzione per la griglia 3x3 è simmetrica rispetto alla diagonale principale e anche per la 5x5 ci sono soluzioni simmetriche, ad es.:
 
0 1 1 0 0
1 0 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 0 1 0
 
 
Ciao,
GaS

 bye, Yoda
Hai ragione, ma quando scrivevo di una sorta di legge di simmetria i riferivo al fatto che per esempio nella griglia 4 x 4 "piegando" la diagonale maggiore sovrapponendo i due "lembi" e osservando se la disposizione degli 0 e 1 che si sovrappongono ci sono sempre (per ogni configurazione) 4 punti "opposti" e due uguali.
 

 configurazione) 4 punti "opposti" e due uguali.
 
Be' ma io l'ho notato perche' la condizione di tutti zeri sulla
diagonale principale e' una caratteristica delle matrici quadrate
antisimmetriche, percio' ho guardato.
 
Comunque magari vale solo per l'ordine pari, GaS ha guardato la 3 e le 5,
poi provero' a trovare una 6 simmetrica.. e una 5 non simmetrica ciao
 
 
-- 
bye, Yoda
 

La mia era solamente una supposizione che si sta rivelando un granchio. In effetti al crescere di n ci sarà tanto di quello spazio che i giochi di simmetria saranno l'eccezione e non la regola

 Penso che per trovarle serva un programmino
 
Programmino fatto, non molto veloce ma ha trovato 156 soluzioni per la 5x5, adesso sta girando per la 6x6, vi faccio sapere i risultati in serata (sempre se qualcuno sia interessato... :-)
 
Il programma NON conta le simmetrie rotazionali (quindi trova 6 soluzioni per la 4x4).
 
Ciao
GaS

"GaS"  ha scritto nel messaggio 
news:74463428-774f-45be...@googlegroups.com...

Ho fatto anch'io il programmino. Mi sembra più veloce del tuo. ;)
 
4 -> 6
5 -> 156
6 -> 5620
7 -> 269130
8 -> 16616796
 
e così via.
 
Ciao.
 
Giorgio
 

"Giorgio Vecchi"  ha scritto nel messaggio 
news:oo68mt$1iue$1...@gioia.aioe.org...
 
Dato che il programmino c'è, lo sfrutto un po'.
 
Questi sono i conteggi delle soluzioni (incluse eventuali rotazioni, ecc.) 
ottenute variando la dimensione della griglia e il numero dei pallini:
 
3, 2 -> 1
4, 2 -> 6
4, 3 -> 1
5, 2 -> 156
5, 3 -> 24
5, 4 -> 1
6, 2 -> 5620
6, 3 -> 6030
6, 4 -> 160
6, 5 -> 1
7, 2 -> 269130
7, 3 -> 1616880
7, 4 -> 290340
7, 5 -> 1140
7, 6 -> 1
8, 2 -> 16616796
8, 3 -> 635155465
8, 4 -> 653128560
8, 5 -> 18515385
8, 6 -> 8988
8, 7 -> 1
 
E questi sono i conteggi imponendo anche il vincolo di non occupabilità 
della seconda diagonale:
 
5, 2 -> 16
6, 2 -> 432
6, 3 -> 80
7, 2 -> 28992
7, 3 -> 38464
7, 4 -> 864
8, 2 -> 1409472
8, 3 -> 11105408
8, 4 -> 1634304
8, 5 -> 4752
 
Ciao.
 
Giorgio
 
 

Effettivamente anche a me sono risultati questi numeri (programmino in c sharp).

Questi risultati non sono miei:
3 1 
4 6 
5 156 
6 5620 
7 269130 
8 16616796 
9 1302305536 
10 126169436016 
11 14802593296140 
12 2069271914687560 
13 339915497582948496 
14 64837968520335428496 
15 14214382941525362069656 
16 3549527421297391994169360 
17 1001677426115759811101034240 
18 317219478762148442235395675776 
19 112034824611937954683531536904336 
20 43880470950820929237567549934682976