#include?
#include?
#include?
#include?
using?namespace?std;



void?constructiveMethod（?int?n?）;
bool?conflicting（const?int?q[]int?n?int?i）;
void?constructNext（int?q[]?int?n?int?i）;
void?repairApproach（?int?n?）;
bool?repair（?int?q[]?int?n?int&?maxConf?）;
int?getConfNum（const?int?q[]?int?n?int?i?）;
void?print（const?int?q[]?int?n）;

int?main（）
{
	srand（time（0））;
	int?N?=?4;
	const?int?REP_NUM?=?10;
	long?start?stop;

	cout<	cout<	while?（N<=32）
	{
		cout<<“N?=?“<		start?=?clock（）;
	//	time（&start）;
		for?（?int?i=0;?i		{
			constructiveMethod（N）;
		}
		//time（&stop）;
		stop?=?clock（）;
		cout<			<<（double）（stop-start）/REP_NUM<<“MS“;

		start?=?clock（）;
	//	time（&start）;
		for?（?int?i=0;?i		{
			repairApproach（N）;
		}
		//time（&stop）;
		stop?=?clock（）;
		cout<			<<（double）（stop-start）/REP_NUM<<“MS“;
		N++;
		cout<	}
	return?0;
}

//constructive?method?to?solve?n?queens?puzzle
bool?g_found;
void?constructiveMethod（?int?n?）
{
	g_found?=?false;
	int*?q?=?new?int[n];
	constructNext（qn0）;
	delete?[]q;
}


//construct?ith?queen‘s?position
void?constructNext（?int?q[]?int?n?int?i?）
{
	if?（?g_found?）
		return;
	if?（?i?==?n?）
	{
//		print（qn）;
		g_found?=?true;
		return;
	}
	for?（?int?j=0;?j	{
		q[i]?=?j;
		if?（?!conflicting（qni）?）
		{
			constructNext（qni+1）;
		}
	}
}

//test?if?q[i]?conflicts?with?q[0..i-1]
bool?conflicting（?const?int?q[]int?n?int?i?）
{
	for?（?int?k=0;?k	{
		if?（?q[k]==q[i]?）
			return?true;
		if?（?q[k]-q[i]?==?k-i?）
			return?true;
		if?（?q[k]-q[i]?==?i-k?）
			return?true;
	}
	return?false;
}


void?repairApproach（?int?n?）
{
	int*?q?=?new?int[n];
	int?maxConf?=?n;
	while?（?maxConf!=0?）
	{
		for?（?int?i=0;?i		{
			q[i]?=?rand（）%n;
		}
		bool?repaired?=?true;
		while?（?repaired?）
		{
			repaired?=?repair（qnmaxConf）;
		}
	}
//	print（qn）;
	delete?[]q;
}

bool?repair（?int?q[]?int?n?int&?maxConf?）
{	
	maxConf?=?-1;
	bool?repaired?=?false;
	for?（?int?i=0;?i	{
		int?orgVal?=?q[i];
		int?minVal?=?q[i];
		int?minConf?=?n;
		for?（?int?j=0;?j		{
			q[i]?=?j;
			int?confNum?=?getConfNum（qni）;
			if?（?confNum?			{
				minConf?=?confNum;
				minVal?=?j;
			}
		}
		q[i]?=?minVal;
		if?（?orgVal?!=?minVal?）
		{
			repaired?=?true;
		}
		if?（?minConf?>?maxConf?）
			maxConf?=?minConf;
	}
	return?repaired;
}

//get?number?of?columns?that?conflct?with?column?i
int?getConfNum（?const?int?q[]?int?n?int?i?）
{
	int?num?=?0;
	for?（?int?j=0;?j	{
		if?（?j==i?）
			continue;
		if?（?q[j]==q[i]?）
			num++;
		else?if?（?q[j]-q[i]?==?j-i?）
			num++;
		else?if?（?q[j]-q[i]?==?i-j?）
			num++;
	}
	re

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2009-03-06?18:53??nQueens\
?????文件????????3131??2008-05-15?19:58??nQueens\nQueens.cpp
?????文件?????1626435??2009-03-06?18:19??nQueens\N皇后問題.pdf