Kuningattaret

Shakissa kuningatar voi liikkua vaaka-, pysty- tai vinosuuntaisesti. Tehtävänäsi on laskea, kuinka monella tavalla kaksi kuningatarta voidaan sijoittaa n x n -shakkilaudalle niin, että ne eivät uhkaa toisiaan.

Esimerkiksi tapauksessa n = 3 mahdollisuudet ovat:

K..   K..   .K.   .K.   ..K   ..K   ...   ...
..K   ...   ...   ...   K..   ...   K..   ..K
...   .K.   K..   ..K   ...   .K.   ..K   K..

Tapauksessa n = 10 mahdollisuuksia on jo 3480.

Voit olettaa, että n on kokonaisluku väliltä 1–50.

Esimerkki 1

Anna koko: 3
Vastaus: 8

Esimerkki 2

Anna koko: 10
Vastaus: 3480