DOCUMENTACIÓ REINES


Descripció

Donat un tauler d'escacs de "n" files per "n" columnes, es pretén col·locar "n" reines de tal manera que no es matin entre elles. O sigui, posar les peces en diferents files, columnes i diagonals.

Per evitar cicles, a cada pas decidirem en quina fila de cada columna posem la reina.

Exemple:

El tauler A, amb un sol moviment pot generar els taulers B o C.

A

Q

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

B

Q

·

·

·

·

·

·

·

·

Q

·

·

·

·

·

·

C

Q

·

·

·

·

·

·

·

·

·

·

·

·

Q

·

·

Heurístiques i Cost

- Heurístiques:

- Cost: Nombre de reines col·locades.

- Poda: No afegim a la llista de nodes a tractar els nodes que tenen una columna amb totes les caselles atacades per alguna reina.

- Exemples:

-

X

Q

X

X

X

-

X

-

X

Q

-

X

X

-

-

X

-

Q

X

X

-

-

X

X

Q

-

X

X

-

-

X

-

-

X

-

Q

X

X

(Les "Q" representen les reines, les "X" les caselles atacades i les "-" les no tractades)

Primer exemple:

Segon exemple:

Tercer exemple:

Inici Anterior