Newsgroup: it.hobby.enigmi
Titolo: Un'enigma che mi sembra molto difficile

Ci sono 12 soluzioni diverse, escludendo rotazioni e riflessioni, per una
scacchiera 8x8. Ve ne sono 2 con una regina nell'angolo. Una è quella
illustrata qui sotto. L'altra?
ciao cesare
o o o o o o o x
o x o o o o o o
o o o o x o o o
o o x o o o o o
x o o o o o o o
o o o o o o x o
o o o x o o o o
o o o o o x o o

E' un problema scacchistico. Empiricamente, si dimostra che e'
possibile, io cercavo di trovare un modo matematico per dimostrarlo,
ma mi sembra che ci siano molte variabili e troppi calcoli.
Allora: quello empirico consiste nel riusicre a mettere 8 regine su
una scacchiera, in modo tale che nessuna possa essere catturata da
un'altra. Ed e' possibile.
Mi chiedevo appunto se esiste un ragionamento puramente matematico,
che stabilisse che su una scacchiera le regine che si possono mettere
senza catturarsi sono al massimo 8.
Avevo impostato anche un modello di ragionamento ma mi sono fermato
subito perche' veniva spropositatamente complesso.
La mia dimostrazione si basava sul calcolo delle case controllate
dalla regina.
Se calcolassimo le case di controllo di una regina posta su una
qualsiasi casa della scacchiera, potremmo dire, essendo la scacchiera
di 64 caselle, quante regine entrano trovando un posto libero e quindi
non stando su una casa gia' controllata da un'altra regina,
solo che ci sono dei gravi problemi:
1) la regina controlla piu' case al centro (28), man mano che si
sposta verso il bordo ne controlla sempre di meno ; per cui non si
puo' stabilire un unico numero e moltiplicarlo per 8.
2) Tra due regine poste sulla scacchiera che non si possono mangiare 
tra loro esistono da un minimo di 2 ad un massimo di 5 caselle che
controllano in comune. Questo numero andrebbe sottratto dal conto
totale.
Insomma: determinare se 8 donne possono stare su una scacchiera e' un
casino.
Qualcuno puo' aiutarmi a cavare un ragno dal buco?
Tenete presente che tutti questi ragionamenti li ho fatti da solo, per
cui se c'e' qualcosa di sbagliato non punitemi a sangue. :)
 

puo' stabilire un unico numero e moltiplicarlo per 8.
Al centro ne controlla solo 27... infatti sono 7 sulla riga, 7 sulla
colonna, 7 sulla diagonale e solo 6 sull'altra diagonale (una delle due
non e' la diagonale maggiore, per forza).
[...]
Comunque carino: si potrebbe provare ad espanderlo, anche se non e'
facile...
Ciauz, Gabry :-)
-- 
 _                        _   _
( )                      ( ) ( )   
http://poisson.dm.unipi.it/~stilli/
| |                      | |/ /
| |                      |   <
| |__                    | |\ \
(____)   I   G   H   T   (_) (_)   N   I   G   H   T

 senza catturarsi sono al massimo 8.
Una regina controlla tutte le caselle della riga in cui si trova,
quindi in ogni riga ci puo' stare al massimo una regina. Le righe
sono 8, quindi al massimo ci possono stare 8 regine. In generale
su una scacchera n x n, ci possono stare al massimo n regine senza
mangiarsi.
Domanda: Si puo' dimostrare che per n > 4, si riescono sempre a
sistemare n regine su una scacchiera n x n, senza che si mangino?
	Mauro



Devi considerare anche le diagonali...!
Quanto hai detto sopra non puo' essere vero, perche' in una scacchiera
5 x 5 non puoi collocare 5 regine senza che si mangino!!!

facile...
Facile?... Tutt'altro!!!
 
 

5 x 5 non puoi collocare 5 regine senza che si mangino!!!
No, ci si riesce invece, guarda qua:
. . . R .
. R . . .
. . . . R
. . R . .
R . . . .
In una scacchiera 4x4 invece, non si possono collocare 4 
regine, e nemmeno 3 in una 3x3 e nemmeno 2 in una 2x2.
Ciao!
Maurizio Mascheroni
===================================================
Maurizio Mascheroni        
mask...@mailbox.icom.it
---------------------------------------------------
La Mecca - Chess Encyclopedia:
 
http://www.maskeret.com/mecca
Blip - Blitz Press Release (News from the world):
 
http://www.maskeret.com/blip
Chess in Italy and much more:
 
http://www.maskeret.com/micio
L'Italia Scacchistica, chess magazine:
 
http://www.maskeret.com/italiascacchistica
Franco Romagnoli, chess shop:
 
http://www.maskeret.com/romagnoli
===================================================


E invece il 4x4 si puo' fare:
 . Q . .
 . . . Q
 Q . . .
 . . Q .
Credo che sia anche l'unica soluzione, a meno di rotazioni e riflessioni.
E' anche bella simmetrica, il che non guasta :-)))
Ah, confermo: 3x3 e 2x2 sono impossibili comunque.
A Mauri', come mai 'sta sortita scacchistica "in trasferta" ? :-)))))


 5 x 5 non puoi collocare 5 regine senza che si mangino!!!
Basta metterle in  a1, b3, c5, d2, e4  oppure  a2, b5, c3, d1, e4
oppure rotazioni e riflessioni di queste 2 soluzini (totale 10).
	Mauro

