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

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

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

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

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

相关文章

来自专栏FreeBuf

如何自己动手制作一个靠谱的PM2.5检测仪

气象专家和医学专家认为,由细颗粒物造成的灰霾天气对人体健康的危害甚至要比沙尘暴更大。粒径10微米以上的颗粒物,会被挡在人的鼻子外面;粒径在2.5微米至10微米之...

3408
来自专栏Petrichor的专栏

主机常见噪音 的原因 及 降噪方法

622
来自专栏ml

hdu----(1847)Good Luck in CET-4 Everybody!(简单巴什博奕)

Good Luck in CET-4 Everybody! Time Limit: 1000/1000 MS (Java/Others)    Memory L...

2434
来自专栏木东居士的专栏

程序员该如何管理后宫:皇后造小人(工厂模式)

1272
来自专栏AI研习社

问答 | 前向推理的时候 Yolov3 怎么指定 GPU?

883
来自专栏互联网软件技术

逻辑思维推理-你的大脑转速是多少?

一个村子里,有50户人家,每家都养了一条狗.现在,发现村子里面出现了N只疯狗,村里规定,谁要是发现了自己的狗是疯狗,就要将自己的狗枪毙.村子里面的人只能看出别人...

1203
来自专栏量子位

深度学习装机指南:我们为普通青年和土豪准备了两套方案

深度学习,始于装机。 王新民 友情贡献 量子位 出品 | 公众号:QbitAI 研究深度学习该买一台什么样的电脑?我的笔记本能满足需求吗? 量子位请来小伙伴,为...

3356
来自专栏吉浦迅科技

Tegra X1 家用遊戲多元化裝置 NVIDIA SHIELD Android TV

NVIDIA 5 日針對智能家居推出 NVIDIA SHIELD 系列 Android TV 裝置,內建 Tegra X1 處理器提供優質性能,而且採用 And...

2595
来自专栏吉浦迅科技

DAY 1: 学习CUDA C Programming Guide

1763
来自专栏ml

HDU----(2157)How many ways??(快速矩阵幂)

How many ways?? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

34210

扫码关注云+社区