| Problema 1: De quantes formes es poden posar les
huit dames (reines) en un tauler d'escacs sense que cap n'ataque una
altra.
La fig. 1a mostra una solució particular. Per a trobar totes les solucions anem a transformar aquest problema en un problema numèric.
Les dames ataquen en horitzontal, vertical i diagonal. De les dues primeres formes (horitzontal i vertical) obtenim que cadascuna de les reines ha d'estar en una filera i una columna diferents. Així, cada posició correspon a una ordenació (permutació és la paraula exacta) dels nombres 1 al 8 on que indiquen la filera ocupada en cada columna. Per exemple, la Fig. 1a mostra la permutació (8,4,1,3,6,2,7,5) perquè en la columna primera ocupem la filera 8, en la columna segona la filera 4, en la columna tercera la filera 1,... En general, cada possibilitat es pot representar per una permutació (ai)i=1...8 on la dama situada en la columna i està també en la filera ai. En l'exemple, a1 = 8, a2 = 4,... Però cal afegir que les dames també ataquen les caselles disposades en les diagonals que ocupen. Dir que dues dames estan en diagonals diferents és el mateix que dir que entre dues posicions ocupades, l'increment de columnes és diferent a l'increment de fileres tant de forma ascendent (+) com de forma descendent (-). Aquesta condició es pot escriure amb termes matemàtic d'aquesta forma: |ai – aj| ¹ |i – j|. Hem tingut en compte aquestos detalls i ens hem ajudat en
un Les solucions que dóna aquest programa les hem escrites tot seguit mantenint el criteri esmentat:
|
