#include <iostream>
using namespace std;
int count=0;
void Output(int n,int *a)
{    int **b;
    count++;
    int i;    b=new int *[n];
    cout<<"第"<<count<<"解："<<endl;
    for(i=1;i<=n;i++)
    {b[i]=new int [n];
        b[i][a[i]]=1;
    }

    for(int s=1;s<=n;s++)
    {    int c=0;
        for(i=1;i<=n;i++)
        {    c++;
            
            if(b[s][i]==1)
                cout<<"*";
            else
                cout<<"O";
                if(c%n==0)
        cout<<endl;
        }

    }
}
bool find(int *a,int i,int k)
{ int j=1;
    while(j<k)
    {if((a[j]==i)||(abs(a[j]-i)==abs(j-k)))
        return false;
    j++;
    }
    return true;
}
void Quen(int k,int n,int *a)
{if(k>n)
    Output(n,a);
    else
        for(int i=1;i<=n;i++)
            if(find(a,i,k))
            {a[k]=i;
                Quen(k+1,n,a);
            }
}


int main()
{    int n;
    int *a;
    cout<<"皇后问题："<<endl;
    cin>>n;
    a=new int [n];
    cout<<n<<"皇后问题求解如下："<<endl;
    Quen(1,n,a);
    return 0;
}