数据结构：n皇后问题

引入N叉树的数据结构，构建​​皇后问题的解空间树。排列长度​​为树的深度，据此判定递归的出口。初始状态将一维数组q置空，以行先序从第0行开始递归求解。遍历​​行每一列​​，若q中已有​​（即第​​列已经放置了皇后），则发生剪枝，继续遍历其他列；若q中没有​​，则​​，递归式进入​​行的遍历，直到数组q中已经赋满​​个列号，则进入递归出口进行判定局面的合理性（即每个行/列/斜线最多仅有1个皇后）。若局面合理，将该合理局面保存在二维数组result中，继续回溯探索其他合理局面；若局面不合理，同样回溯探索其他合理局面。以此类推，直到遍历完解空间中所有情况，result中所保存的就是所有合理局面，result的长度就是​​皇后问题满足条件的所有局面总数。

其中判断局面合理性的方法具体如下：

1. ​(横行)
2. ​​(纵行)

全部代码：

#include
#include
#include

//判断把它放在这是是否是适用的 

int place(int *paraSolution,int paraT){
	int j;
	for(j = 0;j < paraT;j++){
		 if ((abs(paraT - j) == abs(paraSolution[j] - paraSolution[paraT])) || (paraSolution[j] == paraSolution[paraT]))
	return 0;
	}
	return 1;
}

//Backtracking.回溯。 

void backtracking(int* paraSolution,int paraN, int paraT){
	int i;
	if(paraT>paraN){
		for(i = 1;i <= paraN;i++)
		printf("%d",paraSolution[i]);
		printf("rn");
	}
	else
	{
		for(i = 1;i <= paraN;i++){
			paraSolution[paraT] = i;
			if(place(paraSolution,paraT))
			backtracking(paraSolution,paraN,paraT + 1);
		}
	}
}

//Title: n queens.


void nQueen(int paraN){
	int i;
	int*solution = (int*)malloc((paraN + 1) * sizeof(int));
	for(i = 0;i <= paraN;i++)
	solution[i] = 0;
	
	backtracking(solution,paraN,1);
}

//The entrace.输出数据 

int main(){
	printf("输入个数： rn");
	int n;
	scanf("%d",&n);
	nQueen(n);//括号里面写具体有多少个元素 
	return 1;
}

结果：