IL BACKTRACKING DEL PROLOG

NELLA RISOLUZIONE

DEL PROBLEMA DELLE N-REGINE

Indice

Introduzione

Il linguaggio Prolog

Il backtracking nel sistema Prolog

Unificazione e backtracking

Un esempio di utilizzo del baktracking
Il backtracking attraverso il problema delle N-Regine
- Il ruolo del backtracking
Versione audio della lezione
Test della lezione

Introduzione

La seguente lezione si propone di illustrare le caratteristiche e le funzionalità del processo di backtracking all'interno di un linguaggio di programmazione logica quale il Prolog. In particolare, abbiamo scelto di mostrare l'efficacia del backtracking nella risoluzione di un problema noto (il problema delle N-Regine), in cui si devono porre n regine all'interno di una scacchiera nxn in modo che nessuna di esse possa minacciare le altre.

Nei prossimi paragrafi vengono brevemente ricordate le caratteristiche essenziali del Prolog e viene descritto il processo di matching utilizzato dall'interprete per ottenere una soluzione. Viene poi introdotto mediante qualche esempio il processo di backtracking. Infine viene illustrato il problema delle N-Regine ed una sua possibile risoluzione attraverso l'applet "NQueens Applet", realizzata a supporto della lezione ed implementata in Prolog ed in Java; attraverso questo esempio vengono discusse le peculiarità del backtracking mostrandone gli effetti nell'esecuzione dell'applet ed al livello del codice sorgente Prolog.

Il linguaggio Prolog

Nota. La sezione seguente vuole essere un breve riepilogo delle caratteristiche del Prolog; si assume che il lettore abbia familiarità con la programmazione in Prolog e con gli elementi di base del linguaggio (es. atomi, variabili, regole, goal, interazioni con il sistema...).
Chi non conosce questo linguaggio può consultare il tutor.

Per chi ha qualche conoscenza di questo linguaggio, si risorda che il Prolog è un linguaggio di programmazione per computazioni simboliche, non numeriche. Un programma in Prolog è formato da clausole. Quest'ultime possono essere di due tipi: fatti e regole. I primi esprimono qualcosa che è sempre vero, incondizionatamente (es. Socrate è un uomo: uomo(socrate)); le regole invece specificano cose che possono essere vere se determinate condizioni sono vere (es. se X è un uomo, allora X è mortale: mortale(X):-uomo(X)). Ciascuna clausola è composta da oggetti concreti (atomi, costituiti da nomi o costanti), oggetti generali (variabili) oppure oggetti strutturati (funtori, esprimono relazioni tra oggetti). L'interazione con un programma avviene fornendo interrogazioni (goal-list) al sistema Prolog che può rispondere in maniera semplice (sì/no) oppure fornire una lista di sostituzioni di variabili che rendono soddisfacibile l'interrogazione.

Il backtracking del sistema Prolog

Unificazione e backtracking

Per poter spiegare in cosa consiste il processo di backtracking è necessario illustrare il modo in cui il motore Prolog cerca di rispondere ad un'interrogazione. Supponiamo che l'interrogazione posta sia costituita dalla seguente goal-list:

?-G1,G2, ...,Gn.

Il sistema cerca sempre di soddisfare il primo termine (a sinistra). Il sistema Prolog effettua una ricerca tra le clausole presenti nella base di conoscenza: se tale clausola non esiste, il processo termina con una risposta negativa. Se si ha unificazione con un fatto, il sistema cerca di soddisfare il termine successivo (in questo esempio G2). Se l'unificazione avviene con la testa di una regola

H:- F1, F2, ... , Fm.

il termine G1 viene sostituito (nella goal-list) con il corpo della regola, ottenendo la nuova interrogazione:

?- F1, ... , Fm, G2, G3, ... , Gn.

Si tiene conto delle sostituzioni effettute nell'unificazione di H e G1 propagandole anche a tutti i termini F1...Fm e G1...Gn della lista.
Il processo di unificazione procede ricorsivamente sul nuovo termine F1 con le stesse modalità descritte sopra. Una interrogazione termina con successo quando tutti i termini della lista si unificano. Quando l'unificazione di un termine (per esempio G3) non ha successo, il sistema annulla le sostituzioni eseguite a seguito della unificazione del termine precedente (nell'esempio G2) e cerca di soddisfare questo termine in modo diverso: se ci riesce, si riprende col tentativo di soddisfare i termini successivi.

Il backtracking è il processo attivato dal sistema Prolog ogni qualvolta l'esecuzione di un certo subgoal fallisce, cioè quando un termine non può essere unificato; in tal caso il sistema Prolog si riconduce al subgoal precedente e tenta di effettuare un nuovo processo di unificazione. Tutte le sostituzioni di variabili effettuate dal precedente matching sono cancellate; il sistema cerca all'interno della base di conoscenza un'altra clausola che possa fare matching con il termine di cui si deve verificare la soddisfacibilità.

Un esempio di utilizzo del backtracking

Si consideri la seguente base di conoscenza Prolog:

quadrilatero(trapezio).
quadrilatero(rombo).
triangolo(tr_isoscele).
triangolo(tr_equilatero).
poligono(X):-quadrilatero(X).
poligono(X):-triangolo(X).
halatiuguali(rombo).

halatiuguali(tr_equilatero).

Si supponga di effettuare la seguente interrogazione:

?- poligono(Z), halatiuguali(Z).
Il sistema Prolog procede unificando il primo termine dell'interrogazione con la testa della regola 5 ottenendo la nuova goal-list:

