Se citeste un numar natural n. Generati, folosind metoda Backtracking, toate modurile de a aseza n regine pe o tabla de sah n x n astfel incat oricare doua regine sa nu se atace reciproc (sa nu se afle pe aceeasi linie, aceeasi coloana sau aceeasi diagonala).
- Date de intrare
- Se citeste numarul natural n.
- Date de iesire
- Se afiseaza toate solutiile, cate una pe linie: pentru fiecare solutie se afiseaza cele n numere de coloana ocupate de regine (regina de pe linia i se afla pe coloana a[i]), separate prin spatiu, in ordinea in care sunt generate (linie cu linie, coloane incercate in ordine crescatoare).
- Restrictii
- 1 <= n <= 9
Exemple
Exemplul 1
Intrare
1
Iesire
1
Exemplul 2
Intrare
4
Iesire
2 4 1 3 3 1 4 2