专栏首页程序猿算法-编程的灵魂--八皇后

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

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

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

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

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),作者:Admin

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SQL2012_创建架构,复合主键,主表,从表的创建方法。

    创建架构,复合主键,主表,从表的创建方法。 create schema XIXI--创建架构 create table XIXI.U( id int n...

    赵腰静
  • SQL2012_创建架构,复合主键,主表,从表的创建方法。

    创建架构,复合主键,主表,从表的创建方法。 create schema XIXI--创建架构 create table XIXI.U( id int n...

    赵腰静
  • 【算法】快速排序法(一)(二)(三)

    Algorithm Gossip: 快速排序法(一) 说明快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定) ,虽然 ...

    赵腰静
  • 3555: [Ctsc2014]企鹅QQ

    Description PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供...

    attack
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • LeetCode31|打印从1到最大的n位数

    这道题算是api的使用方式了,数据的计算,其实自己也没有什么好说的了,但是由于文章的字数必需要达到300字,所有有些时候就只好在这里唠会嗑了,因为文章的原创对于...

    码农王同学
  • 【剑指Offer】51. 数组中的逆序对

    在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

    瑞新
  • BZOJ4698: Sdoi2008 Sandy的卡片(后缀数组 二分)

    attack
  • AIM Tech Round 5 B. Unnatural Conditions(思维)

    题目链接:http://codeforces.com/contest/1028/problem/B

    Ch_Zaqdt
  • 1022 D进制的A+B (20 分)

    输入两个非负 10 进制整数 A 和 B (≤230−1),输出 A+B 的 D (1<D≤10)进制数。

    可爱见见

扫码关注云+社区

领取腾讯云代金券