#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, j;
    if(p > n)
        {
        if(nr < 1)
            {
            for(i = 1; i < p; i++)
                g << sol[i] << " ";
            g << "\n";
            }
        nr++;
        }
    else
        for(i = l; i < n + 1; i++)
            for(j = 1; j < n + 1; j++)
                if(!col[j] && !diag1[i - j] && !diag2[i + j])
                    {
                    sol[p] = j;

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

                    bk(p + 1, i + 1);

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

int main()
{
    f >> n;

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

    return 0;
}