Vuit reines

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

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 , 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'algoritme

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

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

abcdefgh
8
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
Solució única 1
abcdefgh
8
e8 blanques dama
b7 blanques dama
d6 blanques dama
g5 blanques dama
c4 blanques dama
h3 blanques dama
f2 blanques dama
a1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 2
abcdefgh
8
d8 blanques dama
b7 blanques dama
g6 blanques dama
c5 blanques dama
f4 blanques dama
h3 blanques dama
e2 blanques dama
a1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 3
abcdefgh
8
d8 blanques dama
f7 blanques dama
h6 blanques dama
c5 blanques dama
a4 blanques dama
g3 blanques dama
e2 blanques dama
b1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 4
abcdefgh
8
c8 blanques dama
f7 blanques dama
h6 blanques dama
a5 blanques dama
d4 blanques dama
g3 blanques dama
e2 blanques dama
b1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 5
abcdefgh
8
e8 blanques dama
c7 blanques dama
h6 blanques dama
d5 blanques dama
g4 blanques dama
a3 blanques dama
f2 blanques dama
b1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 6
abcdefgh
8
e8 blanques dama
g7 blanques dama
d6 blanques dama
a5 blanques dama
c4 blanques dama
h3 blanques dama
f2 blanques dama
b1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 7
abcdefgh
8
d8 blanques dama
a7 blanques dama
e6 blanques dama
h5 blanques dama
f4 blanques dama
c3 blanques dama
g2 blanques dama
b1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 8
abcdefgh
8
c8 blanques dama
f7 blanques dama
d6 blanques dama
a5 blanques dama
h4 blanques dama
e3 blanques dama
g2 blanques dama
b1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 9
abcdefgh
8
f8 blanques dama
b7 blanques dama
g6 blanques dama
a5 blanques dama
d4 blanques dama
h3 blanques dama
e2 blanques dama
c1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 10
abcdefgh
8
d8 blanques dama
g7 blanques dama
a6 blanques dama
h5 blanques dama
e4 blanques dama
b3 blanques dama
f2 blanques dama
c1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 11
abcdefgh
8
f8 blanques dama
d7 blanques dama
g6 blanques dama
a5 blanques dama
h4 blanques dama
b3 blanques dama
e2 blanques dama
c1 blanques dama
8
77
66
55
44
33
22
11
abcdefgh
Solució única 12

Referències

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

Bibliografia

Vegeu també

Enllaços externs

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!