#include?
#include?
#include?
#include?
#include?


ifstream?infile（“input.txt“）;
ofstream?outfile（“output.txt“）;


const?unsigned?long?maxshort=65536L;
const?unsigned?long?multiplier=1194211693L;
const?unsigned?long?adder=12345L;

//隨機(jī)數(shù)類
class?RandomNumber
{
public:
	//構(gòu)造函數(shù)，缺省值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子
	RandomNumber（unsigned?long?s=0）;
	//產(chǎn)生0:n-1之間的隨機(jī)整數(shù)
	unsigned?short?Random（unsigned?long?n）;
	//產(chǎn)生[01）之間的隨機(jī)實(shí)數(shù)
	double?fRandom（void）;
private:
	//當(dāng)前種子
	unsigned?long?randSeed;
};

//產(chǎn)生種子
RandomNumber::RandomNumber（unsigned?long?s）
{
	if（s==0）
		randSeed=time（0）;?//用系統(tǒng)時(shí)間產(chǎn)生種子
	else
		randSeed=s;???????//由用戶提供種子
}

//產(chǎn)生0:n-1之間的隨機(jī)整數(shù)
unsigned?short?RandomNumber::Random（unsigned?long?n）
{
	randSeed=multiplier*randSeed+adder;
	return?（unsigned?short）（（randSeed>>16）%n）;
}

//產(chǎn)生[01）之間的隨機(jī)實(shí)數(shù)
double?RandomNumber::fRandom（void）
{
	return?Random（maxshort）/double（maxshort）;
}

//2維數(shù)組類
template?
void?Make2DArray（T**?&x?int?rows?int?cols）
{
????????//創(chuàng)建行指針
????????x?=?new?T*?[rows];
????????//為每行分配空間
????????for（int?j?=?0;?j?????????{
????????????????x[j]?=?new?T[cols];
????????}
}


template?
void?Delete2DArray（T**?&x?int?rows）
{
????????//釋放為每行所分配的空間
????????for（int?j?=?0;?j?????????{
????????????????delete[]?x[j];
????????}
????????//刪除行指針
????????delete[]?x;
????????x?=?NULL;
}

class?Queen
{
	friend?bool?nQueen（int）;
	private:
		bool?Place（int?k）;//測(cè)試皇后k置于第x[k]列的合法性
		bool?Backtrack（int?t）;//解n后問(wèn)題的回溯法
		bool?ddBacktrack（int?t）;//迭代法
		int?Placenum（int?k）;//暫時(shí)不用計(jì)算已放置皇后個(gè)數(shù)
		int?QueensLV（int?stopVegas）;//隨機(jī)放置n個(gè)皇后的拉斯維加斯算法
		bool?ctrl（int?m）;//測(cè)試皇后是否已控制棋盤
		int?n//皇后個(gè)數(shù)
			*x*y*a**z;//x[k]表示：第k行皇后置于第x[k]列
?????????????????????????//y是用來(lái)記錄每行皇后可行位置
?????????????????????????//a是用來(lái)記錄最優(yōu)解皇后位置
?????????????????????????//z是用來(lái)記錄皇后控制的方格
		int?cminc;//cmin記錄最優(yōu)皇后個(gè)數(shù)，c為當(dāng)前個(gè)數(shù)
		RandomNumber?rnd;//隨機(jī)數(shù)產(chǎn)生器定義在類里隨機(jī)效果更好
};

bool?Queen::Place（int?k）
{//測(cè)試皇后k置于第x[k]列的合法性x[k]和x[j]都大于0時(shí)候比較
	if（x[k]>0）
		for（int?j=1;j			if（（x[j]>0）&&（（abs（k-j）==abs（x[j]-x[k]））||x[j]==x[k]））
				return?false;
	return?true;
}

bool?Queen::ctrl（int?m）
{//測(cè)試皇后是否已控制棋盤m*m
	int?ijuvcount=0;
	for（i=1;i<=m;i++）
		for（j=1;j<=m;j++）?z[i][j]=0;//初始置0
	for（i=1;i<=m;i++）
	{
		if（x[i]>0）?//i行有皇后時(shí)
		{
			for（j=1;j<=m;j++）?{z[i][j]=1;z[j][x[i]]=1;}//i行x[i]列所有元素都控制
			for（u=iv=x[i];u>=1&&v>=1;u--v--）?z[u][v]=1;//（ix[i]）左上對(duì)角線所有元素都控制
			for（u=iv=x[i];u<=m&&v>=1;u++v--）?z[u][v]=1;//（ix[i]）左下對(duì)角線所有元素都控制
			for（u=iv=x[i];u>=1&&v<=m;u--v++）?z[u][v]=1;//（ix[i]）右上對(duì)角線所有元素都控制
			for（u=iv=x[i];u<=m&&v<=m;u++v++）?z[u][v]=1;//（ix[i]）右下對(duì)角線所有元素都控制
		}
	}
	for（i=1;i<=m;i++）
		for（j=1;j<=m;j++）?count+=z[i][j];
	return（count==m*m）;
}

bool?Queen::Backtrack（int?t）
{//解n后問(wèn)題的回溯法有解輸出true
	if（t>n）
		{//輸出一個(gè)解
//		for（int?i=1;i<=n;i++）
//			a[i]=x[i];
//		return?true;
		if（ctrl（n）&&（c<=cmin））
		{
			a

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件??????68414??2007-08-11?11:12??皇后控制問(wèn)題\queen.pdf

?????文件???????6028??2007-08-11?11:11??皇后控制問(wèn)題\queen1.cpp

?????文件?????140288??2007-08-11?11:11??皇后控制問(wèn)題\queen1.ppt

?????文件???????4617??2010-12-21?14:20??皇后控制問(wèn)題\queen2.cpp

?????文件?????224768??2007-08-11?11:11??皇后控制問(wèn)題\queen2.ppt

?????文件???????3176??2010-12-21?14:25??皇后控制問(wèn)題\queen3.cpp

?????文件?????185344??2007-08-11?11:12??皇后控制問(wèn)題\queen3.ppt

?????文件??????????3??2010-12-21?14:15??皇后控制問(wèn)題\input.txt

?????文件?????????19??2010-12-21?14:28??皇后控制問(wèn)題\output.txt

?????文件?????597976??2010-12-21?14:20??皇后控制問(wèn)題\queen2.exe

?????文件?????594415??2010-12-21?14:25??皇后控制問(wèn)題\queen3.exe

?????目錄??????????0??2007-08-11?11:12??皇后控制問(wèn)題

-----------?---------??----------?-----??----

??????????????1825048????????????????????12