Newsgroup: it.scienza.informatica
Titolo: Problema delle 9 regine

Conoscete il problema delle 8 regine? Bene io vorrei se qualcuno e' a
conoscenza di una dimostrazione che
per ogni n il problema delle n regine e' risolubile.

per ogni n il problema delle n regine e' risolubile.
suppongo sia sufficiente procedere per induzione...
Ciao,
Fabio Alemagna

Fabio Alemagna wrote:

  No.

...

di quanti tasselli è formata la scacchiera? 

tita wrote:

  Qual e' l'ipotesi induttiva? E come la usi nel caso induttivo

per ogni n il problema delle n regine e' risolubile.
??? se per "n" intendi contemporaneamente il numero delle regine e
delle colonne, allora come puoi immaginare non puoi far stare due
regine in una scacchiera 2*2. E nemmeno tre regine in una scacchiera
3*3. Quindi il problema parte male. Non ho mai pensato a scacchiere
9*9 con nove regine e non trovo piu' il pgm che avevo scritto per la
soluzione classica del 8*8. Se ho tempo ci faccio una pensata. 
Ciao, Francesco 

Dovresti specificare meglio cosa intendi con n,
comunque il problema delle otto regine e' il tipico
problema che si risolve per via iterativa, provando
tutte le combinazioni a mano, o meglio facendolo fare
ad un programma. Se ti interessa devo avere da qualche
parte il programma C che risolve il problema per le
solite 8 regine. E' molto facile estenderlo a n (sempre
sapendo cos'e' n) e vedere se funziona.

Fracasso Gian Luca wrote:

  Lo conosco benissimo. Quello che io voglio e' non un programma che
