#include <fstream>
#include <stdlib.h>

using namespace std;

int n, nr, sol[30], col[30], diag1[30], diag2[30];

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

void bk(int p, int l)
{
    int i;
    if(p > n)
        {
        if(nr < 1)
            {
            for(i = 1; i < p; i++)
                g << sol[i] << " ";
            g << "\n";
            }
        nr++;
        }
    else
            for(i = 1; i < n + 1; i++)
                if(!col[i] && !diag1[l - i] && !diag2[l + i])
                    {
                    sol[p] = i;

                    col[i] = 1;
                    diag1[l - i] = 1;
                    diag2[l + i] = 1;

                    bk(p + 1, l + 1);

                    col[i] = 0;
                    diag1[l - i] = 0;
                    diag2[l + i] = 0;
                    }
}

int main()
{
    f >> n;

    bk(1, 1);
    g << nr;

    return 0;
}