我的想法是遍历正方形的每个点，如果合法就放置，如果遍历到最后一个点的下一个点就检查当前的摆放是否合法。（DFS里的参数s没用，x为横坐标，y为纵坐标，z是未放置的个数）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
//#pragma G++ optimize(2)
//#pragma G++ optimize(3, "Ofast", "inline")
using namespace std;
int n, ans;
bool s1[100], s2[100], s3[100], s4[100];
queue<int> q;
void DFS(int s, int x, int y, int z) {
	if(x > n) {
		DFS(s, 1, y + 1, z);
		return;
	}
	if(y > n) {
		if(z == 0) {
			if(ans < 3) {
				for(int i = 0; i < q.size(); i++) {
					printf("%d ", q.front());
					q.push(q.front());
					q.pop();
				}
				printf("\n");
			}
			ans++;
		}
		return;
	}
	if(!s1[x] && !s2[y] && !s3[x + y] && !s4[x - y + n]) {
		s1[x] = true;
		s2[y] = true;
		s3[x + y] = true;
		s4[x - y + n] = true;
		q.push(x);
		DFS(s, 1, y + 1, z - 1);
		s1[x] = false;
		s2[y] = false;
		s3[x + y] = false;
		s4[x - y + n] = false;
		q.pop();
	}
	DFS(s, x + 1, y, z);
}
int main() {
	scanf("%d", &n);
	DFS(0, 1, 1, n);
	printf("%d", ans);
	return 0;
}