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)[......]

继续阅读