|
Rompicapo delle otto regine
Una possibile soluzione del problema.
Il rompicapo (o problema) delle otto regine è un problema che consiste nel trovare il modo di posizionare otto donne (pezzo degli scacchi) su una scacchiera 8×8 tali che nessuna di esse possa catturarne un'altra, usando i movimenti standard della regina. Perciò, una soluzione dovrà prevedere che nessuna regina abbia una colonna, traversa o diagonale in comune con un'altra regina. Il problema delle otto regine è un esempio del più generale problema delle n regine, che consiste nel piazzare, con le condizioni illustrate precedentemente, n regine su una scacchiera n × n; in questa forma, in particolare, esso viene spesso usato per illustrare tecniche di progettazione di algoritmi e di programmazione. È stato dimostrato matematicamente che il problema è risolvibile per n = 1 o n ≥ 4, mentre non lo è per n = 2 e n = 3. StoriaIl problema venne originariamente proposto nel 1848 dal giocatore di scacchi Max Bezzel, e negli anni molti matematici, incluso Gauss, che riuscì a trovare 72 delle 92 soluzioni, hanno lavorato al problema e alla sua forma generalizzata. La prima soluzione fu data da Franz Nauck nel 1850. Fu Nauck poi ad estendere il problema alla sua forma generalizzata. Nel 1874, S. Günther propose un metodo per trovare le soluzioni del problema utilizzando i determinanti, metodo che venne perfezionato poi da J.W.L. Glaisher. Edsger Dijkstra, nel 1972, usò il problema delle n regine per illustrare il potere di ciò che egli chiamò programmazione strutturata. Pubblicò una descrizione assai dettagliata dello sviluppo di un algoritmo backtracking DFS. Tutte le soluzioniLe 92 soluzioni si riducono essenzialmente a 12 non ottenibili l'una dall'altra tramite rotazioni e riflessioni:
Numero delle soluzioniLa tabella seguente mostra il numero di soluzioni del problema delle n regine, sia uniche[1] che distinte[2], per n = 1–14, 24–27.
Notare che il problema delle sei regine ha meno soluzioni del problema delle cinque regine. Non esiste ancora una formula per calcolare l'esatto numero di soluzioni. Versione animata della soluzione ricorsiva
Questa animazione usa il backtracking per risolvere il problema. Una regina è posizionata in una colonna che non genera conflitto. Se la colonna non viene trovata il programma ritorna all'ultimo stato positivo e viene provata una differente colonna. NoteBibliografia
Altri progetti
Collegamenti esterni
Algoritmi e programmi risolutivi
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
