Il backtracking attraverso il problema delle N-Regine - Descrizione del problema, Il ruolo del backtracking

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.