#include<iostream>
using namespace std;
void dfs(int i);//i表示行数
int sum;//sum为答案的总数
bool flag_l[100];//左对角线的标记 '/'
bool flag_r[100];//右对角线的标记 '\'
bool flag_col[100];//列的标记
int n;//因为dfs中要用,所以定义为全局变量
int answers[100];//结果
int main(void){
cin>>n;
dfs(1);//从第一行;
cout<<sum;
return 0;
}
void dfs(int i){//深度搜索
int j;//j表列数
if(i>n){//递归结束的条件
sum++;
if(sum>3) return ;
for(int k=1;k<=n;k++) cout<<answers[k]<<" ";
cout<<endl;
return ;
}
for(j=1;j<=n;j++){
if(!flag_col[j]&&!flag_r[j+i]&&!flag_l[i-j+n])//平移，因为害怕是负数，可移动大于n的数
{
answers[i]=j;
flag_col[j]=1;
flag_r[j+i]=1;
flag_l[i-j+n]=1;
dfs(i+1);//行向下移动
//回溯，返回上一行
flag_col[j]=0;
flag_r[j+i]=0;
flag_l[i-j+n]=0;
}
}
}
