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

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

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

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

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 条评论
登录 后参与评论

相关文章

来自专栏数据科学与人工智能

【数据挖掘】数据挖掘领域最有影响力的18个算法

ICDM2006-介绍:数据挖掘领域最有影响力的18个算法 ICDM是数据挖掘领域的顶级会议之一,在数据挖掘理论与应用领域具有相当影响力。 Class...

2635
来自专栏机器之心

资源 | 谷歌与MIT联袂巨著:《计算机科学的数学》开放下载

选自CSAIL.Mit 机器之心编译 参与:蒋思源、吴攀 谷歌和麻省理工学院联袂出品的《计算机科学的数学》昨日已经开放下载了,读者可点击文末「阅读原文」下载。...

2817
来自专栏HansBug's Lab

1342: [Baltic2007]Sound静音问题

1342: [Baltic2007]Sound静音问题 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 710 ...

3567
来自专栏杨熹的专栏

Udacity-Machine Learning纳米学位-学习笔记1

课程地址 Category: Machine Learning    Artificial Intelligence    Data Science   ...

3327
来自专栏CreateAMind

视觉机械臂 visual-pushing-grasping

1131
来自专栏ml

HDUOJ--8球胜负

8球胜负 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

3499
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(一)——安装

一、MADlib简介         MADlib是Pivotal公司与伯克利大学合作的一个开源机器学习库,提供了精确的数据并行实现、统计和机器学习方法对结构化...

3177
来自专栏腾讯音视频实验室

现场报道 | SIGGRAPH Asia 2017 (DAY 3):领略前沿Poster papers

今天是SIGGRAPH Asia 2017的第三天,也是Poster papers讲解的最后一天(总共两天,每天中午13:00-14:00)。今年中了poste...

3907
来自专栏腾讯高校合作

【犀牛鸟·视野】SIGGRAPH Asia 2017 (DAY 3):领略前沿poster papers,关注WebXR新技术

今天是SIGGRAPH Asia 2017的第三天,也是Poster papers讲解的最后一天(总共两天,每天中午13:00-14:00)。今年中了poste...

3646
来自专栏小樱的经验随笔

“玲珑杯”ACM比赛 Round #12题解&源码

我能说我比较傻么!就只能做一道签到题,没办法,我就先写下A题的题解&源码吧,把官方给出的题解贴出来! A -- Niro plays Galaxy Note ...

3877

扫码关注云+社区