ESERCITAZIONE APPLET: 2000-2001

Scopo

Lo scopo dell'esercitazione è quello di definire una Applet per il gioco delle Otto regine, uno dei classici problemi di intelligenza artificiale.
Più precisamente occorre definire: Regole
È dimostrato che su una scacchiera di ordine N > 3 si possono collocare fino ad N regine da scacchi senza che nessuna sia minacciata da un'altra. Una regina minaccia i pezzi che si trovano sulla sua stessa riga, colonna o lungo le due diagonali. Lo scopo del rompicapo è trovare tutti i modi di piazzare N regine su una scacchiera di ordine N senza che nessuna sia minacciata da un'altra.


Celle controllate da una regina

La soluzione è il cosidetto algoritmo di backtracking, che consiste nell'inserire un test dopo ogni nuovo assegnamento per controllare se qualche vincolo non sia stato violato dagli assegnamenti (posizioni delle regine) fatti fino a quel punto (invece di controllare l'ammissibilità della soluzione alla fine). Il rompicapo delle otto regine venne pubblicato nel 1848 in una rivista tedesca di scacchi, ed attrasse l'attenzione del matematico Carl Friedrich Gauss, che però riuscì a trovare solo 72 delle 92 possibili soluzioni.

Algoritmo in C (copyright Eilon Lipton, 2000)
Output (possibili soluzioni)

Materiale

Nella pagina di laboratorio è disponibile documentazione su APPLET Java.

Consegna