Il backtracking attraverso il problema delle N-Regine

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.