Vuit reines

problema de raonament lògic

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.

abcdefgh
8
Chessboard480.svg
d8 blanques dama
g7 blanques dama
c6 blanques dama
h5 blanques dama
b4 blanques dama
e3 blanques dama
a2 blanques dama
f1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Una de les possibles solucions.

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.[1]

PlantejamentModifica

Degut a 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  , mentre que per la diagonal ascendent es compleix que tenen el mateix valor  . Per tant, si tenim dues reines en les posicions   i   estan a la mateixa diagonal si i només si:

  o bé  
  o bé  

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   d'enters entre 1 i 8 és  -prometedor per   si cap de les   reines col·locades en les posicions   amenaça a cap de les altres. Les solucions del problema es corresponen als vectors 8-prometedors.

Establiment de l'algoritmeModifica

Sigui   el conjunt de vectors de  -prometedors, definim   el graf dirigit tal que   si i només si existeix un enter  , amb   tal que

  •   és  -prometedor
  •   és  -prometedor
  •   per a tot  

L'arrel de l'arbre   resultant és el vector buit corresponent a  , i les fulles corresponen a solucions   o bé posicions sense sortida  . 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  -prometedor, sabent que és una extensió d'una vector  -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  ; si es dóna aquest cas vol dir que és un vector 8-prometedor, és a dir que compleix totes les restriccions és una solució vàlida. Si   l'algorisme explora les extensions  -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   (es busca el  -prometedor) i s'afegeix una nova fila, columna i diagonals al conjunt de restriccions per la propera iteració.

Generalització per n reinesModifica

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

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

Solucions al problema de les vuit reinesModifica

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

abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 1
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 2
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 3
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 4
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 5
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 6
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 7
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 8
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 9
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 10
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 11
abcdefgh
8
 
 
 
 
 
 
 
 
 
8
77
66
55
44
33
22
11
abcdefgh
Solució única 12

ReferènciesModifica

  1. Rubio, Isabel. «Un millón de dólares para quien resuelva este “simple” enigma de ajedrez» (en castellà). El País, 06-09-2017. [Consulta: 6 setembre 2017].

BibliografiaModifica

Enllaços externsModifica

Vegeu tambéModifica