#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> temp;
vector<vector<int> > ans;
int L[3][30];//代表了所有的信息
int n;
void dfs(int cur)
{
if(cur == n)
{
ans.push_back(temp);
return ;
}
for(int i=0;i<n;i++)//枚举当前行的列值
{
if(L[0][i] || L[1][cur+i] || L[2][cur-i+n] ) continue;//|| !ok(cur,i)) continue;
temp.push_back(i+1);
L[0][i] = L[1][cur+i] = L[2][cur-i+n] = 1;
//这里为啥是i , cur + i, cur-i+n呢?
//i代表的是列,这个没问题,如果列未访问过那么值为0
//cur+i代表的是副对角线
//我们看下面这个矩阵
/*
1 2 3 对于(1,2)这个位置的元素,它的副对角线是(2,1),那么2+1就对应了副对角线的一一对应关系
1 0 0 0 可能还不是特别让人接受,我们看最长的那个副对角线,(1,3),(2,2),(3,1),是不是详细明了了
2 0 0 0
3 0 0 0 同时,对于cur+n-i也就是对于主对角线的一一映射关系了,小伙伴仿照上边的副对角线进行判断吧...
tips:(cur,i) -> (n-i,cur)
*/
dfs(cur+1);
L[0][i] = L[1][cur+i] = L[2][cur-i+n] = 0;
temp.pop_back();
}
}
bool cmp(vector<int> a,vector<int> b)
{
for(int i=0;i<n;i++)
if(a[i] != b[i])
return a[i] < b[i];
}
void print(vector<int> a)
{
for(int i=0;i<n;i++)
printf("%d%c",a[i]," \n"[i==n-1]);
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)//枚举第一行的所有可能情况
{
temp.clear();
temp.push_back(i+1);
L[0][i] = L[1][i] = L[2][n-i] = 1;//分别表示该行,该副对角线以及主对角线 分别对应0,1,2
dfs(1);
L[0][i] = L[1][i] = L[2][n-i] = 0;
temp.pop_back();
}
//sort(ans.begin(),ans.end(),cmp);由于我们搜索的顺序就是字典序,可以不用进行排序,不然13的时候会TLE
for(int i=0;i<3 && i < ans.size();i++)
print(ans[i]);
printf("%d\n",ans.size());
return 0;
}