Vuit reines

	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 de les possibles solucions.

El trencaclosques de les vuit reines (o de les vuit dames) és un problema de raonament lògic que consisteix a posar vuit dames d'escacs en un escaquer (8 × 8 caselles) de tal manera que cap d'elles sigui capaç de capturar-ne qualsevol altra amb els moviments estàndards de la dama dels escacs. Les dames s'han de col·locar de tal manera que no n'hi hagi cap capaç d'amenaçar les altres. Per tant, requereix una solució en què no hi hagi dues dames que comparteixin la mateixa fila, columna o diagonal.

El trencaclosques de les vuit dames és un exemple del més general trencaclosques de les n reines que consisteix a col·locar n dames en un tauler d'escacs n × n, que només té solucions per a n= 1 o n ≥ 4.

El problema concret de 8 × 8 té 92 solucions diferents.

Plantejament

Com que cada reina pot amenaçar a les reines que estiguin en la mateixa fila, cada una s'ha de situar en una fila diferent. Podem representar les 8 reines mitjançant un vector on cada índex representa la fila i el valor per a aquell índex representa la columna. Llavors, si el vector té un valor repetit, la distribució és incorrecta. Per tant, el vector correspondria a una permutació dels vuit primers nombres enters.

Pel que fa a les diagonals; sabem que pel que fa a una mateixa diagonal descendent, es compleix que tenen el mateix valor $fila-columna$, mentre que per la diagonal ascendent es compleix que tenen el mateix valor $fila+columna$. Per tant, si tenim dues reines en les posicions $(i,j)$ i $(k,l)$ estan a la mateixa diagonal si i només si:

$i-j=k-l$ o bé $i+j=k+l$

$i-k=j-l$ o bé $i-k=l-j$

Tenint en compte totes aquestes consideracions, podem aplicar l'esquema retroactivament per col·locar les vuit reines d'una manera realment eficient. Per a fer-ho, reformulem el problema com un problema de cerca en un arbre. Diem que un vector $V_{1\dots k}$ d'enters entre 1 i 8 és $k$-prometedor per $0\leq k\leq 8$ si cap de les $k$ reines col·locades en les posicions $(1,V_{1}),(2,V_{2}),\dots ,(k,V_{k})$ amenaça a cap de les altres. Les solucions del problema es corresponen als vectors 8-prometedors.

Establiment de l'algoritme

Sigui $N$ el conjunt de vectors de $k$-prometedors, definim $G=(N,A)\,$ el graf dirigit tal que $(U,V)\in A$ si i només si existeix un enter $k$, amb $0\leq k\leq 8$ tal que

• $U$ és $k$-prometedor
• $V$ és $(k+1)$-prometedor
• $U_{i}=V_{i}$ per a tot $i\in \{1,\dots ,k\}$

L'arrel de l'arbre $G$ resultant és el vector buit corresponent a $k=0$, i les fulles corresponen a solucions $k=8$ o bé posicions sense sortida $k<8$. Les solucions del problema es poden obtenir explorant l'arbre. Tot i això, no es genera l'arbre explícitament per explorar-lo després, sinó que els nodes es van generant i abandonant en el transcurs de l'exploració mitjançant una cerca en profunditat.

Cal decidir si un vector és $k$-prometedor, sabent que és una extensió d'una vector $(k-1)$-prometedor. Únicament és necessari comprovar l'última reina que calgui afegir. Això es pot accelerar si s'associa a cada node prometedor el conjunt de columnes i el de diagonals ascendents i descendents controlades per les reines que ja s'han col·locat.

L'algorisme comprova primer si $k=8$; si es dona aquest cas vol dir que és un vector 8-prometedor, és a dir que compleix totes les restriccions és una solució vàlida. Si $k<8$ l'algorisme explora les extensions $(k+1)$-prometedores realitzant un cicle de 1 a 8 al qual es comprova si les reines col·locades es veuen les unes a les altres. Si no és el cas es realitza una recurrència en la qual s'incrementa $k$ (es busca el $(k+1)$-prometedor) i s'afegeix una nova fila, columna i diagonals al conjunt de restriccions per la propera iteració.

Generalització per n reines

El problema de les vuit reines es pot generalitzar per a $n$ reines. El problema consisteix en col·locar $n$ reines en un escaquer de $n\times n$ de manera que cap d'elles sigui amenaçada.

Podeu consultar el nombre de solucions possibles totals per cada $n$, incloent translacions, simetries i rotacions, a l'OEIS A000170

Podeu consultar el nombre de solucions úniques possibles per cada $n$ a l'OEIS A002562

Solucions al problema de les vuit reines

El problema de les vuit reines té 92 solucions, de les quals 12 són essencialment diferents, és a dir les 92 solucions existents es poden obtenir a partir de translacions, simetries i rotacions de les 12 solucions úniques, que es mostren a continuació:

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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 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 Solució única 12

Bibliografia

• Gomez Campos, Luis Ernesto. Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press, 2004. ISBN 0-691-11503-6. 
• Brassard, Gilles; Bratley, Paul. «Exploración de grafos». A: Fundamentos de Algoritmia (en castellà). Madrid: Prentice Hall, 1997. ISBN 84-89660-00-X. 

Vegeu també

• Puzle d'escacs

Enllaços externs

• Weisstein, Eric W., «QueensProblem» a MathWorld (en anglès).
• N-Queens solvers in many programming languages