算法-编程的灵魂--八皇后

对于我们程序员来说,算法是编程的灵魂,算法的好坏与否,也决定了你代码的健壮性。

----至此,祝愿各位五一节快乐,玩的开心!

下面,看看下面的经典算法,经典的算法很多,写多了大家也不会看完看细,所以就发一个大家回味而已。

Algorithm Gossip: 八皇后 说明西洋棋中的皇后可以直线前进,吃掉遇到的所有棋子,如果棋盘上有八个皇后,则这八 个皇后如何相安无事的放置在棋盘上,1970年与1971年, E.W.Dijkstra与N.Wirth曾经用这个问 题来讲解程式设计之技巧。 解法关于棋盘的问题,都可以用递回求解,然而如何减少递回的次数?在八个皇后的问题中,不必要所有的格子都检查过,例如若某列检查过,该该列的其它格子就不用再检查了,这个方 法称为分支修剪。 #include <stdio.h>

#include <stdlib.h>

#define N 8int column[N+1]; // 同栏是否有皇后,1表示有 int rup[2*N+1]; // 右上至左下是否有皇后 int lup[2*N+1]; // 左上至右下是否有皇后 int queen[N+1] = {0};int num; // 解答编号 void backtrack(int); // 递回求解 int main(void)

{ int i;

num = 0;

for(i = 1; i <= N; i++)

column[i] =1;

for(i = 1; i <= 2*N; i++)

rup[i] =lup[i] = 1;

backtrack(1);

return 0;}

void showAnswer()

{

int x, y;

printf("\n解答 %d\n", ++num);

for(y = 1; y <= N; y++)

{

for(x = 1; x<= N; x++)

{

if(queen[y] == x)

{ printf(" Q"); }

else {printf(" .");

}

}

printf("\n"); }

}

void backtrack(int i)

{

int j;

if(i > N)

{

showAnswer();

}

else

{

for(j = 1; j<= N; j++)

{

if(column[j] == 1 && rup[i+j] == 1 && lup[i-j+N] == 1)

{ queen[i] = j; column[j] = rup[i+j] = lup[i-j+N] = 0; backtrack(i+1);

column[j] = rup[i+j] = lup[i-j+N] = 1; }

}

}

}

原文发布于微信公众号 - 数据库SQL(SQLdba)

原文发表时间:2015-04-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏申龙斌的程序人生

从勾股定理,到费马大定理,再到椭圆曲线,一部辉煌壮丽的数学史诗

5015
来自专栏企鹅号快讯

简单有效的多标准中文分词

-欢迎 加入AI技术专家社群>> 本文介绍一种简洁优雅的多标准中文分词方案,可联合多个不同标准的语料库训练单个模型,同时输出多标准的分词结果。通过不同语料库之间...

2097
来自专栏思影科技

Nature:婴儿早期大脑发育与高危自闭症

来自北卡罗莱纳大学教堂山分校的Heather Cody Hazlett等人在nature上发表了关于自闭症的高风险婴儿的大脑发育的letter,这项工作研究了1...

3357
来自专栏新智元

褚达晨:深度学习青衫磊落险峰行,人工智能漫谈之一

【新智元导读】作者褚达晨认为,科技发展让人类借助计算机的能力,在一个超高维弯曲空间中,搜寻自然世界奥秘。而深度学习则是利用最近年发展起来的大算力,让计算机代替人...

2628
来自专栏阮一峰的网络日志

为什么数码相机可以拍出彩色照片?

上个月(11月13日),83岁的柯达公司退休工程师布赖斯·拜尔(Bryce Bayer)去世。 ? 一家国内杂志邀请我写纪念文章,回顾他对数码摄影的巨大贡献。 ...

3275
来自专栏大数据文摘

用神经网络续写《权力的游戏》,这个脑洞有点大(附完整小说下载)

1214
来自专栏AI科技大本营的专栏

AI 技术讲座精选:数学不好,也可以学习人工智能(七)——自然语言处理的奇妙神奇之处

机器都能做到吗? 我现在是任由自动化左右吗? 未来AI会让作家失业吗? 请阅读本文。 编译 | AI100 在本系列的第五部分中发现了卷积神经网络...

2749
来自专栏机器之心

业界 | 通过分析视网膜图像诊断心脑血管疾病:谷歌大脑团队取得医疗深度学习新进展

28812
来自专栏AI科技评论

动态 | 准确率远超人类病理学家!谷歌用深度学习算法检测癌症

AI科技评论按:为了解决诊断时间有限和诊断结果不一致的问题,谷歌研究院正在研究如何让深度学习在数字病理学领域发挥作用,通过创建一个自动检测算法,在病理学家的工作...

2849
来自专栏机器人网

采用MEMS优化移动机器人的导航性能

地面机器人系统通常用于人工介入成本过高、危险过大或者效率过低的任务。在许多情况下,机器人必须能够自主工作,利用导航系统来监视并控制它从一个位置移到另一个位置。管...

2777

扫描关注云+社区