八皇后问题:在8*8格的棋盘上,放8个皇后,任意两个皇后不能在同一行,同一列,同一斜线上,求有几种摆法
　　n皇后问题:在n*n格的棋盘上,放n个皇后,任意两个皇后不能在同一行,同一列,同一斜线上,求有几种摆法
　　#include "stdafx.h"
　　#include <iostream>
　　#include <fstream>
　　using namespace std;
　　//非递归
　　void queen(int n)
　　{
　　int *c=new int [n];//记录列状态
　　int *d1=new int[2*n-1];//记录正对角线状态
　　int *d2=new int[2*n-1];//记录负对角线状态
　　int *lc=new int[n];//记录皇后在第n放的列数
　　int **Queen=new int *[n];//棋盘
　　for(int i=0;i<n;i++)//初始化
　　{
　　Queen[i]=new int[n];
　　for(int j=0;j<n;j++)
　　{
　　Queen[i][j]=0;
　　}
　　c[i]=0;
　　d1[i]=0;
　　d1[2*n-i-2]=0;
　　d2[i]=0;
　　d2[2*n-i-2]=0;
　　}
　　int line=0;//行
　　int column=0;//列
　　__int64 num=0;//可以摆放的数量
　　__int64 count=0;//考试大提示循环次数
　　while(line>=0)
　　{
　　while(column<n)
　　{
　　count++;
　　if(c[column]==0&&d1[line-column+n-1]==0&&d2[line+column]==0)//如果列,正负对角线都没有放,则为真
　　{
　　if(line==n-1)//如果到最后一行,则为真
　　{
　　Queen[line][column]=1;
　　num++;//摆放数量加1
　　Queen[line][column]=0;
　　break;
　　}
　　else
　　{
　　//记录摆放状态
　　Queen[line][column]=1;
　　c[column]=1;
　　d1[line-column+n-1]=1;
　　d2[line+column]=1;
　　lc[line]=column;
　　line++;//进入下一行,从第0列开始
　　column=0;
　　}
　　}
　　else
　　column++;
　　}
　　count++;
　　//如果这一行,所有格都不能放,则退一行,则从上一行上次摆放的下一列开始遍历
　　line--;
　　if(line>=0)
　　{
　　column=lc[line];
　　Queen[line][column]=0;
　　c[column]=0;
　　d1[line-column+n-1]=0;
　　d2[line+column]=0;
　　column++;
　　}
　　}
　　cout<<num<<'\t'<<count<<endl;;
　　}
　　//递归
　　void queen1(int i,int**Queen,int *a,int *d1,int *d2,int& n,int &QueenNumber,__int64&count)
　　{
　　int iColumn;
　　for(iColumn=0;iColumn<n;iColumn++)
　　{
　　count++;
　　if(a[iColumn]==0&&d1[i-iColumn+n-1]==0&&d2[i+iColumn]==0)
　　{
　　Queen[i][iColumn]=1;
　　a[iColumn]=1;
　　d1[i-iColumn+n-1]=1;
　　d2[i+iColumn]=1;
　　if(i<n-1)
　　queen1(i+1,Queen,a,d1,d2,n,QueenNumber,count);
　　else
　　{
　　QueenNumber++;
　　/*
　　fstream outstuf;
　　outstuf.open("out.txt",ios::out|ios::app);
　　for(int i=0;i<8;i++)
　　{
　　for(int j=0;j<8;j++)
　　{
　　outstuf<<Queen[i][j]<<" ";
　　}
　　outstuf<<"\r\n";
　　}
　　outstuf<<"\r\n";
　　outstuf.close();*/
　　}
　　Queen[i][iColumn]=0;
　　a[iColumn]=0;
　　d1[i-iColumn+n-1]=0;
　　d2[i+iColumn]=0;
　　}
　　}
　　}
　　void queendg(int n)
　　{
　　int *c=new int [n];
　　int *d1=new int[2*n-1];
　　int *d2=new int[2*n-1];
　　int **Queen=new int *[n];
　　for(int i=0;i<n;i++)
　　{
　　Queen[i]=new int[n];
　　for(int j=0;j<n;j++)
　　{
　　Queen[i][j]=0;
　　}
　　c[i]=0;
　　d1[i]=0;
　　d1[2*n-i-2]=0;
　　d2[i]=0;
　　d2[2*n-i-2]=0;
　　}
　　int QueenNumber=0;
　　__int64 count=0;
　　queen1(0,Queen,c,d1,d2,n,QueenNumber,count);
　　cout<<QueenNumber<<'\t'<<count<<endl;;
　　}
　　int _tmain(int argc, _TCHAR* argv[])
　　{
　　queendg(8);
　　queen(8);
　　return 0;
　　}
　　考试大提示:经测试
　　queen(16)共14772512种放法,用时206秒
　　queendg(16)共14772512种放法,用时248秒 来源:考试大网