c语言算法之深度优先搜索（n皇后问题）

N皇后问题的深度优先搜索解法

在编程领域中，N皇后问题是一个经典的问题，旨在解决在N×N的棋盘上放置N个皇后，使得它们互不攻击。皇后可以攻击到同行、同列以及两个对角线方向的任意格子。今天，我将为大家介绍一种基于深度优先搜索（DFS）的解法，并通过一段C语言代码来详细解析。

首先，我们需要定义一个数组lie来记录每一行皇后的列位置。这个数组的大小通常为N，但为了适应更大规模的问题，这里我将其定义为100。

接下来，我们定义一个打印函数print，用于输出当前棋盘上的皇后布局。通过遍历lie数组，我们可以打印出每一行皇后的列位置。

然后，是核心的判断函数jian。这个函数用于判断在(hang, j)位置放置皇后是否合法。它首先遍历已经放置了皇后的所有行，检查当前位置是否与已放置的皇后在同一列或同一对角线上。如果是，则返回0表示不合法；否则，返回1表示合法。这里使用了abs函数来计算行差和列差的绝对值，以便同时检查主对角线和副对角线的冲突。

紧接着，是深度优先搜索的主体函数dfs。它采用递归的方式，尝试在每一行的每一列放置皇后。如果当前行超过了总皇后数，说明已经成功放置了所有皇后，此时调用print函数输出当前布局；否则，继续尝试在当前行的下一列放置皇后。如果当前位置合法（即jian函数返回1），则更新lie数组并递归调用dfs函数处理下一行。

最后，是程序的入口函数main。它首先读取用户输入的皇后数N，然后调用dfs函数从第一行开始尝试放置皇后。

这段代码简洁而高效，通过深度优先搜索的方式，能够找到所有可能的N皇后布局。在实际应用中，我们还可以对代码进行优化，比如使用位运算来提高判断函数的速度，或者使用剪枝技术来减少不必要的搜索。

N皇后问题不仅是一个有趣的编程问题，更是锻炼我们逻辑思维和算法设计能力的好工具。通过解决这个问题，我们可以更深入地理解深度优先搜索等算法的原理和应用。希望这篇文章能够帮助大家更好地理解N皇后问题的解法，并在实际编程中加以应用。

#include<stdio.h>  
#include<math.h>  
  
// 定义一个数组用于记录每一行皇后的列位置  
int lie[100];  
  
// 打印当前棋盘上的皇后布局  
void print(int huanghou) {  
	for(int i=1; i<=huanghou; i++) {  
		printf("%d ", lie[i]); // 打印每一行皇后的列位置  
	}  
	printf("\n"); // 换行  
}  
  
// 判断在(hang, j)位置放置皇后是否合法  
int jian(int hang, int j) {  
	int i = 1;  
	while(i < hang) {  
		if(lie[i] == j || abs(hang - i) == abs(j - lie[i])) {  
			return 0; // 如果发现冲突，则返回0表示不合法  
		}  
		i++;  
	}  
	return 1; // 没有发现冲突，返回1表示合法  
}  
  
// 深度优先搜索的主体函数  
void dfs(int hang, int huanghou) {  
	if(hang > huanghou) {  
		print(huanghou); // 如果所有皇后都放置完毕，打印当前布局  
	} else {  
		for(int j = 1; j <= huanghou; j++) {  
			if(jian(hang, j)) {  
				lie[hang] = j; // 在当前行j列放置皇后  
				dfs(hang + 1, huanghou); // 递归处理下一行  
			}  
		}  
	}  
}  
  
int main() {  
	int n;  
	scanf("%d", &n); // 读取用户输入的皇后数N  
	dfs(1, n); // 从第一行开始尝试放置皇后  
	return 0;  
}