A Mauri', come mai 'sta sortita scacchistica "in trasferta" ? :-)))))
Gli scacchi non sono il mio unico interesse, per mio fortuna :-)))
e allora ogni tanto seguo anche altri newsgroup: non e' la
prima volta che intervengo qui, anche se le ultime sono
talmente in la' nel tempo che non me le ricordo piu'.
Per tornare al problema delle 8 regine, segnalo che c'e'
un breve articolo a riguardo nel sito dell'Italia Scacchistica:
http://www.maskeret.com/italiascacchistica/a_ottodonne.htm
Tra le altre cose, ci sono tutte le 12 posizioni possibili


 5 x 5 non puoi collocare 5 regine senza che si mangino!!!
??  Ci sono 2 distinte soluzioni.
Eccone una:
- * - - - 
- - - * -
* - - - -
- - * - -
- - - - *
Ma ragazzi !!  e' un problema notissimo, fu proposto per la prima volta
da un tale Bezzel nel 1848, se ne interesso' perfino il grande Gauss.
Una cosa diversa e' invece contare quante siano le soluzioni per una
scacchiera di ordine n (caselle di un lato). Ecco i risultati
conosciuti, non considerando rotazioni e riflessioni:
ordine       num. di soluzioni
 4              1
 5              2
 6              1
 7              6
 8             12
 9             46
10             92
11            341
12           1787
13           9233
14          45752
15         285053
16        1846955
17       11977939  			
a presto
dario

 ma mi sembra che ci siano molte variabili e troppi calcoli.
Varie persone hanno risposto sulle varianti del problema, Dario ha gia'
risposto, quindi non resta molto da dire. :-)
Solo che e' stato dimostrato che il problema (n regine su scacchiera nxn)
e'
sempre
risolubile per n>= 4. La dimostrazione e' costruttiva, nel senso che
indica come
disporle. Si basa sul mettere le regine in fila "a salto di Cavallo":
guardate le
soluzioni per la 5x5 e potete farvi un'idea di come espandere lo schema.
Servono strategie leggermente diverse a seconda del valore di n mod 6, con
lievi differenze nel mettere una regina vicino al centro o in un angolo e
nel
ruotare di 180 gradi uno schema per mezza scacchiera per completare
l'altra meta'.
In questo modo e' stata costruita una soluzione record, per una scacchiera
di
lato 3.000.000, in tempi brevi (il tempo di calcolo e' lineare rispetto
all'ordine).
Non esiste invece una formula nota per il numero di soluzioni possibili al
variare di n.
Come il buon senso suggerisce, al crescere di n il numero di soluzioni
aumenta;
la crescita sembra esponenziale, ma non e' stato dimostrato.
Il problema si complica se le regine diventano Amazzoni (muovono anche
come
il cavallo). La minima soluzione e' su scacchiere di ordine 10, sembra che
si possa
risolvere per n >=10, ma non sono riuscito a trovare una strategia per le
scacchiere di ordine 6n+2 e 6n+3 (le altre sono facili). Mi sembra che una
parte di
queste sia stata risolta (sicuramente per n piccolo), ma qui mi fermo.
Ciao
Mauro Fiorentini

 Mauro Fiorentini
Mauro, ho un ottimo programma scritto da Francesco Balena che genera e
conta tutte le sol. per regine e amazzoni. Vedi MC Microcomputer 131
luglio/agosto 1993.
Il num. di soluzioni per le amazzoni per gli ordini da 10 a 20 sono:
10   1
11   6
12   22
13   239
14   653
15   4089
16   25411
17   166463
18   1115871
19   8062150
20   61984976
dario

 dario
Ho scritto anche io un programma. Grazie dei numeri, cosi' controllero' le mie
soluzioni.
Quello che volevo dire e' che, sebbene buon senso ed evidenza sperimentale
suggeriscano che per n >= 10 il problema per le amazzoni sia sembre risolubile,
manca una dimostrazione per i casi 6n+2 e 6n+3. Col mio programma ho
trovato e contato le soluzioni per 14, 15, 20 e 21 e mi sembra che qualcuno
abbia
risolto qualche altro caso (12n+2, forse), ma non conosco una strategia generale
per le Amazzoni, mentre per le regine ne esistono parecchie, che insieme coprono
tutti i casi con n>=4.
Stampando tutte le soluzioni per n = 14, ne ho cercata qualcuna "regolare", che
potesse essere estesa ad altri casi, senza successo.
Aggiungo una congettura, assolutamente ovvia.
Con il vincolo che 2 regine non possano trovarsi a distanza (euclidea) < k
(reale),
esiste un n0 tale che per n >= n0 il problema e' sempre risolubile.
Le amazzoni solo un caso particolare con k = sqrt(5) e n0 = 10.
Non conosco nessun risultato, sperimentale o teorico, in questo senso.
Qualcuno vuol provare a calcolare n0 per i primi valori di k?
(k = sqrt(8), k = sqrt(10), k = sqrt(13) ecc.)
Buon lavoro
Mauro Fiorentini

 dario
Mannaggia. Il mio programma non elimina le soluzioni identiche per
rotazioni/riflessioni.
di conseguenza ho valori circa 8 volte superiori.
Do l'elenco per chi fosse interessato.
10:    4
11:    44
12:    156
13:    1876
14:    5180
15:    32516
16:    202900
17:    1330622
18:    8924976
19:    64492432
20:    495864256
Per l'ordine 20 mi e' servito un giorno e mezzo di calcolo.
Ciao
Mauro