60分

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[22], b[22], c[22], d[22], cnt=0, n;
void dfs(int i) {	//给第i层放皇后 
    if(i==n+1) {
        cnt++;
        if(cnt<=3)
        {
        	for(int i=1; i<=n; i++) {
     	   		cout << a[i] <<' ';
   			}
   			cout << endl;
		}
        return;
    }
    for(int j=1; j<=n; j++) {
        if(!b[j]&&!c[i-j+n]&&!d[i+j]) {
            a[i] = j;
            b[j] = true;
            c[i-j+n] = true;
            d[i+j] = true;
            dfs(i+1);
            b[j] = false;
            c[i-j+n] = false;
            d[i+j] = false;
        } 
    }	
} 
int main() {
	cin >> n;
    dfs(1);
    cout << cnt;
    return 0;
}