Il problema delle 8 regine
Il problema delle 8 regine è un problema matematico che consiste nel trovare il modo posizionare otto regine su una scacchiera in modo che non si possano mangiare tra di loro, quindi in modo che nessuna si trovi sulla stessa riga o colonna o su una delle diagonali occupata da un altra.
E’ un problema molto noto in letteratura perchè è stato usato più volte per la didattica della programmazione.
- Viene proposto per la prima volta da Max Bezzel, uno studioso di problemi scacchistici, nel 1848.
- Viene risolto per la prima volta nel 1850 da Franz Nauck (non ho idea di chi sia).
- Viene studiato, nelle sue versioni generalizzate, da molti altri matematici incluso Carl Friedrich Gauss ( lui c’entra sempre. Gauss è il Chuck Norris della matematica. Gauss può uccidere Chuck Norris con un calcio rotante).
- Nel 1972 fu usato da Edsger Wybe Dijkstra per illustrare una tecnica fondamentale di programmazione (il backtrack).
- Sempre nel 1972 Niklaus Wirth lo usa come “toy problem” nel suo famosissimo paper “Program Development by Stepwise Refinement”.
Cominciamo dal principio, tralasciando l’algoritmica per ora.
Avete davanti una scacchiera vuota e 8 regine come fate a piazzarle?
Per comodità consideriamo l’insieme delle caselle come un insieme ordinato di 64 posizioni, questo ci consentirà di rendere un insieme ordinato anche quello delle soluzioni. Piazziamo la prima regina sulla locazione 1 e poi spostiamoci lungo le caselle piazzando una regina ogni volta che sia possibile, arriviamo in questo modo alla situazione illustrata nel Diagramma1.
Diagramma 1
A questo punto abbiamo un problema: l’ultima pedina è impossibile da piazzare!
considerato che sappiamo per certo che delle soluzioni devono esistere possiamo concludere che almeno una di quelle regine si trova in una posizione sbagliata , come procedere allora?
Andiamo indietro di una pedina e cerchiamo se la 7 ha altre posizioni in cui essere piazzata (sapendo che ci deve essere una regina in ogni riga abbiamo 2 posizioni da controllare), ci rendiamo conto che anche lei non ne ha, allora togliamo la 7 e lavoriamo sulla 6, ma anche lei non ne ha di disponibili e quindi torniamo alla 5, e così via fino a trovare alternative. una volta trovata un alternativa si rimpiazzano le pedine che abbiamo tolto a partire dalla nuova configurazione trovata e se da essa non ci sono soluzioni valide per tutte le 8 pedine torniamo di nuovo indietro fino a trovarne.
Eseguendo questo procedimento possiamo arrivare alla prima soluzione che si trova molto lontano da quella da cui sono partito, è quella mostrata nel Diagramma2.
Diagramma 2
Backtrack
Il procedimento appena descritto si chiama backtrack, è può essere sintetizzato nella frase
“Prova a fare qualcosa, se non funziona torna indietro e riprova qualcos’altro”
è un procedimento molto generico che permette di risolvere molti problemi, anche se non è molto veloce per l’alto numero di combinazioni provate.
Adesso cerchiamo di formalizzare il problema per costruire un algoritmo capace di risolverlo Cominciamo dalla definizione della singola soluzione accettabile, che è composta da due vincoli:
- La scacchiera deve contenere 8 regine
- Nessuna delle regine deve essere capace di mangiarne un altra
A questo punto cominciamo a utilizzare il modello per trarne le proprietà che ci permetteranno di costruire l’algoritmo.
- Ci potrà essere solo una regina in ogni riga, quindi ogni riga contiene necessariamente 1 regina
- Lo stesso principio vale per le colonne, quindi ogni colonna contiene necessariamente 1 regina
- Nella scacchiera esistono 15 diagonali crescenti ,considerando diagonali anche il caso degenere delle singole caselle agli angoli, e ognuna di esse potrà contenere al massimo una regina, questo significa che ci saranno 7 diagonali libere e 8 occupate ( definiamo crescente una diagonale con verso concorde sia a x che a y)
- Lo stesso principio vale per le diagonali decrescenti
E adesso l’ultima considerazione, ovvia ma fondamentale
Partendo da una configurazione valida ( che non viola la condizione B) togliendo una regina si ottiene un’altra configurazione valida.
La 5 ci permette di eseguire con sicurezza il backtrack.
Cominciamo a pensare alle strutture di dati da utilizzare,
- Ci servirà innanzitutto un vettore di booleani che rappresenta la scacchiera ,quindi un vettore di 64 bit. Non lo useremo per i check comunque, ma solo per gestire l’output
- Stessa cosa per le colonne
- Uno per le diagonali decrescenti da 14bit
- E un ultimo per le diagonali crescenti da 14bit
Nelle diagonali crescenti la somma di riga e colonna è costante, e farà da indice. In quelle decrescenti la sottrazione tra righe e colonne è costante e farà da indice, andrà però sfalzata di 7 posizioni in avanti visto che i vettori partono da 0 nel linguaggio scelto (Java).
Detto questo supponendo di disporre di funzioni per aggiungere e togliere regine, una per verificare la disponibilità di una posizione e un ultima per eseguire il dump della scacchiera su schermo la codifica della funzione principale dell’algoritmo è molto compatta:
void generate(){
int h=0;
do{
if(check(n, h)){
iterazioni++;
piazza(n,h);
n++;
if(n==8){
System.out.println(dump(scacchiera));
}
else
generate();
n--;
rimuovi(n,h);
}
h++;
}while(h<8);
}
h rappresenta la colonna corrente, n la riga.
Partendo da (0,0) si controlla che la posizione sia disponibile, se lo è si piazza una regina, se le regine sono 8 siamo su una disposizione finale e allora la stampiamo.
Se non lo siamo richiamiamo la funzione che piazzerà un altra regina e richiamerà se stessa fino a trovare una posizione finale.
Al che togliamo l’ultima cominciamo a cercare una posizione finale successiva, l’algoritmo si conclude quando la prima regina è stata spostata nell’intera prima riga.
L’algoritmo trova tutte le 92 soluzioni in 1951 iterazioni. Questa versione genera tutte le combinazioni in maniera ricorsiva, una versione che le genera una per volta è un po’ più complicata da implementare e ce ne occuperemo nel prossimo articolo.
Per la cronaca, la prima soluzione (quella che stavamo svolgendo a mano a inizio articolo) si trova dopo 113 iterazioni
8 | * |
7 | * |
6 | * |
5 | * |
4 | * |
3 | * |
2 | * |
1 |* |1
113
Per concludere allego il codice completo del progetto
Codice completo del progetto
Queens.java
package darshan.queen;  
import java.util.BitSet;
public class Queens {
int k=0;
int n=0;
int c=0;
long iterazioni=0;
BitSet diagonali_c;
BitSet diagonali_d;
BitSet righe;
BitSet colonne;
BitSet scacchiera;
public Queens(){
diagonali_c=new BitSet(14);
diagonali_d=new BitSet(14);
colonne=new BitSet(8);
scacchiera=new BitSet(64);
}
int p(int r, int c){
return r*8+c;
}
boolean check(int riga, int colonna){
return !(colonne.get(colonna) || diagonali_c.get(riga-colonna+7) || diagonali_d.get(riga+colonna));
}
void generate(){
int h=0;
do{
if(check(n, h)){
iterazioni++;
piazza(n,h);
n++;
if(n==8){
System.out.println(dump(scacchiera));
}
else
generate();
n--;
rimuovi(n,h);
}
h++;
}while(h<8);
}
void piazza(int riga, int colonna){
scacchiera.set(p(riga, colonna));
colonne.set(colonna);
diagonali_c.set(7+riga-colonna);
diagonali_d.set(riga+colonna);
}
void rimuovi(int riga, int colonna){
scacchiera.clear(p(riga, colonna));
colonne.clear(colonna);
//righe.clear(riga);
diagonali_c.clear(7+riga-colonna);
diagonali_d.clear(riga+colonna);
}
public String dump(BitSet scacchiera){
StringBuffer buffer= new StringBuffer();
c++;
for(int a=7;a>=0;a--){
buffer.append("n"+(a+1)+" |" );
for(int b=0;b<8;b++){
if(scacchiera.get(a*8+b))
buffer.append("* ");
else
buffer.append(" ");
}
buffer.append("|");
}
buffer.append(c+"n"+iterazioni);
return buffer.toString();
}
}
Main.java
package darshan.queen;
public class Main {
public static void main(String[] args) {
Queens q= new Queens();
q.generate();
}
}
