#include <bits/stdc++.h>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int diagp[105],diags[105],sol[105],fr[105],n,nr;
void back1(int k)
{
    if (k>n)
    {
        nr++;
        if (nr==1)
        {
            for (int i=1;i<=n;i++)
            {
                g<<sol[i]<<" ";
            }
            g<<'\n';
        }
    }
    else
    {
        for (int j=1;j<=n;j++)
        {
            if (fr[j]==0&&diagp[k+j]==0&&diags[k-j+n]==0)
            {
                sol[k]=j;
                fr[j]=1;
                diagp[k+j]=1;
                diags[k-j+n]=1;
                back1(k+1);
                fr[j]=0;
                diagp[k+j]=0;
                diags[k-j+n]=0;
            }
        }
    }
}
int main()
{
    f>>n;
    back1(1);
    g<<nr;
    return 0;
}