il Problema delle N Regine

Il problema delle 8 Regine, proposto per la prima volta nel 1848 da Max Bezzel, richiede di disporre 8 regine su una scacchiera, in modo che nessuna sia minacciata da un'altra (considerando che la Regina si muove in orizzontale, Verticale e Diagonale).
Il problema si può estendere a una scacchiera NxN, su cui disporre N regine.

Escludendo il caso banale di una regina su una scacchiera di una sola casella, il Lato deve essere almeno di quattro caselle per trovare una soluzione (2 disposizioni simmetriche).
Il numero delle soluzioni cresce al crescere del Lato.

Struttura dati

La scacchiera dovrebbe essere allocata in una matrice NxN, con righe e colonne da 1 a Lato.
Per velocizzare le operazioni, però, la scacchiera verrà solo immaginata nella fase di analisi e non corrisponde ad una reale variabile in memoria: la posizione delle Regine viene controllata tramite quattro array monodimensionali.

int Colonne [ ] segnala le colonne occupate dalle Regine
int Destre  [ ] segnala le diagonali principali occupate
int Sinistre[ ] segnala le diagonali secondarie occupate
int Casa     [ ] riporta le posizioni di ogni regina, una per rigo;
è usato solo per la visualizzazione della soluzione

Le case di una diagonale destra hanno costante la differenza tra gli indici.
Le case di una diagonale sinistra hanno costante la somma degli indici.
Le diagonali sono in numero quasi doppio rispetto alle righe e alle colonne, andranno quindi dimensionate adeguatamente.
Nei tre array 0 indica la linea libera, 1 indica la linea occupata.

int   Lato lato della scacchiera e numero delle Regine
long Totale numero delle soluzioni trovate

Per velocizzare le operazioni, le variabili sono dichiarate globalmente.

Algoritmo

Il calcolo si basa sull'uso della funzione ricorsiva Regine():

  1. la funzione riceve il rigo su cui operare (valori da 1 a Lato);

  2. tenta di posizionare una Regina sul rigo alle colonne da 1 a N, verificando che non siano già occupate la colonna, la diagonale destra o la diagonale sinistra.

  3. ad ogni regina posizionata correttamente, viene chiamata ricorsivamente la stessa funzione per il rigo sottostante;

  4. sul rigo = Lato, la ricorsione termina e viene segnalata una nuova disposizione.

Codice Sorgente in C

Il programma è stato scritto in linguaggio C per compilatore Borland 3.1, ma può essere facilmente adattato ad un qualsiasi compilatore.
Potete scaricare direttamente l'eseguibile di soli 13 Kb.

Considerazioni finali

I tempi di calcolo sono notevolmente allungati dalla visualizzazione continua delle soluzioni; per analizzare qualche soluzione occorre fermare l'esecuzione con il tasto Pausa.
Eliminando dal programma la chiamata alla Sub VediSoluzione(), i tempi si riducono drasticamente: per trovare tutte le disposizioni di 15 Regine su una scacchiera con lato 15 (oltre due milioni) bastano circa 20 secondi. In ogni caso il tempo di calcolo cresce di un fattore 7 (circa) ad ogni incremento del lato.

Software didattico