Tag Archives: 八皇后

数据结构重读 – 回溯法与树的遍历 (幂集问题八皇后问题)

有许多问题，可以利用试探和回溯的搜索技术求解。

求解的过程实际是先序遍历一棵“状态树”的过程。

例1：有集合A = {1, 2, ...n}，求A的全部子集。

思路：从求全部子集（幂集）这个事情上，实际上对每个元素只有两个状态：要么在一个子集中，要么不在。

因此，可以逐一对A中每个元素进行“取”和“舍”，从而构造一棵完全二叉树。

算法如下：

注意这里是1~n，不是0~n
void mj(int n, int pos, int* flag)
{
i[......]

八皇后问题的c语言描述

没有做优化，纯回溯，自己写的。
八皇后问题的c语言描述：
#include
#include

int a[9]={0,0,0,0,0,0,0,0,0},count=0;

void f(int n);//核心
void op();//这个是找到满足条件的解的时候输出
int ct(int n);//这个函数判断是否有冲突

int main()
{
f(1);
printf("\n共有%d个解",count);
return 0;
}

void f(int n)[......]