NQueens Project

NQueens@home

Home: http://nqueens.ing.udec.cl/

Impulsor: Secció d'Ensenyament de la Facultat d'Enginyeria a la Universitat de Concepción a Xile.

Àrea: Matemàtiques

Objectius:
Trobar totes les solucions al problema de N-Dames, de N=18 a N=26 (rècord mundial).
El problema N-Dames és col·locar N dames NxN sense que una d'elles pugui prendre l'altra segons les regles d'escacs, una dama pot prendre qualsevol peça situada a la seva columna o sobre una de les seves dos diagonals.

El problema es pot representar amb N variables (V i ∈ [1 .. N], i = 1 .. N), en representació de la posició de la columna de la dama de la línia i. De fet, ja que dues dames no poden estar en la mateixa línia, i que hi ha tantes dames com línies, hi ha exactament una i nomès una dama per línia.
Les limitacions imposades sobre les variables V i, són els següents:
per a tots i ≠ j:
* V i j ≠ V (no posar a dues dames en la mateixa columna).
* V i - V i ≠ j - j (no posar a dues dames en la mateixa diagonal NO-SE)
* V i + V j ≠ r + j (no posar dues dames en la mateixa diagonal NE-SO)
Per a més informació podeu veure l'article de la Viquipèdia Eight queens puzzle (en Anglès), on explica el problema de les vuit dames.