Il problema delle n regine è un classico della programmazione. È fondamentalmente un rompicapo che consiste nel piazzare su una scacchiera di dimensione generica n x n, n regine in modo che non possano mangiarsi a vicenda (ovvero, esattamente una regina per ogni riga e per ogni colonna, posizionate in modo che nessuna regina si trovi sulla stessa riga, colonna o diagonali di un'altra). La ricerca delle soluzioni di questo problema è un tipico problema di applicazione della ricorsione.
Ancora una volta per il corso di intelligenza artificiale qui a Copenhagen invece ci è stato richiesto di sviluppare un'intelligenza artificiale che consenta di risolvere il gioco interattivamente (ovvero, l'utente piazza una regina sulla scacchiera, e l'algoritmo calcola a runtime le soluzioni ammissibili con quel vincolo). Quando le regine posizionate sono tali da poter portare a una sola soluzione valida, l'algoritmo se ne accorge e piazza automaticamente le regine rimaste nelle uniche posizioni ammissibili.
http://img338.imageshack.us/img338/411/screenshotay.png
L'algoritmo si basa su un BDD (Binary Decision Diagram) che esprime la logica del gioco, considerando ogni posizione della scacchiera come una variabile booleana in cui è possibile o meno settare una regina. Piazzare una regina sulla scacchiera equivale ad applicare un vincolo a questa funzione booleana. Quando una regina viene piazzata, l'algoritmo verifica ricorsivamente non solo quali variabile booleane nella funzione devono essere false (ovvero, quali caselle devono essere invalidate) per portare a una soluzione valida, ma deve anche verificare ricorsivamente se, con la configurazione corrente della scacchiera, piazzando una regina in una casella vuota è possibile arrivare ad una soluzione (lo fa provando a piazzare una regina lì, e ricorsivamente vedendo se da lì piazzando una regina nelle caselle libere rimaste si arriva a una soluzione). Se non è possibile arrivare a una soluzione da lì, allora anche se quella casella vuota è ammissibile per il piazzamento di una regina in quanto non viola nessun vincolo di "chi mangia chi" viene invalidata ugualmente, in quanto porta a un vicolo cieco.
Descrizione completa dell'algoritmo:
http://0x00.ath.cx/prog/queens.pdf
Download del software (in Java):
http://0x00.ath.cx/prog/queens4itu.tar.gz
Per eseguirlo, basta scompattarlo e runnare lo script
passando come parametro l'n della dimensione della scacchiera (in questo caso, genera una scacchiera 5x5). Piccola nota: l'algoritmo funziona benissimo con una scacchiera 5x5, ancora bene con una 6x6, comincia a dare problemi con una 7x7. Questo perché lo spazio delle soluzioni aumenta esponenzialmente all'aumentare delle dimensioni della scacchiera, aumenta nello stesso modo anche il numero di foglie da esaminare nel BDD, e il garbage collector di Java viene richiamato di continuo per deallocare i nodi di troppo, piantando così l'algoritmo. Inutile dire che usando una libreria esterna per gestire la BDD non è solo colpa mia.
Ancora una volta per il corso di intelligenza artificiale qui a Copenhagen invece ci è stato richiesto di sviluppare un'intelligenza artificiale che consenta di risolvere il gioco interattivamente (ovvero, l'utente piazza una regina sulla scacchiera, e l'algoritmo calcola a runtime le soluzioni ammissibili con quel vincolo). Quando le regine posizionate sono tali da poter portare a una sola soluzione valida, l'algoritmo se ne accorge e piazza automaticamente le regine rimaste nelle uniche posizioni ammissibili.
http://img338.imageshack.us/img338/411/screenshotay.png
L'algoritmo si basa su un BDD (Binary Decision Diagram) che esprime la logica del gioco, considerando ogni posizione della scacchiera come una variabile booleana in cui è possibile o meno settare una regina. Piazzare una regina sulla scacchiera equivale ad applicare un vincolo a questa funzione booleana. Quando una regina viene piazzata, l'algoritmo verifica ricorsivamente non solo quali variabile booleane nella funzione devono essere false (ovvero, quali caselle devono essere invalidate) per portare a una soluzione valida, ma deve anche verificare ricorsivamente se, con la configurazione corrente della scacchiera, piazzando una regina in una casella vuota è possibile arrivare ad una soluzione (lo fa provando a piazzare una regina lì, e ricorsivamente vedendo se da lì piazzando una regina nelle caselle libere rimaste si arriva a una soluzione). Se non è possibile arrivare a una soluzione da lì, allora anche se quella casella vuota è ammissibile per il piazzamento di una regina in quanto non viola nessun vincolo di "chi mangia chi" viene invalidata ugualmente, in quanto porta a un vicolo cieco.
Descrizione completa dell'algoritmo:
http://0x00.ath.cx/prog/queens.pdf
Download del software (in Java):
http://0x00.ath.cx/prog/queens4itu.tar.gz
Per eseguirlo, basta scompattarlo e runnare lo script
Codice:
./run.sh 5passando come parametro l'n della dimensione della scacchiera (in questo caso, genera una scacchiera 5x5). Piccola nota: l'algoritmo funziona benissimo con una scacchiera 5x5, ancora bene con una 6x6, comincia a dare problemi con una 7x7. Questo perché lo spazio delle soluzioni aumenta esponenzialmente all'aumentare delle dimensioni della scacchiera, aumenta nello stesso modo anche il numero di foglie da esaminare nel BDD, e il garbage collector di Java viene richiamato di continuo per deallocare i nodi di troppo, piantando così l'algoritmo. Inutile dire che usando una libreria esterna per gestire la BDD non è solo colpa mia.
Dante