h2. Date de ieşire

În fişierul de ieşire $damesah.out$ se vor găsi două linii. Pe prima linie va fi afişată prima soluţie în ordine lexicografică. Aceasta solutie este formata din $N$ numere, al $i$-lea numar reprezentand coloana pe care se afla dama de pe linia $i$. Pe cea de-a doua linie, se va gasi numărul total de soluţii.

În fişierul de ieşire $damesah.out$ se vor găsi două linii. Pe prima linie va fi afişată prima soluţie în ordine lexicografică. Aceasta solutie va fi formată din $N$ numere, al $i$-lea număr reprezentând coloana pe care se află dama de pe linia $i$. Pe cea de-a doua linie, se va găsi numărul total de soluţii.

h2. Restricţii

Aranjarea damelor pe tabla de sah este o problema clasica de backtracking. Metoda de rezolvare cu backtracking presupune generarea tuturor solutiilor si testarea lor daca sunt valide sau nu. O dama poate fi plasata pe tabla de sah daca pentru fiecare dama aranjata deja, aceasta nu se afla pe aceeasi coloana, linie sau diagonala cu niciuna dintre ele. Solutia se afla 'aici':job_detail/1086267?action=view-source .

Pentru a optimiza algoritmul, pentru fiecare dama de pe tabla de sah, se va marca, folosind vectori auxiliari linia, coloana si diagonala pe care este plasata aceasta. Astfel se poate verifica in complexitate $O(1)$ daca o dama poate fi pusa sau nu pe tabla de sah la o anumita pozitie. O astfel de solutie gasim 'aici':job_detail/1086238?action=view-source .

Pentru a optimiza algoritmul, pentru fiecare dama de pe tabla de sah, se va marca, folosind vectori auxiliari linia, coloana si diagonala pe care este plasata aceasta. Astfel se poate verifica in complexitate $O(1)$ daca o dama poate fi pusa sau nu pe tabla de sah la o anumita pozitie. O astfel de solutie gasim 'aici':job_detail/1086312?action=view-source.

== include(page="template/taskfooter" task_id="damesah") ==

9573