Rompicapo delle otto regine

Da Wikipedia, l'enciclopedia libera.

Il rompicapo (o problema) delle otto regine è un problema matematico ispirato al gioco degli scacchi, pubblicato per la prima volta su una rivista di scacchi tedesca nel 1848. Alla soluzione del problema si dedicò anche il noto matematico Carl Friedrich Gauss, che trovò 72 diverse soluzioni.

Nella sua formulazione originale, il problema consiste nel trovare il modo di disporre otto regine su una scacchiera in modo tale che nessuna di esse sia minacciata dalle altre. In altre parole (dato che la regina può spostarsi in orizzontale, in verticale e in diagonale di un qualsiasi numero di caselle) ogni regina deve avere la sua riga, la sua colonna e le sue due diagonali libere. Le soluzioni possibili sono 92 (20 in più di quelle trovate da Gauss).

Il problema può essere generalizzato a una scacchiera di N caselle di lato sulla quale si debbano collocare un pari numero di regine; in questa forma, in particolare, esso viene spesso usato per illustrare tecniche di progettazione di algoritmi e di programmazione. È stato dimostrato matematicamente che per ogni N maggiore di 3 esistono un certo numero positivo di soluzioni; questo numero varia in base al variare di N.

Indice 1 Topologia delle soluzioni 2 Bibliografia 3 Collegamenti esterni 3.1 Algoritmi e programmi risolutivi

[modifica] Topologia delle soluzioni

Delle 92 soluzioni per la scacchiera 8×8, è facile intuire che molte siano sostanzialmente identiche, ovvero ottenibili l'una dall'altra attraverso semplici trasformazioni topologiche come rotazioni o riflessioni. Il numero di soluzioni intrinsecamente diverse è pari a 12.

Di queste, ve ne sono 7 (n. 1-2-3-4-6-8-10) legate da una ulteriore relazione (per quanto risulta a chi scrive non è descritta in letteratura; si propone di chiamarla relazione Di Segni). Se si prende una qualsiasi di queste e la si riproduce in tutte le direzioni fino a occupare il piano (si pensi a un numero infinito di scacchiere con la stessa disposizione di regine accostate l'una all'altra), vengono implicitamente anche riprodotte le altre 6 (o loro riflessioni o rotazioni). Queste 7 soluzioni costituiscono dunque quella che viene chiamata un'unica topologia nel piano.

Infatti, partendo dalla soluzione n.1 e spostandosi di:

• una casella sotto + una a destra, si trova la n.2 ruotata di 180°
• una casella sopra + una a sinistra, si trova la n.3 riflessa e ruotata a destra
• una casella sopra + due a sinistra, si trova la n.4 ruotata a sinistra
• una casella a sinistra, si trova la n.6
• una casella sopra, si trova la n.8 riflessa e ruotata di 180°
• due caselle a sinistra, si trova la n.10 ruotata di 180°

Tra le 5 soluzioni restanti, per una di queste (n. 9), ripetendo il procedimento descritto per le prime sette, si trova (due caselle a destra + quattro sotto) una copia riflessa della stessa. Le altre 4 sono non riconducibili l'una all'altra. Una di queste è l'unica simmetrica (n. 12).

Soluzione n. 2

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 3

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 4

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 5

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 6

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 7

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 8

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 9

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 10

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 11

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

Soluzione n. 12

8
7
6
5
4
3
2
1
	a	b	c	d	e	f	g	h

[modifica] Bibliografia

• Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton University Press, Princeton. ISBN 0-691-11503-6.

[modifica] Collegamenti esterni

• (EN) Articolo su MathWorld
• (EN) Soluzioni
• (EN) Pagina sul problema delle N regine
• Pagina sul problema delle N regine

[modifica] Algoritmi e programmi risolutivi

• Soluzione in Atari BASIC
• Soluzione con algoritmi genetici
• Soluzione Haskell/Java
• Soluzione Java
• Soluzione Standard ML
• Soluzioni varie
• Soluzione LISP
• Soluzione Javascript