Olimpiadi di Informatica 2010
Giornate preparatorie
Dipartimento di Informatica
Università di Torino
marzo 2010
6 – Algoritmi di backtracking: il problema delle regine.
(versione 21/12/2015)
12/21/2015
E. Giovannetti -- OI09.
1
Il problema delle otto (o n) regine.
Disporre 8 regine sulla scacchiera 8  8 in modo che nessuna
regina ne attacchi un’altra secondo le regole del gioco degli
scacchi; cioè in modo che nessuna si trovi nella stessa riga, o
nella stessa colonna, o nelle stesse “diagonali” di un’altra.
Il problema è generalizzabile in modo banale a n regine su
una scacchiera n  n :
• per n  4 il problema non è risolubile, come si vede con
ispezione diretta;
• per ciascun n  4 il problema ammette più soluzioni.
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
2
Come rappresentare le soluzioni.
• Poiché non possono esserci due regine nella stessa riga,
qualunque disposizione che risolva il problema deve avere
una e una sola regina per riga.
• Allora possiamo disporre la prima regina nella prima riga, la
seconda regina nella seconda riga, … la i-esima regina nella
i-esima riga, ecc.
• Una soluzione è quindi semplicemente una permutazione di
degli n numeri naturali da 1 a n o da 0 a n-1, rappresentabile
per mezzo di un array.
• Esempio: per la scacchiera 5  5 l’array {0, 2, 4, 1, 3} è la
disposizione delle regine nelle caselle:
(0,0); (1,2); (2,4); (3,1); (4,3).
• Naturamente i ruoli delle righe e delle colonne sono
perfettamente intercambiabili.
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
3
L’algoritmo ricorsivo: descrizione molto informale.
Per posizionare le regine dall’i-esima riga in avanti:
• se i è la riga successiva all’ultima, termina con successo;
• altrimenti cerca una colonna j tale che siano prive di regine
• la colonna j stessa,
• la diagonale ascendente passante per la casella (i,j),
• la diagonale discendente passante per la casella (i,j);
• posiziona la i-esima regina nella casella (i,j);
• posiziona le regine dall’ i+1-esima riga in avanti;
• se tale posizionamento ha successo, termina con successo;
• altrimenti backtrack: rimuovi la i-esima regina e poi cerca
un’altra colonna j che soddisfi alle condizioni di cui sopra,
e così via finché non ci sono più colonne da esaminare:
• in tal caso termina con fallimento.
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
4
L’algoritmo ricorsivo: descrizione più precisa
n = dimensione della tastiera; array indiciati da 0 a n-1
boolean posizionaDallaRiga(int i) {
if(i == n) return true;
else {
for(int j = 0; j < n; j++) {
if(colonna j è libera da regine
&& diagonale ascendente per (i,j) è libera da regine
&& diagonale discendente per (i,j) è libera da regine) {
posiziona l’i-esima regina nella colonna j;
if(posizionaDallaRiga(i+1)) return true;
else rimuovi l’i-esima regina; continua il ciclo
}
}
fine ciclo for
return false;
se si sono provate senza successo tutte
}
le colonne j, si fallisce
} 21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
5
La chiamata iniziale
Naturalmente la funzione ricorsiva deve essere inizialmente
invocata con il valore del primo indice (1 in Pascal, 0 in C):
boolean problemaRegine() {
return posizionaDallaRiga(0);
}
La soluzione è rappresentata da una struttura-dati globale;
se si definisce una procedura che visualizza la soluzione, il
main avrà la forma
…
problemaRegine();
visualizzaSoluzione();
…
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
6
Strutture dati convenienti.
Per poter effettuare in tempo costante i test sulla presenza
di regine nella colonna e nelle due diagonali, conviene tenere
tre array di booleani, indiciati rispettivamente dal numero di
colonna e dal “numero di diagonale”, dove il k-esimo elemento
di ognuno degli array ha il significato:
• la k-esima colonna, o diagonale in su, o in giù, è senza regine.
In una scacchiera n  n vi sono:
• n colonne;
• 2n diagonali ascendenti;
• 2n diagonali discendenti.
Osserva:
• le caselle (i, j) di una data diagonale ascendente sono quelle
per cui i+j = costante dipendente dalla diagonale;
• le caselle di una data diagonale discendente sono quelle per
cui i-j = costante dipendente dalla diagonale;
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
7
Strutture dati convenienti: Pascal.
Indiciamo, come naturale, righe e colonne da 1 a 8:
const n = …;
var q: array[1..n] of integer; // posizioni delle regine
freeCol: array[1..n] of boolean;
Allora:
• la somma i+j varia da 1+1 a n+n, cioè da 2 a 2n;
• la differenza i-j varia da 1-n a n-1
(ad es., per n = 8, varia da -7 a +7).
Quindi, poiché in Pascal gli array si possono indiciare con un
range qualunque:
freeDiagRise: array[2..2*n] of boolean;
freeDiagFall: array[-n+1..n-1] of boolean;
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
8
Strutture-dati convenienti: C++
Gli array sono indiciabili solo a partire da 0, quindi:
int q[n];
bool freeCol[n];
Poiché gl’indici di riga e di colonna vanno da 0 a n-1:
• la somma i+j varia da 0 a 2n-2, cioè ha 2n-1 possibili valori,
• la somma i-j varia da –n+1 a n-1, cioè ha 2n-1 possibili valori.
Quindi:
bool freeDiagRise[2*n - 1];
bool freeDiagFall[2*n - 1];
Nel codice, per l’accesso all’array delle diagonali discendenti
occorrerà “traslare” il range –n+1..n-1 nel range 0..2n-1,
sommando n-1 al valore di i-j.
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
9
Strutture-dati convenienti: nomi corti.
Per ragioni di spazio nelle slides successive (o eventualmente
per velocità di codifica) usiamo nomi più corti per gli array.
In C++:
int q[n];
bool c[n];
// colonne libere
bool a[2*n - 1]; // diagonali ascendenti libere
bool b[2*n - 1]; // diagonali discendenti libere
In Pascal:
var q: array[1..n] of integer;
c: array[1..n] of boolean;
a: array[2..2*n] of boolean;
b: array[-n+1..n-1] of boolean;
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
10
La funzione ricorsiva (C++)
bool placeQueens(int i) {
if(i == n) return true;
for(int j = 0; j < n; j++) {
if(c[j] && a[i+j] && b[i-j+n-1]) {
q[i] = j;
c[j] = a[i+j] = b[i-j+n-1] = false;
if(placeQueens(i+1)) return true;
else c[j] = a[i+j] = b[i-j+n-1] = true;
}
}
return false;
}
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
11
La funzione top-level
void queens() {
for(int i = 0; i < n; i++) c[i] = true;
for(int i = 0; i < 2*n-1; i++) a[i] = true;
for(int i = 0; i < 2*n-1; i++) b[i] = true;
placeQueens(0);
}
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
12
Il ciclo for in Pascal
In Pascal l’indiciamento degli array è più immediato:
...
for j:= 1 to n do begin
if (c[j] and a[i+j] and b[i-j]) then begin
q[i]:= j;
c[j]:= false; a[i+j]:= false; b[i-j]:=false;
if placeQueens(i+1) then begin
result:= true; exit
end
else begin
c[j]:= true; a[i+j]:= true; b[i-j]:= true
end
end
end;
...
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
13
Il problema delle n regine: tutte le soluzioni.
Con una lieve modifica dell’algoritmo si possono generare
tutte le soluzioni, cioè tutte le disposizioni di n regine sulla
scacchiera n  n che soddisfano alle condizioni del problema.
Per ottenere ciò, basta non fermarsi quando si trova una
soluzione, bensì continuare il backtracking.
Non è quindi più necessario che la procedura restituisca un
booleano: ogni volta che si trova una soluzione si può semplicemente stamparla, oppure aggiungerla ad una struttura-dati
(ad es. una matrice) che rappresenta l’insieme delle soluzioni.
Se si è interessati anche o solo al numero delle soluzioni, si
può introdurre un contatore che conti il numero di soluzioni,
da incrementarsi ogni volta che se trova una.
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
14
Il problema delle n regine: tutte le soluzioni.
void placeQueens(int i) {
for(int j = 0; j < n; j++) {
if(c[j] && a[i+j] && b[i-j+n-1]) {
q[i] = j;
c[j] = a[i+j] = b[i-j+n-1] = false;
if(i == n-1) {
writeSolution();
numSolutions++;
}
else placeQueens(i+1);
c[j] = a[i+j] = b[i-j+n-1] = true;
}
}
}
21/12/2015 14:31
E. Giovannetti - AlgELab-09-10 - Lez.46
15