Aštuonių valdovių uždavinys


Pradinių duomenų failas:
valdoves.in  
Rezultatų failas:
valdoves.out  
Laiko apribojimas:
2 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Aštuonių valdovių uždavinys senas kaip ir pats šachmatų žaidimas. Uždavinys prašo rasti būdą išdėstyti aštuonias valdoves šachmatų lentoje taip, kad nei viena iš jų kitai neskelbtų šacho (taigi nebūtų vienoje eilėje, stulpelyje ar įstrižainėje su kita valdove). Žr. pavyzdį žemiau:

 

Šį uždavinį sprendė ir Karlas Frydrichas Gausas (Carl Friedrich Gauss), dažnai vadinamas garsiausiu visų laikų matematiku. Žinoma, jis ieškojo ne vieno būdo išdėstyti valdoves, o bendro sprendinio.

Tačiau šiandien mes galime pasitelkti kompiuterių pagalbą! Parašykite programą, kuri rastų, kaip išdėstyti N valdovių NxN matmenų šachmatų lentoje, bei kiek iš viso tokių sprendinių egzistuoja.

Pradiniai duomenys

Pradinių duomenų faile įrašytas vienintelis sveikas skaičius N (1 <= N <= 13).

Rezultatai

Pirmoje rezultato failo eilutėje, programa turi įrašyti skaičių būdų minėtu būdu galima idėstyti N valdovių NxN dydžio šachmatų lentoje. Jei egzistuoja bent vienas sprendinys, programa turi išvesti tokio išdėstymo schemą (bet kurią iš galimų). Schemoje tušti langeliai turi būti žymimi taško simboliu, o valdovės – raide V (žr. pavyzdį). Eilučių pabaigoje neturi būti nereikalingų tarpo simbolių.

Pavyzdžiai

Pradiniai duomenys Rezultatai
5
10
V.... 
..V.. 
....V
.V... 
...V.
8
92
V....... 
....V... 
.......V
.....V.. 
..V..... 
......V. 
.V...... 
...V....
3
0