#include <iostream>
using namespace std;
#define MAX 21
int arr[MAX]; //arr[i]=k,表示在第i行的第k个位置放置一个皇后
int sum;//计数解的个数
int n;//记录几行几列
bool cmp(int row, int col) {//当前行和列
for (int i = 1; i < row; i++) {
if(col == arr[i] || abs(row-i) != abs(col - arr[i]))
return false;
}
return true;
}
void backTracking(int row) {
if (row == n) {
sum++; //找到了一个解
}
else {
for (int i = 1; i < n; i++) {//从第一列到最后一列
if (cmp(row, i)) {
arr[row] = i; //记录
backTracking(row + 1); //遍历下一行
}
arr[row] = 0;
}
}
}
int main() {
cin >> n;
backTracking(1);
cout << sum <<endl;
system("pause");
return 0;
}