PROBLEMA DELLE REGINE ===================== Il problema consiste nel disporre su una scacchiera quadrata delle regine, una per riga, in modo che non si attacchino a vicenda. Due regine si attaccano se sono sulla stessa colonna oppure sulla stessa diagonale (dato che su una riga c'e' solamente una regina, non occorre considerare il caso di due regine sulla stessa riga). Ad esempio, consideriamo la seguente configurazione su una scacchiera di dimensione 5: - - A - - - - - - B C - - - - - - D - - La regina A attacca la regina C (stessa diagonale) e la regina D (stessa colonna). La regina B attacca la regina D (stessa diagonale). La regina C attacca la regina A (stessa diagonale). La regina D attacca la regina A (stessa colonna) e la regina B (stessa diagonale). Una soluzione del problema delle regine per una scacchiera di dimensione 5 e': - - - X - X : casella occupata da una regina X - - - - - : casella libera - - X - - - - - - X - X - - - L'obiettivo dell'esercizio e' di scrivere un programma ProblemaRegine che legge dalla linea di comando un intero n>1 e stampa tutte le soluzioni del problema delle regine su una scacchiera di dimensione n. Esempio ------- Il comando java ProblemaRegine 4 deve stampare SOLUZIONE 1 - X - - - - - X X - - - - - X - SOLUZIONE 2 - - X - X - - - - - - X - X - - che sono le due uniche soluzioni al problema delle regine per una scacchiera di dimensione 4. E' possibile che le soluzioni siano stampate in ordine diverso. Notare che per n=2,3 il problema non ha soluzioni. Con la scacchiera standard (n=8) ci sono 92 soluzioni. Struttura del programma ----------------------- Il programma, oltre alla classe ProblemaRegine che contiene il metodo main, utilizza le classi Regina e Scacchiera descritte sotto. Usiamo la solita convenzione di numerare le righe e le colonne a partire da 0, la riga 0 e' quella piu' in alto, la colonna 0 quella piu' a sinistra. In ogni riga della scacchiera c'e' una e una sola regina. Si noti che: 1) nella descrizione dei metodi la segnatura a volte e' scritta in forma incompleta; 2) i campi utilizzati nelle classi devono avere visibilita' private; 3) una classe puo' contenere altri metodi oltre a quelli esplicitamente nominati. * Regina Classe che descrive la regina di una scacchiera. Deve avere un costruttore Regina(scacchiera, riga) che costruisce una regina per la scacchiera specificata dal primo parametro, alla riga specificata dal secondo parametro, alla colonna 0. Si assume che la scacchiera contenga la riga specificata. Deve possedere i seguenti metodi (in alcuni casi occorre utilizzare i metodi della classe Scacchiera descritti sotto): - getRiga() Restituisce la riga in cui si trova la regina. - getColonna() Restituisce la colonna in cui si trova la regina. - isUltima() Restituisce true se la regina e' nell'ultima riga della scacchiera, false altrimenti. - nextRegina() Restituisce la prossima regina della scacchiera (ossia, la regina nella riga successiva a quella in cui si trova questa regina) oppure null se questa e' l'ultima regina. - attaccaRegina(reg) Restituisce true se questa regina attacca la regina reg specificata dal parametro, false altrimenti. Si assume che reg sia sulla stessa scacchiera di questa regina. - attaccaReginePrecedenti() Restituisce true se questa regina attacca una delle regine posizionate alle righe precedenti, false altrimenti. - cercaPosizione() E' il metodo che implementa la strategia per la ricerca delle soluzioni. Il metodo cerca una posizione corretta per questa regina (ossia, una posizione per cui questa regina non attacca nessuna delle regine alle righe precedenti) e chiede ricorsivamente alla prossima regina di fare altrettanto. Quando si arriva all'ultima regina, e' stata trovata una soluzione al problema. Piu' in dettaglio, supponiamo che questa sia la regina alla riga R della scacchiera SC. Assumiamo che quando il metodo viene chiamato valga la seguente proprieta' (pre-condizione): (*) Le regine della scacchiera SC alle righe 0,1, ... , R-1 sono posizionate in modo tale che non si attacchino a vicenda. Il metodo sposta questa regina una colonna per volta, a partire dalla colonna 0 fino all'ultima colonna della scacchiera. Ogni volta che la regina si trova in una posizione per cui non attacca nessuna delle regine precedenti, compie una delle seguenti azioni: A) Se questa e' l'ultima regina, e' stata trovata una nuova soluzione al problema. Va stampata la soluzione usando il metodo opportuno della classe Scacchiera. B) Altrimenti, ricorsivamente, chiede alla prossima regina di cercarsi una posizione (chiamata ricorsive di questo metodo). Si noti che quando nel caso B si fa la chiamata ricorsiva, la pre-condizione (*) e' verificata, in quanto la regina alla riga R e' ora in una posizione per cui non attacca nessuna delle regine alle righe precedenti (le altre regine gia' verificavano (*) e non sono state mosse). Nel caso A non vengono fatte chiamate ricorsive, e questo garantisce la terminazione del procedura di ricerca delle soluzioni. * Scacchiera Classe che descrive una scacchiera con una regina per riga. Deve avere un costruttore che costruisce una scacchiera di dimensione dim specificata da un parametro, in cui viene disposta una regina per riga alla colonna 0. Si assume dim>0. Deve possedere i seguenti metodi: - getDimensione() Restituisce la dimensione di questa scacchiera. - getRegina(r) Restituisce la regina alla riga r. - contieneRegina(r, c) Dati due interi r e c qualunque, restituisce true se nella scacchiera alla riga r e colonna c c'e' una regina, false altrimenti. - incrementaSoluzioni() Incrementa di 1 il numero di soluzioni trovate al problema delle regine (va definito un contatore per le soluzioni). - trovaSoluzioni() Cerca tutte le soluzioni del problema delle regine per questa scacchiera (e' sufficiente una chiamata al metodo cercaPosizione della classe Regina). - stampa() Stampa una soluzione del problema (numero della soluzione e configurazione della scacchiera).