Diferente pentru problema/damesah intre reviziile #7 si #37

Diferente intre titluri:

damesah
Problema Damelor

Diferente intre continut:

== include(page="template/taskheader" task_id="damesah") ==
    Se dau N dame si o tabla de sah de dimensiune NxN. Sa se gaseasca toate modalitatile de a aranja toate damele astfel incat oricare doua dame sa nu se atace. Doua dame se ataca daca se afla pe aceeasi linie,coloana sau diagonala.
    Se cere sa afişăm totalitatea modurilor în care pot fi aranjate cele N dame.
Se dau $N$ dame şi o tablă de şah de dimensiune $NxN$. Să se găsească toate modalităţile de a aranja toate damele astfel încât oricare două dame să nu se atace. Două dame se atacă dacă se află pe aceeaşi linie, coloană sau diagonală. Se cere să se afişeze prima soluţie în ordine lexicografică şi numărul total de soluţii.
h2. Date de intrare
Fişierul de intrare $damesah.in$ va contine o singura linie si anume numarul N.
Fişierul de intrare $damesah.in$ va contine pe prima linie numărul natural $N$, având semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $damesah.out$ se vor afla, separate prin spatiu, modurile in care pot fi aranjate cele N dame.
Un mod de aranjare reprezinta o matrice formata astfel:
* Daca la coordonatele (i,j) se va afla o dama se va afisa litera "D"
* Daca la coordonatele (i,j) va fi spatiu liber atunci se va afisa simbolul "*"
Î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
* $3 ≤ N ≤ 12$
* $4 ≤ N ≤ 13$
h2. Exemplu
table(example). |_. damesah.in |_. damesah.out |
| 4
| *D**
  ***D
  D***
  **D*
 
  **D*
  D***
  ***D
  *D**
| 2 4 1 3
2
|
 
h3. Explicaţie
...
h2. Explicatie
 
Pentru $N = 4$ dame, prima solutie generata va fi $2 4 1 3$. Fiecare numar $V[i]$ reprezinta coloana pe care se va afla dama de pe linia $i$. S-au gasit in total $2$ solutii.
 
h2. Indicatii de rezolvare
 
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/1086312?action=view-source.
== include(page="template/taskfooter" task_id="damesah") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
9573