Nova secció: Plantejament
m (neteja i estandardització de codi) |
(Nova secció: Plantejament) |
||
|
| tright
|
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|ql|__
El problema concret de 8 × 8 té 92 solucions diferents.<ref>{{ref-web|cognom=Rubio|nom=Isabel|url= https://elpais.com/elpais/2017/09/04/ciencia/1504535610_082169.html| consulta=6 setembre 2017|títol=Un millón de dólares para quien resuelva este “simple” enigma de ajedrez| editor= [[El País]] |data=6 setembre 2017|llengua=castellà}}</ref>
== Plantejament ==
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 <math>fila - columna</math>, mentre que per la diagonal ascendent es compleix que tenen el mateix valor <math>fila + columna</math>. Per tant, si tenim dues reines en les posicions <math>(i, j)</math> i <math>(k, l)</math> estan a la mateixa diagonal [[si i només si]]:
: <math>i-j=k-l</math> o bé <math>i+j=k+l</math>
: <math>i-k=j-l</math> o bé <math>i-k=l-j</math>
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 [[Arbre (teoria de grafs)|cerca en un arbre]]. Diem que un vector <math>V_{1\dots k}</math> d'enters entre 1 i 8 és <math>k</math>-prometedor per <math>0\leq k\leq8</math> si cap de les <math>k</math> reines col·locades en les posicions <math>(1,V_1),(2,V_2),\dots,(k,V_k)</math> amenaça a cap de les altres. Les solucions del problema es corresponen als vectors 8-prometedors.
=== Establiment de l'algoritme ===
Sigui <math>N</math> el conjunt de vectors de <math>k</math>-prometedors, definim <math>G=(N,A)\,</math> el [[Graf (matemàtiques)|graf]] dirigit tal que <math>(U,V)\in A</math> si i només si existeix un enter <math>k</math>, amb <math>0\leq k\leq8</math> tal que
* <math>U</math> és <math>k</math>-prometedor
* <math>V</math> és <math>(k+1)</math>-prometedor
* <math>U_i=V_i</math> per a tot <math>i\in\{1,\dots,k\}</math>
L'arrel de l'arbre <math>G</math> resultant és el vector buit corresponent a <math>k = 0</math>, i les fulles corresponen a solucions <math>k = 8</math> o bé posicions sense sortida <math>k < 8</math>. 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 <math>k</math>-prometedor, sabent que és una extensió d'una vector <math>(k-1)</math>-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 <math>k=8</math>; 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 <math>k<8</math> l'algorisme explora les extensions <math>(k+1)</math>-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 <math>k</math> (es busca el <math>(k+1)</math>-prometedor) i s'afegeix una nova fila, columna i diagonals al conjunt de restriccions per la propera iteració.
== Referències ==
| |||