Se consideră o tablă de șah de dimensiune n. Să se plaseze pe tablă n regine astfel încât să nu existe două regine care să se atace.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran o singură configurație validă a tablei de șah. Ea va fi alcătuită din n linii cu câte n caractere - sau *, separate prin câte un spațiu. Caracterul - reprezintă o poziție liberă de pe tablă, iar caracterul * reprezintă o poziție de pe tablă ocupată de o regină.

Restricții și precizări

• 4 ≤ n ≤ 10;
• două regine se atacă dacă se află pe aceeași linie, aceeași coloană sau aceeași diagonală;
• orice configurație validă a tablei este acceptată.

Exemplu

Intrare

4

Ieșire

- - * - 
* - - - 
- - - * 
- * - - 

SOLUTIE

#include <iostream>
#include <cmath>
using namespace std;

int n,  sol=0;
double v[100];
void afisare()
{
      sol=1;
      for(int i=1;i<=n;i++)
      {
            for(int j=1;j<=n;j++)
            {
                  if(v[i]==j)
                        cout<<"* ";
                  else cout<<"- ";
            }
            cout<<'\n';
      }
}
int valid(int k)
{
      for(int i=1;i<k;i++)
      {
            if(v[i]==v[k]||(abs(v[k]-v[i])==(k-i)))
                  return 0;
      }
      return 1;
}
int solutie(int k)
{
      return k==n;
}
void back(int k)
{
      for(int i=1;i<=n;i++)
      {
            v[k]=i;
            if(valid(k))
            {
                  if(solutie(k)&&sol==0)
                  {
                        afisare();
                  }
                  else back(k+1);
            }
      }
}
int main()
{
    cin>>n;
    back(1);
    return 0;
}