10
思路：假设我们现在把皇后放在第一个格子，那么根据题目上的限制，那么下一个皇后放置的位置和之前放的不能在同一行，同一列，也不能在一个斜角上。
如图所示：
那么我们可以得到下一张图
这样我们也就知道后来的皇后可以放在那些点 不可以放在那些点 从图中我们不难看出(0,1)就是我们下次要放置皇后的地方，但是这个点是不满足条件的，所以我们要回溯，返回到上一点的状态，往下一个点查找，直到可以找到允许放置皇后的点，那么下一个可以放置皇后的点就是(1,2)
就这样一直查找下去 直到可以在这个棋盘上可以放置n个皇后。
如果放置在第一个点不行，那么我们把皇后放在下一个点试试。如图：
然后再按照之前的步骤查找。
基本思路我们有了，那么我们怎么保证放置的皇后不在同一列，同一个斜角呢？
首先我们有一个数组visit[n]，n是要放置的皇后的个数，那么我们可以visit[i]=1表示我在第i列有放置皇后（但是不知道在哪一行），那么我就不能在在第i列放置皇后；再说同一斜角，我们把n个皇后编号，然后我们再map数组里面存我们把几号皇后放置在哪个点，那么我们可以根据皇后的位置来算出它们是否成斜角
dis[sum] - dis[j] == (j - sum)||dis[sum] - dis[j] == (sum - j)
最后，只要我们按照要求把n个皇后放置在棋盘上，就ok了。
注意：这道题一定要先进行打表，否则会超时的！！！！
代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int dis[100], vis[100], jie[100]; int n, ans; void dfs(int sum) { int flag; if(sum==n+1) { ans++; return ; } for(int i = 1; i <= n; i++) { if(vis[i]==0) { dis[sum] = i; flag = 1; for(int j = 1; j <= sum - 1; j++) { if(dis[sum] - dis[j] == (j - sum)||dis[sum] - dis[j] == (sum - j)) { flag = 0; break; } } if(flag) { vis[i] = 1; dfs(sum + 1); vis[i] = 0; } } } } int main() { for(int i = 1; i <= 10; i++) { ans = 0; n = i; memset(dis, 0, sizeof(dis)); memset(vis, 0, sizeof(dis)); dfs(1); jie[i] = ans; } while(cin >> n) { if(n==0) break; cout << jie[n] << endl; } return 0; }
