Rompicapo delle otto regine

Da Wikipedia, l'enciclopedia libera.
a b c d e f g h
8
Chessboard480.svg
d8 donna del bianco
g7 donna del bianco
c6 donna del bianco
h5 donna del bianco
b4 donna del bianco
e3 donna del bianco
a2 donna del bianco
f1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Una possibile soluzione del problema.

Il rompicapo (o problema) delle otto regine è un problema che consiste nel trovare il modo di posizionare otto regine (pezzo degli scacchi) su una scacchiera 8x8 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.

Storia[modifica | modifica sorgente]

Il 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 soluzione 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 soluzioni[modifica | modifica sorgente]

Le 92 soluzioni si riducono essenzialmente a 12 non ottenibili l'una dall'altra tramite rotazioni e riflessioni:

a b c d e f g h
8
Chessboard480.svg
d8 donna del bianco
g7 donna del bianco
c6 donna del bianco
h5 donna del bianco
b4 donna del bianco
e3 donna del bianco
a2 donna del bianco
f1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 1
a b c d e f g h
8
Chessboard480.svg
e8 donna del bianco
b7 donna del bianco
d6 donna del bianco
g5 donna del bianco
c4 donna del bianco
h3 donna del bianco
f2 donna del bianco
a1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 2
a b c d e f g h
8
Chessboard480.svg
d8 donna del bianco
b7 donna del bianco
g6 donna del bianco
c5 donna del bianco
f4 donna del bianco
h3 donna del bianco
e2 donna del bianco
a1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 3
a b c d e f g h
8
Chessboard480.svg
d8 donna del bianco
f7 donna del bianco
h6 donna del bianco
c5 donna del bianco
a4 donna del bianco
g3 donna del bianco
e2 donna del bianco
b1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 4
a b c d e f g h
8
Chessboard480.svg
c8 donna del bianco
f7 donna del bianco
h6 donna del bianco
a5 donna del bianco
d4 donna del bianco
g3 donna del bianco
e2 donna del bianco
b1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 5
a b c d e f g h
8
Chessboard480.svg
e8 donna del bianco
c7 donna del bianco
h6 donna del bianco
d5 donna del bianco
g4 donna del bianco
a3 donna del bianco
f2 donna del bianco
b1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 6
a b c d e f g h
8
Chessboard480.svg
e8 donna del bianco
g7 donna del bianco
d6 donna del bianco
a5 donna del bianco
c4 donna del bianco
h3 donna del bianco
f2 donna del bianco
b1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 7
a b c d e f g h
8
Chessboard480.svg
d8 donna del bianco
a7 donna del bianco
e6 donna del bianco
h5 donna del bianco
f4 donna del bianco
c3 donna del bianco
g2 donna del bianco
b1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 8
a b c d e f g h
8
Chessboard480.svg
c8 donna del bianco
f7 donna del bianco
d6 donna del bianco
a5 donna del bianco
h4 donna del bianco
e3 donna del bianco
g2 donna del bianco
b1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 9
a b c d e f g h
8
Chessboard480.svg
f8 donna del bianco
b7 donna del bianco
g6 donna del bianco
a5 donna del bianco
d4 donna del bianco
h3 donna del bianco
e2 donna del bianco
c1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 10
a b c d e f g h
8
Chessboard480.svg
d8 donna del bianco
g7 donna del bianco
a6 donna del bianco
h5 donna del bianco
e4 donna del bianco
b3 donna del bianco
f2 donna del bianco
c1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 11
a b c d e f g h
8
Chessboard480.svg
f8 donna del bianco
d7 donna del bianco
g6 donna del bianco
a5 donna del bianco
h4 donna del bianco
b3 donna del bianco
e2 donna del bianco
c1 donna del bianco
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Soluzione unica 12

Numero delle soluzioni[modifica | modifica sorgente]

La tabella seguente mostra il numero di soluzioni del problema delle n regine, sia uniche (sequenza A002562 dell'OEIS) che distinte (sequenza A000170 dell'OEIS), per n = 1–14, 24–26.

n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 24 25 26
Uniche: 1 0 0 1 2 1 6 12 46 92 341 1 787 9 233 45 752 28 439 272 956 934 275 986 683 743 434 2 789 712 466 510 289
Distinte: 1 0 0 2 10 4 40 92 352 724 2 680 14 200 73 712 365 596 227 514 171 973 736 2 207 893 435 808 352 22 317 699 616 364 044

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[modifica | modifica sorgente]

Eight-queens-animation.gif

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.

Bibliografia[modifica | modifica sorgente]

  • Jordan Bell e Brett Stevens, A survey of known results and research areas for n-queens, Discrete Mathematics, Vol. 309, numero 1, gennaio 2009, 1-31.
  • John Watkins, Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press, 2004. ISBN 0-691-11503-6.
  • O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972. ISBN 0-12-200550-3.
  • Three Dimensional NxN-Queens Problems, L.Allison, C.N.Yee, & M.McGaughey (1988), Department of Computer Science, Monash University, Australia.
  • S. Nudelman, The Modular N-Queens Problem in Higher Dimensions, Discrete Mathematics, vol 146, iss. 1-3, 15 November 1995, pp. 159–167.
  • On The Modular N-Queen Problem in Higher Dimensions, Ricardo Gomez, Juan Jose Montellano and Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexico.
  • J. Barr e S. Rao, The n-Queens Problem in Higher Dimensions, Elemente der Mathematik, vol. 61 (2006), pp. 133–137.

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

Algoritmi e programmi risolutivi[modifica | modifica sorgente]