Problema delle N regine

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: 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. 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).