N皇后（递归算法）

问题描述：N皇后问题是一个以国际象棋为背景的问题：如何能够在 n*n 的国际象棋棋盘上放置N个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。输入n，有多少种摆放的情况？

此题是我第一次接触递归算法的题目

第一行输入测试次数t；

输入测试的行数，输出总数

1       1  2       0  3       0  4       2  5       10  6       4  7       40  8       92  9       352  10      724  11      2680  12      14200  13      73712  14      365596  15      2279184  16      14772512  17      95815104  18      666090624  19      4968057848  20      39029188884  21      314666222712  22      2691008701644  23      24233937684440  24      227514171973736  25      2207893435808352  

代码实现

#include<bits/stdc++.h>using namespace std;int c=0;int cheak(int x[],int nowhang){ //判断是否在同一列，在对角  int i; for(i=1;i<nowhang;i++) if(x[i]==x[nowhang]||fabs(i-nowhang)==fabs(x[i]-x[nowhang])) return 0; return 1;}void queen(int n,int x[],int now){ //从第一行开始x=1  int i; for(i=1;i<=n;i++) { x[now]=i;//每一次从第一列开始往最后一列放  if(cheak(x,now)==1) { if(now==n)//放到最后一行，计数++  c++; else queen(n,x,now+1);//否则继续往下一行放  } }}int main(){ int t,n,x[25]; cin>>t; while(t--) { cin>>n; queen(n,x,1); cout<<c<<endl; c=0; } return 0; }