#include <bits/stdc++.h>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");

int N,Stack[22],Columns[22],Diagonals[22],SolNumber=0;

void write()
{
    if(SolNumber==0)
    {
        for(int i=1;i<=N;++i) g<<Stack[i]<< " ";
        g<<"\n";
    }
    SolNumber++;
}

void back(int level)
{
    if (level>N) write();
    else
        for (int i=1; i<=N; ++i)
        {
            if (!Columns[i]&&!Diagonals[level-i]&&!Diagonals[level+i])
            {
                Columns[i]=Diagonals[level-i]=Diagonals[level+i]=1;
                Stack[level]=i;
                back(level+1);
                Columns[i]=Diagonals[level-i]=Diagonals[level+i]=0;
            }
        }
}

int main()
{
    f>>N;
    back(1);
    g<<SolNumber;
}