CSP最小冲突法解决n皇后问题

人工智能-CSP最小冲突法解决n皇后问题，(中国地质大学，计算机学院~~)

#include“CSPAlgorithms.h“

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



CSP_Queens::CSP_Queens（int numOfQueens）
{
	srand（（unsigned）time（NULL））;

	N = numOfQueens;
	row = new int[N];
	col = new int[N];
	pdiag=new int[2 * N];
	cdiag=new int[2 * N];
	R=new int[N];
}

CSP_Queens::~CSP_Queens（）
{
	if （NULL != row）delete[]row;
	if （NULL != col）delete[]col;
	if （NULL != pdiag）delete[]pdiag;
	if （NULL != cdiag）delete[]cdiag;
	if （NULL != R）delete[]R;
}
int CSP_Queens::swap（int &a int &b）
{
	int t = a; a = b; b = t;
	return 0;
}
//
int CSP_Queens::GetP（int row int col）
{
	return row - col + N - 1;
}

int CSP_Queens::GetC（int row int col）
{
	return row + col;
}
//返回begin begin + 1 ...  end - 1 这end - begin个数中的随机的一个
int CSP_Queens::My_rand（int begin int end）//左闭右开[begin end）
{
	return rand（） % （end - begin） + begin;
}
//原地shuffle算法，算法导论中的randomize in place算法
void CSP_Queens::Randomize（int a[] int begin int end）// 左闭右开
{
	for （int i = begin; i <= end - 2; i++）{
		int x = My_rand（i end）;
		swap（a[i] a[x]）;
	}
}
//初始化皇后的摆放，同时初始化rowcolpdiagcdiag数组
void CSP_Queens::Init（）
{
	for （int i = 0; i < N; i++）{//首先全部安放在主对角线上
		R[i] = i;
	}
	//下面随机抽取调换两行皇后位置
	Randomize（R 0 N）;//初始化N个皇后对应的R数组为0~N-1的一个排列，
	//此时 即没有任意皇后同列，也没有任何皇后同行
	for （int i = 0; i < N; i++）{
		row[i] = 1;//每行恰好一个皇后
		col[i] = 0;
	}
	for （int i = 0; i < 2 * N - 1; i++）{
		pdiag[i] = 0;
		cdiag[i] = 0;
	}
	//初始化当前棋局的皇后所在位置的各个冲突数
	for （int i = 0; i < N; i++）{
		col[R[i]]++;
		pdiag[GetP（i R[i]）]++;
		cdiag[GetC（i R[i]）]++;
	}
}


//用最小冲突算法调整第row行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第row行）
//调整过后check一下看看是否已经没有冲突，如果没有冲突（达到终止状态），返回true
bool CSP_Queens::Adjust_row（int row）
{
	int cur_col = R[row];
	int optimal_col = cur_col;//最佳列号，设置为当前列，然后更新
	int min_conflict = col[optimal_col] + pdiag[GetP（row optimal_col）] - 1
		+ cdiag[GetC（row optimal_col）] - 1;//对角线冲突数为当前对角线皇后数减一
	for （int i = 0; i < N; i++） {//逐个检查第row行的每个位置
		if （i == cur_col） {
			continue;
		}
		int conflict = col[i] + pdiag[GetP（row i）] + cdiag[GetC（row i）];
		if （conflict < min_conflict） {
			min_conflict = conflict;
			optimal_col = i;
		}
	}
	if （optimal_col != cur_col） {//要更新colpdiagcdiag
		col[cur_col]--;
		pdiag[GetP（row cur_col）]--;
		cdiag[GetC（row cur_col）]--;

		col[optimal_col]++;
		pdiag[GetP（row optimal_col）]++;
		cdiag[GetC（row optimal_col）]++;
		R[row] = optimal_col;
		if （col[cur_col] == 1 && col[optimal_col] == 1
			&& pdiag[GetP（row optimal_col）] == 1 && cdiag[GetC（row optimal_col）] == 1） {
			return Qualify（）;//qualify相对更耗时，所以只在满足上面基本条件后才检查
		}
	}
	//当前点就是最佳点，一切都保持不变
	return false;//如果都没变的话，肯定不满足终止条件，否则上一次就应该返回true并终止了
}

//检查冲突
bool CSP_Queens::Qualify（）
{
	for （int i = 0; i < N; i++）{
		if （col[R[i]] != 1 ||
			pdiag[GetP（i R[i]）] != 1 ||
			cdiag[GetC（i R[i]）] != 1） {
			return false;
		}
	}
	return true;
}
void CSP_Queens:

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4026  2015-11-14 18:18  CSPAlgorithms\CSPAlgorithms\CSPAlgorithms.cpp

     文件       1816  2015-11-14 11:56  CSPAlgorithms\CSPAlgorithms\CSPAlgorithms.h

     文件       4215  2015-11-14 11:56  CSPAlgorithms\CSPAlgorithms\CSPAlgorithms.vcxproj

     文件       1187  2015-11-14 11:56  CSPAlgorithms\CSPAlgorithms\CSPAlgorithms.vcxproj.filters

     文件       1671  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.log

     文件     162801  2015-11-14 18:18  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.obj

     文件       1538  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog\cl.command.1.tlog

     文件      25442  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog\CL.read.1.tlog

     文件       2438  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog\CL.write.1.tlog

     文件        204  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog\CSPAlgorithms.lastbuildstate

     文件       2938  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog\link.command.1.tlog

     文件       3046  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog\link.read.1.tlog

     文件        844  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog\link.write.1.tlog

     文件     164483  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\Source.obj

     文件     363520  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\vc120.idb

     文件     348160  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\vc120.pdb

     文件       4940  2015-11-14 18:21  CSPAlgorithms\CSPAlgorithms\Source.cpp

     文件        985  2015-11-14 00:45  CSPAlgorithms\CSPAlgorithms.sln

    ..A..H.     32256  2015-11-14 20:13  CSPAlgorithms\CSPAlgorithms.v12.suo

     文件      72192  2015-11-14 19:34  CSPAlgorithms\Debug\CSPAlgorithms.exe

     文件     570068  2015-11-14 19:34  CSPAlgorithms\Debug\CSPAlgorithms.ilk

     文件     904192  2015-11-14 19:34  CSPAlgorithms\Debug\CSPAlgorithms.pdb

     目录          0  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug\CSPAlgorithms.tlog

     目录          0  2015-11-14 19:34  CSPAlgorithms\CSPAlgorithms\Debug

     目录          0  2015-11-14 18:21  CSPAlgorithms\CSPAlgorithms

     目录          0  2015-11-14 12:06  CSPAlgorithms\Debug

     目录          0  2015-11-14 00:46  CSPAlgorithms

----------- ---------  ---------- -----  ----

              2672962                    27



............此处省略0个文件信息