?- quadrilatero(Z), halatiuguali(Z).
Analogamente, dall'unificazione di quadrilatero(Z) con la prima clausola disponibile (1), si ottengono la sostituzione Z = trapezio e la nuova interrogazione:
?- halatiuguali(trapezio).
Il tentativo di unificazione di questo termine fallisce. Il meccanismo di backtracking del Prolog consente di risalire alla goal-list precedente:

?- quadrilatero(Z), halatiuguali(Z).

e di provare ad unificare il termine quadrilatero(Z) con un'altra clausola presente nella base di conoscenza. L'unificazione ha successo con la clausola numero 2 e la sostituzione di Z con rombo. In tal modo la goal-list si riduce a:

?- halatiuguali(rombo).

L'unificazione di questo termine ha successo e la risposta del sistema è

Z = rombo.

Forzando il sistema a cercare nuove soluzioni si ottiene anche la risposta:

Z = tr_equilatero.

Il backtracking attraverso il problema delle N-Regine

Descrizione del problema

Il problema delle N-regine consiste nel disporre n regine su di una scacchiera nxn senza che esse si minaccino a vicenda. Le regine hanno le stesse proprietà dell'omonimo pezzo degli scacchi, cioè in una mossa possono spostarsi di un numero arbitrario di caselle in verticale, orizzontale e diagonale. Il problema dunque è quello di posizionare le regine su caselle "sicure", cioè non minacciate da altre regine; intendiamo quindi per sicura una casella che non può essere raggiunta da un pezzo in una sola mossa. n indica il numero di regine (ed anche di caselle per lato della scacchiera) che devono essere posizionate sulla scacchiera. La soluzione del problema fornisce una (o più) disposizione di tutte le n regine su caselle sicure, in modo che la configurazione ottenuta risulti essere sicura, ossia nessuna regina può essere minacciata. Il problema deve essere risolto per
n >= 4, poiché scegliendo n compreso tra 0 e 3 il problema risulta essere banalmente insolubile.

L'applet NQueens

Seguendo il seguente link si può eseguire Nqueens Applet che risolve il problema delle N-Regine: sono disponibili due modalità di esecuzione che consentono meglio di apprezzare il comportamento del programma con particolare riferimento al processo di backtracking. Sono presenti inoltre una descrizione dell'interfaccia dell'applet ed i link ai codici sorgenti Java e Prolog.

Il ruolo del backtracking

L'applet consente di mostrare con immediatezza l'attività di backtracking del sistema Prolog nel posizionamento delle regine sulla scacchiera. Supponiamo
n (numero di regine) = 4. Come si può vedere dall'esecuzione dell'applet in modalità step-by-step le prime 2 regine possono essere collocate su posizioni sicure:

Figura 1
Nella configurazione corrente tuttavia non può essere posizionata la terza regina. Tramite il meccanismo del backtracking si cerca allora una nuova configurazione sicura per la seconda regina.

Figura 2
A questo punto anche la terza e la quarta regina possono essere inserite sulla scacchiera in posizioni non minacciate da altri pezzi. In realtà l'Applet non mostra tutti i passaggi intermedi del backtracking del sistema Prolog, ma visualizza solo le configurazioni stabili, quelle cioè in cui le regine poste sulla scacchiera sono su caselle sicure. Tramite il comando "Altre Soluzioni" si possono ricercare, se esistono, nuove soluzioni al problema. Si consideri ora il meccanismo di backtracking a livello del programma sorgente Prolog che risolve il problema delle N-regine. (Per fini didattici si supponga un'istanza semplificata del problema in cui N = 5).

nqueens(5, Position):-
    construct_solution(5, Position),
    find_solution(Position, [1,2,3,4,5]).

construct_solution(0, [ ]).
construct_solution(N, [ _ | Tail]):- M is N - 1, M >= 0,
                                                      construct_solution(M, Tail).

find_solution([ ], _ ).
find_solution([Y | Others], List):-
    find_solution(Others, List),
    member(Y, List),
    noattack(Y, Others, 1).

noattack( _, [ ], _ ).
noattack(Y, [Y1 | Others], Xdist):-
    Y =\= Y1,
    Y1 - Y =\= Xdist,
    Y - Y1 =\= Xdist,
    Dist1 is Xdist + 1,
    noattack(Y, Others, Dist1).

La soluzione finale è rappresentata da una lista di 5 elementi che indicano rispettivamente le 5 colonne in cui devono essere poste le regine, assumendo ovviamente che ciascun pezzo debba essere posto su una riga differente. Si supponga dunque di aver posizionato le prime due regine come indicato nella figura 1. Al momento dell'esecuzione dell'interrogazione find_solution(...) si ha che Others = [3,1] e List = [1,2,3,4,5].
L'esecuzione del subgoal member(Y, List) produce la sostituzione Y = 1, tuttavia è facile da verificare che per tale sostituzione l'esecuzione del termine noattack(1,[3,1],1) fallisce. Attraverso il processo di backtracking si tenta allora a risoddisfare member(Y, List): per nessun altro valore di Y però il termine noattack è unificabile. Per questo è necessario ricollocare la seconda regina; provando infatti a risoddisfare il termine member(Y, List) si ottiene l'unica altra alternativa possibile Y = 4 come indicato dalla figura 2. Procedendo in maniera simile è possibile collocare gli altri pezzi mancanti sulla scacchiera.