代码如下

#include <cstdio>
using namespace std;

int n , a[18][18] , ok , can[18][18][55][55] , ans[18][8] , cnt;

void out()
{
    for (int i = 1; i <= n; i++)
        printf("%d" , ans[i][cnt]);
    puts("");
}

void dfs(int x , int y)
{
    if (ok == n)
    {
        if (cnt <= 3) out();
        cnt++;
        return;
    }
    if (can[x][y][n - (x - y)][x + y - 1])
    {
        if (y == n) dfs(x + 1 , 1);
        else dfs(x , y + 1);
    }
    can[x][y][n - (x - y)][x + y - 1] = 1;
    ans[x][cnt] = y;
    if (y == n) dfs(x + 1 , 1);
    else dfs(x , y + 1);
    can[x][y][n - (x - y)][x + y - 1] = 0;
    ans[x][cnt] = 0;
}

int main()
{
    scanf("%d" , &n);
    dfs(1 , 1);
    printf("%d" , cnt);
    
    return 0;
}