N queens problem

Il problema consiste nel riempire una scacchiera n*n con n regine in modo che nessuna minacci l'altra.

Qui potete trovare il problema nella sua forma originale
http://mathworld.wolfram.com/QueensProblem.html

Invece qui potete trovare la sequenza di numeri interi che indica quante soluzioni (comprese di rotazioni e riflessioni) ottenete al variare di n
http://www.research.att.com/~njas/sequences/A019654

Quello che vi voglio illustrare adesso è un algoritmo (attualmente in fase di sperimentazione) che vi consente di trovare una soluzione per una scacchiera (n*n) * (n*n) a partire da una soluzione per una scacchiera n*n.

Per praticità vi illustro l'algoritmo con una soluzione già trovata

Disegnate una scacchiera 5*5.

Un teorema di Fermat afferma che ogni numero primo nella forma 4n+1 può essere scritto come somma di due quadrati.
Una classe di soluzioni per il problema delle n regine è data da questa scomposizione
http://demonstrations.wolfram.com/Fermats4n1TheoremAndTheNQueensProblem/

Prendiamo la soluzione per n=5 nel modo descritto nella pagina di sopra e disegnamo la scacchiera 25*25.
Una volta disegnata la scacchiera 25*25 possiamo trovare una soluzione per questa scacchiera a partire dalla scacchiera 5*5!

Quello che dovete fare è riempire la scacchiera 25*25 nel seguente modo.

Potete immaginare la scacchiera 25*25 divisa in 25 scacchiere 5*5.
Ogni settore avrà una posizione x,y all'interno della nostra scacchiera.
Adesso guardate la scacchiera 5*5 e vedete in quale posizione avete inserito la regina,la posizione della regina determina la posizione del settore che dovete riempire.

Se ad esempio vedete una regina nella posizione 2,1 sapete che dovete riempire il settore 2,1 con la soluzione della scacchiera 5*5.
Ripetete questo procedimento fino a quando esaurite tutte le regine nella scacchiera 5*5 e se avete seguito bene le istruzioni avete ottenuto una soluzione per la scacchiera 25*25!

La mia ipotesi è che si possa applicare questo algoritmo per n>4,se provate ad eseguire questo algoritmo per n=4 non riuscirete a trovare una soluzione per n=16.

La mia ipotesi è:
Data una qualsiasi soluzione per il problema delle n regine,con n>4 è possibile trovare una soluzione per il problema delle n*n regine.

Ma è possibile che per altri n l'ipotesi non sia verificata
Detto questo vi saluto,e buon divertimento! :)