Rompicapo delle otto regine

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.

	a	b	c	d	e	f	g	h
8									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.

Storia

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 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 soluzioni

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									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									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									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									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									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									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									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									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									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									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									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									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

La tabella seguente mostra il numero di soluzioni del problema delle n regine, sia uniche^[1] che distinte^[2], per n = 1–14, 24–27.

n:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	…	24	25	26	27
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	29 363 495 934 315 694
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	234 907 967 154 122 528

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.

Note

^ sequenza A002562 dell'OEIS
^ sequenza A000170 dell'OEIS

Bibliografia

8 regine su una scacchiera (approccio informatico), in Micro & Personal Computer, n. 7, Roma, Gruppo Editoriale Suono, ottobre/novembre 1980, pp. 64-69, OCLC 859585120.
(EN) 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.
(EN) John Watkins, Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press, 2004. ISBN 0-691-11503-6.
(EN) Ole-Johan Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972. ISBN 0-12-200550-3.
(EN) L.Allison, C.N.Yee, & M.McGaughey, Three Dimensional NxN-Queens Problems, Department of Computer Science, Monash University, Australia, 1988.
(EN) S. Nudelman, The Modular N-Queens Problem in Higher Dimensions, Discrete Mathematics, vol 146, iss. 1-3, 15 November 1995, pp. 159–167.
(EN) Ricardo Gomez, Juan Jose Montellano and Ricardo Strausz, On The Modular N-Queen Problem in Higher Dimensions, Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexico, 2004.
(EN) J. Barr e S. Rao, The n-Queens Problem in Higher Dimensions, Elemente der Mathematik, vol. 61 (2006), pp. 133–137.

Altri progetti

Wikimedia Commons contiene immagini o altri file sul rompicapo delle otto regine

Collegamenti esterni

(EN) Articolo su MathWorld, su mathworld.wolfram.com.
(EN) Soluzioni, su bridges.canterbury.ac.nz. URL consultato il 22 marzo 2006 (archiviato dall'url originale il 1º gennaio 2011).
(EN) Pagina sul problema delle N regine, su liacs.nl. URL consultato il 22 marzo 2006 (archiviato dall'url originale il 14 ottobre 2006).
Pagina sul problema delle N regine, su durangobill.com. URL consultato il 22 marzo 2006 (archiviato dall'url originale il 5 gennaio 2011).
Versione DOS/Windows giocabile, su sblendorio.eu.
Versione CP/M giocabile, su github.com.
Rompicapo delle otto regine: gioco gratuito per iPhone, su itunes.apple.com.

Algoritmi e programmi risolutivi

Soluzione in Atari BASIC, su atarimagazines.com.
Metodo generale n regine con implementazione in java
Soluzione con algoritmi genetici, su dossier-andreas.net.
Soluzione Haskell/Java, su scdi.org. URL consultato il 22 marzo 2006 (archiviato dall'url originale il 30 aprile 2006).
Soluzione Java, su math.utah.edu.
Soluzione Standard ML, su dcs.ed.ac.uk.
Soluzione LISP, su obereed.net.

Portale Matematica

Portale Scacchi

[1] sequenza A002562 dell'OEIS

[2] sequenza A000170 dell'OEIS

[1]

[2]