利用深搜枚举所有情况。但直接搜索会超时，必须剪枝。根据八皇后的对称关系。如果n 为偶数，则只需对第一行搜一半，然后搜出来的数目再乘以2；如果为奇数，对第一行中点以前的搜索，然后搜出来的数目乘以2再加上中点搜出来的数目。这样会提高一倍的速度。但因为n = 6时，由于要输出前三种方案，这三种方案，恰好又一种必须经过第一行后半部分的搜索才搜得到。所以必须对其做点处理。

 

/*
PROG: checker
LANG: C
*/
#include<stdio.h>
#define max 30
int R[3][max],  co[ max], up[max], down[max], s[max];
int k, n;
void Dfs(int depth, int row, int col)
{
    int i, j ;
    s[depth++] = col + 1;
    if (depth == n)
    {
        if (k < 3)
        {
            for (i = 0; i < depth; i++)
            {
                R[k][i] = s[i];
            }
        }
        k++;
    }
    else
    {
        co[col] = 0;
        up[row + col] = 0;
        down[col + n - row - 1] = 0;
        i = row + 1;
        if (i < n)
        {
            for (j = 0; j < n; j++)
            {
                /*if (!co[j] || !up[i + j] || !down[j + n - i - 1])
                {
                }
                else
                {
                    Dfs(depth, i, j);
                }*/

                if (co[j] && up[i + j] && down[j + n - i - 1])
                {
                    Dfs(depth, i, j);
                }
            }
        }
        co[col] = 1;
        up[row + col] = 1;
    down[col + n - row - 1] = 1;
    }
    
};
int main()
{
    FILE * fin = fopen("checker.in", "r");
    FILE * fout = fopen("checker.out", "w");
    int i, j, m, sum;
    fscanf(fin, "%d", &n);
    for (i = 0; i < max; i++)
    {
        co[i] = 1;
        up[i] = 1;
        down[i] = 1;
    }
    k = 0;
    if (n > 6)
    {
        if (n % 2 == 0)
        {
            m = 0;
        }
        else
        {
            m = 1;
        }
        for (i = 0; i < n / 2; i++)
        {
            Dfs(0,     0, i);
        }
        sum = k;
        if (m)
        {
            Dfs(0, 0, n / 2);
        }
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n - 1; j++)
            {
                fprintf(fout, "%d ", R[i][j]);
            }
            fprintf(fout, "%d\n", R[i][j]);
        }
        if (m)
        {
            fprintf(fout, "%d\n", sum * 2 + k - sum );
        }
        else
        {
            fprintf(fout, "%d\n", sum * 2);
        }
    }
    else
    {
        for (i = 0; i < n; i++)
        {
            Dfs(0,     0, i);
        }
        for (i = 0; i < 3; i++)
        {
            for (j = 0; j < n - 1; j++)
            {
                fprintf(fout, "%d ", R[i][j]);
            }
            fprintf(fout, "%d\n", R[i][j]);
        }
        fprintf(fout, "%d\n", k);
    }
        
    return 0;
}