【免费】用栈求解n皇后问题n皇后问题（C语言实现）_用栈求解N皇后资源-CSDN文库

需积分: 0 134 浏览量 2023-07-05 18:09:15 上传评论 1 收藏 119KB PDF 举报

资源推荐

资源详情

资源评论

n皇后问题（C语⾔实现）

算法核⼼：

（1）递归：从第⼀⾏开始，不断地递归处理下⼀⾏，直到处理到n+1⾏就停⽌。

（2）回溯：若该⾏的任意位置均不能满⾜条件，则进⾏回退，退到上⼀⾏的下⼀个状态。

算法步骤：

对于每⼀⾏⽽⾔：

1. 先判断该⾏是不是第n⾏，如果是，则说明现在栈数组g[]中保存着⼀个可⾏的解法，进⾏输出。

2. 若不是，则从该⾏的下⼀个状态开始(每⼀⾏的状态为0,1,2…n-1，初始状态为0)，

（1）若该点满⾜，则存储该点的位置，并进⾏下⼀⾏的递归，同时，在每⼀个递归的后⾯要进⾏出栈(因为输出不⽌⼀个解法)；

（2）若不满⾜，则继续取下⼀个状态。

实现代码

//

定义数据结构

typedef struct{

int m;

int n;

}Dian; //m

是⾏，

n

是列

Dian g[20]; //

模拟⼀个栈，栈⽤来存储现在满⾜条件的点

int top=-1,k=1;

//

出栈和⼊栈操作

void Push(Dian a){

top++;

g[top]=a;

}

Dian Pop(){

Dian t;

t=g[top];

top--;

return t;

}

//

输⼊数据

int Input(){

int n;

printf(( 请输⼊n值值 );

scanf(( ,&n);

return n;

}

//

判断该点是否满⾜要求

bool Can(Dian a){

int i;

for(i=0;i<=top;i++)

{

if(a.n==g[i].n) //

同⼀列不满⾜

return false;

if(abs(a.m-g[i].m)==abs(a.n-g[i].n))

return false; //

同⼀条斜线也不满⾜

}

return true;

}

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

内容反馈

哆啦哆啦S梦

粉丝: 138
资源: 517

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip