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秒
最新评论