trova la soluzione,
dato che esistono ottime euristiche, e si e' giunti a risolvere il
problema per n molto grande. Io voglio
sapere se: esiste un n tale che per ogni n' > n il problema nelle n'
regine e' risolubile. Come puoi ben capire
e' ben diverso dal scrivere un semplice programmino. I programmi prima
si scrivono, e poi si dimostra
che funzionano. Questa e' l'informatica come scienza ( vedi thread "Sul
NG" ).

regine e' risolubile
in base alla definizione di limite non esiste (ripeto non so se ho centrato
il problema, quindi posso benissimi sbagliarmi).
ciao

NG" ).
Continua a non essere chiaro cosa tu intendi per "n".
E' solo il numero di regine oppure e' *anche* il numero dei lati di
una scacchiara quadrata?
In secondo luogo, e' bene che tu precisi che tipo di soluzione vuoi
(logica, algoritmica, matematica ....)
Ad esempio, buttiamo le regine o trasformiamole in torri.
Ci vuole poco a capire che per ogni scacchiera di lato "n" si possono
mettere "n" torri. Salendo il numero dei lati, le torri saranno sempre
di pari numero ma salgono di parecchio le "COMBINAZIONI". 
Questo e' logica intuitiva ma non ancora matematica. Sempre nella
logica intuitiva posso dire che se la nostra scacchiera, occupata da
torri, fosse di 2 per 1000, le torri sarebbero sempre due (idem per le
regine). Esiste quindi un fattore limitante che e' dato dal lato piu'
corto. In una scacchiera 2*2 non ci stanno due regine ma ci stanno in
una scacchiera 2*3 (due soluzioni). Perche'? Perche' in una scacchiera
2*2 ci sono due colonne, due righe e due diagonali mentre in una 2*3
ci sono due colonne, tre righe e 4 diagonali e cio' da' spazio per due
soluzioni. La nebbia si dirada? Si' perche' il discriminante e' il
numero delle diagonali, oltre al lato piu' corto. Ma il numero delle
diagonali cresce molto di piu' di quello dei lati. In una scacchiera
2*2 ci sono 2 diagonali. In una di 3*3 ce ne sono sei. Dieci in una
4*4. La formula e' quindi ((Latox-1)+(Latoy-1))*2 ed in una scacchiera
di 8*8 ci sono quindi 28 diagonali che attraversano 64 celle. Se il
fattore limitante "diagonale" cresce piu' del fattore limitante "lato"
allora non dubito che esista un nuero "n" di lati oltre il quale c'e'
sempre una soluzione. 
Ciao, 
Francesco F. 

per ogni n il problema delle n regine e' risolubile.
A conoscenza no, ma ci si puo' tentare. Come dicevo il problema
limitante e' il numero di colonne ed il numero di diagonali. 
Il primo e' direttamente il nostro "n" mentre il secondo e'
calcolabile come: C = (((n - 1) + (n - 1))-1)*2 ed e' il numero delle
colonne che atraversano una scacchiera n*n. Poi c'e da calcolare D
come il numero di colonne che n regine occupano in una scacchiera n*n.
Ora come tutti possono immaginare, le regine occupano due diagonali
cadauna, salvo una ed una sola, che se viene messa in un angolino,
occupa la diagonale piu' lunga. Nessun'altra la puo' imitare e la cosa
e' palese. Quindi il nostro D e' pari a ((n-1)*2)+1 
Una caratteristica delle nostre regine e' di non occupare la stessa
riga (e' una cosa intollerabile per le regine) e quindi direi che
possiamo calcolare un indice I pari a (C - D - n) che rappresenta i
gradi di liberta' di una scacchiara n*n per n regine. Chiunque abbia
excel od equivalente si puo' industriare come puo' per fare i calcoli.
Come vedete I comincia ad essere maggiore di zero per n = 6 poi sale
sempre in modo lineare. Ad ogni n+1, I si incrementa di una unita' e
quindi ci dice che per n che vale da 6 in su, la soluzione e' sempre
valida. Non solo, ma moltiplicando I * n abbiamo, a mio avviso quante
siano le soluzioni del probelema per ogni "n". Per le 8 regine infatti
I vale 3 e quindi le soluzioni sono 24. Quando avevo fatto il
programma nel '91 mi aveva dato prorio 24 ma non c'era internet e non
potevo confrontarmi con nessuno. Non so nemmeno se quella soluzione
empirica (classico algoritmo esaustivo e ricursivo)  scritta in C
(ebbene si', lo confesso) fosse giusta o no e colgo l'occasione per
avere una conferma. 
Se qualcuno sospetta od afferma che ho solo moltiplicato l'eta del
capostazione di Poggibonsi per il numero di regine meno il numero di
colonne lo dica apertamente :-)) o taccia per sempre. ^__^ 
Best regards,
Francesco Forti

e' palese. Quindi il nostro D e' pari a ((n-1)*2)+1 
Ho verificato poi che questo e' il numero minimo. E' pero' possibile
mettere n regine in modo che occupino 2n colonne. 
In questo caso e' possibile avere soluzioni proprio perche' non si
occupano le due diagonali piu' lunghe. In ogni caso, il numero delle
diagonali occupate cresce sempre meno del numero delle diagonali
disponibili e questo credo sia abbastanza per la dimostrazione che
l'altro Francesco cerca. 
Saluti, Francesco 

scusate la mia ironia e ignoranza, ma le regine erano 8 o 9?
C'e' il problema delle 8 regine nella scacchiera tradizionale 8x8 ma
si puo' pensare alla soluzione di un problema di 9 regine in una
scacchiera 9x9 e via dicendo. Chi ha aperto il thread si chiedeva se
c'era una soluzione matematica valida per "n" che vale da un tot in
su. 
Ciao, Francesco F.

su.
Thanks'.
(allora niente programma per fare concorrenza all' IBM !?!).


Francesco Forti
================================= (2) ============================


Credo che il "massimo" esperto di questo problema sia Corrado Giustozzi di
MCMicrocomputer. Il suo articolo di una decina di anni fa su di un programma
per Texas TI58 proprio sul problema delle regine gli valse l'assunzione ad
MC ...
Prova una mail al sito Web di MC, di solito e' molto cortese e risponde a
tutti.
______________________________________________
Cesare G. Rossi - Ross Software, Inc.
Microsoft Certified Sales Specialist
Microsoft Certified Professional + Internet
Microsoft Certified System Engineer
Microsoft Certified Trainer
Global Knowledge Network Certified Security Engineer
______________________________________________
