Torna alla Home Page del corso    Torna alla pagina degli Elaborati

CSP: L’ESEMPIO DELLE N-REGINE.
Il Constraint Satisfaction Problem (CSP) è un paradigma semplice e potente, con il quale possono essere formulati numerosi problemi. A livello informale, il concetto fondamentale del ragionamento basato sui vincoli è quello di constraint network, definito da un insieme di variabili, un dominio di valori per ogni variabile ed un insieme di vincoli tra le variabili. Risolvere un constraint network significa trovare un assegnamento di valori per ogni variabile, in modo tale che tutti i vincoli siano soddisfatti. Il problema delle n-regine può essere formulato in CSP:

• vi sono n variabili, ciascuna delle quali corrisponde ad una colonna;
• il dominio di valori di ognuna delle n variabili è il numero di riga.
• la variabile x_i rappresenta l’i-esima colonna della scacchiera, ed il suo dominio D_i è costituito dai numeri delle righe: in altre parole x_i può assumere i valori ad 1 ad n, ciascuno dei quali individua una riga. Il vincolo tra le variabili può essere espresso dal fatto che due variabili non possono avere lo stesso valore (altrimenti le regine si troverebbero sulla stessa riga) e dal fatto che la differenza tra il numero delle colonne di due regine deve essere diverso dalla differenza del numero delle righe in cui si trovano (altrimenti sarebbero sulla stessa diagonale).

In figura sono visualizzate due istanze del problema delle 4-regine; con la lettera Q sono indicate le regine disposte sulla scacchiera, mentre le posizioni in grigio sono quelle in cui non possono essere poste altre regine perché potrebbero venire attaccate dalle regine già disposte. Ad esempio {(x₁, 4)} indica che nella colonna 1 è stata messa la regina alla riga 4, e questo implica che saranno vietate per le altre regine le posizioni {(x₂, 4), (x₃, 4), (x₄, 4)} (perché sono sulla stessa riga) e {(x₂, 3), (x₃, 2), (x₄, 1)} (perché sono sulla stessa diagonale): le caselle colorate indicano proprio le posizioni vietate. Nell’istanza di destra la tupla {(x₁, 2), (x₂, 4), (x₃, 1), (x₄, 3)} (o, più semplicemente (2,4,1,3)) è una soluzione completa: è facile verificare che nessuna regina può essere attaccata dalle altre.
Come viene applicato il backtracking al problema delle n-regine così formulato?
 

Precedente    Successiva