#include <bits/stdc++.h>
using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int N,Stack[22],Columns[22],Diagonalsl[44],Diagonalsr[44];
constexpr int SolNumber[] = { 0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184 };
#define Diagonalsl (Diagonalsl+22)

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

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

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