N皇后问题构造性方法与启发式修补的比较《人工智能》课程实验，C++实现

N皇后问题构造性方法与启发式修补的比较（《人工智能》课程实验，C++实现）

#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 ）
			{
				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