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

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

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

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

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

相关文章

来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏Jerry的SAP技术分享

How to update BOL entity property value via ABAP code

Suppose I have one product with ID I042416 which could be found in CRM WebClient...

510
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

1742
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2818
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

761
来自专栏草根专栏

适合在Markdown里面使用的emoji

因为Markdown里面加颜色需要写html style, 所以对于一些标题, 还是用一下emoji吧: RED APPLE (&#x1F34E;): ? GR...

2704
来自专栏JMCui

MongoDB系列五(地理空间索引与查询).

Volvo Today, Volvo announced i...

2712
来自专栏Java学习123

HTTP Status 500 - {msg=SolrCore 'collection1' is not available due to init failure: Could not load c

41011
来自专栏菩提树下的杨过

linq to sql取出随机记录/多表查询/将查询出的结果生成xml

在手写sql的年代,如果想从sqlserver数据库随机取几条数据,可以利用order by NewId()轻松实现,要实现多表查询也可以用select * f...

2176

扫码关注云+社区