回溯算法的N皇后

一个用三种方法解决N皇后问题并且效率很高的c语言程序。 用到了前向检查的回溯法 、基本回溯算法、面向冲突的回跳法等三种方法解决问题。

#include 
#include 
#include 

#ifndef N_QUEEN_H
#define N_QUEEN_H

#include 

#define MAX_VARS 128
#define FAIL -1
#define NONE -1

int num_vars;
int* assignment;
int algorithm_switch;

typedef struct _Var
{
	int index; // 本变量的标号
	int cur_value; // 本变量的赋值
 
	int *domain; // 本变量的值域
	int domain_index; // 指向本变量能够在值域中取出的下一个值
	
	int forwardcheck_depth; // 当此变量被赋值后，向前检查的变量的数目
	
	// 下面的两个数据用于记录当前变量的值域被前面变量的赋值导致的排除情况
	int *domain_filter_count;
	int num_filtered_value;
	
	// 记录本变量的冲突集，若conflic_set[i]为true，则表示本变量与第i号变量存在冲突
	bool *conflict_set;

} Var;

Var** all_vars;  // all the information about every variable

// 初始化每个变量的信息
void InitVarInfo（） {
	int var_index;
	int value_index;

	assert（num_vars > 0）;

	all_vars = （Var**） calloc（num_vars sizeof（Var*））;
	for（var_index = 0; var_index < num_vars; var_index++）
		all_vars[var_index] = （Var*） calloc（1 sizeof（Var））;

	for（var_index = 0; var_index < num_vars; var_index++）
	{
		all_vars[var_index]->index = var_index;
		all_vars[var_index]->cur_value = NONE;

	
		all_vars[var_index]->domain = （int*） calloc（num_vars sizeof（int））;
		for（value_index = 0; value_index < num_vars; value_index++）
		{
			all_vars[var_index]->domain[value_index] = value_index;
		}
		all_vars[var_index]->domain_index = 0;
	
		all_vars[var_index]->forwardcheck_depth = 0;

		all_vars[var_index]->domain_filter_count = （int*） calloc（num_vars sizeof（int））;
		for（value_index = 0; value_index < num_vars; value_index++）
		{
			all_vars[var_index]->domain_filter_count[value_index] = 0;
		}
		all_vars[var_index]->num_filtered_value = 0;

		all_vars[var_index]->conflict_set = （bool*） calloc（num_vars sizeof（bool））;
		for（value_index = 0; value_index < num_vars; value_index++）
		{
			（all_vars[var_index]->conflict_set）[value_index] = false;
		}		
	}
	
	// dump the information of var for debug
	/*
	for（var_index = 0; var_index < num_vars; var_index++）
	{
		printf（“Information of var%d \n“ var_index）;
		printf（“Index: %d\n“ all_vars[var_index]->index）;
		printf（“Current value: %d\n“ all_vars[var_index]->cur_value）;

		// TODO: dump other infomation
	}
	*/
}

// 将标号为var_index的变量的取值位置设置为该变量domain的初始位置
void ResetDomainIndex（int var_index）
{
	all_vars[var_index]->domain_index = 0;

}

// 取出标号为var_index的变量的值域中的一个值，如果该值域中的所有值均被尝试过
// 则返回fail，表示失败
int NextValue（int var_index）
{
	int value;
	int &value_index = all_vars[var_index]->domain_index;

	if（value_index >= num_vars）
		return FAIL;
	
	for（; value_index < num_vars; value_index++）
	{
		if（all_vars[var_index]->domain_filter_count[value_index] == 0）
		{
			value = all_vars[var_index]->domain[value_index];
			break;
		}
	}
	
	if（value_index >= num_vars）
		return FAIL;
	else {
		value_index++;
		return value;
	}
}

// 根据var_index分析出需要回溯到的变量的标号
int BacktrackTo（int var_index）
{
	return var_index - 1;
}

// 判断当前的assignment中对标号为0 ... var_i

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

     文件      12949  2012-01-08 17:48  testqueen\111.cpp

     文件      29440  2012-01-08 17:48  testqueen\Debug\111.obj

     文件       3732  2012-01-08 17:48  testqueen\Debug\BuildLog.htm

     文件         67  2012-01-08 17:48  testqueen\Debug\mt.dep

     文件      36864  2012-01-08 17:48  testqueen\Debug\testqueen.exe

     文件        663  2012-01-01 22:39  testqueen\Debug\testqueen.exe.embed.manifest

     文件        728  2012-01-01 22:39  testqueen\Debug\testqueen.exe.embed.manifest.res

     文件        621  2012-01-08 17:48  testqueen\Debug\testqueen.exe.intermediate.manifest

     文件     408180  2012-01-08 17:48  testqueen\Debug\testqueen.ilk

     文件     429056  2012-01-08 17:48  testqueen\Debug\testqueen.pdb

     文件      52224  2012-01-08 17:48  testqueen\Debug\vc90.idb

     文件      69632  2012-01-08 17:48  testqueen\Debug\vc90.pdb

     文件     592896  2012-01-16 11:41  testqueen\testqueen.ncb

     文件        883  2012-01-01 22:30  testqueen\testqueen.sln

    ..A..H.      8704  2012-01-16 11:41  testqueen\testqueen.suo

     文件       3919  2012-01-01 22:35  testqueen\testqueen.vcproj

     文件       1427  2012-01-16 11:41  testqueen\testqueen.vcproj.SKY-20111108IPY.Administrator.user

     目录          0  2012-01-08 17:48  testqueen\Debug

     目录          0  2012-01-08 17:48  testqueen

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

              1651985                    19