文档章节

回溯法 解决8皇后问题

大大美女女
 大大美女女
发布于 2013/11/26 15:49
字数 128
阅读 41
收藏 0
#include <stdio.h>
#include <math.h>
#include <iostream>

using namespace std;

const int kMaxSize = 10;

int x[kMaxSize] = {-1};

bool IsLegal(int k) {
  for (int i = 0; i < k; i++) {
    if (x[k]==x[i]||abs(k-i)==abs(x[k]-x[i])) {
      return false;
    }
  }
  return true;
}

int main(int argc, char* argv[]) {
  int k = 0;
  while (k >= 0) {
    x[k] = x[k] + 1;         
    while (x[k] < kMaxSize && !IsLegal(k)) {
      x[k] = x[k] + 1;
    }

    if (x[k] < kMaxSize && k == kMaxSize -1) {
      for (int i = 0; i < kMaxSize; i++) {
        cout << x[i];
      }
      cout << endl;
    } else if (x[k] < kMaxSize && k < kMaxSize) {
      k = k + 1;
    } else {
      x[k] = -1;
      k = k - 1;
    }
  }
}


有趣有爱有价值:http://www.qihu100.com


© 著作权归作者所有

共有 人打赏支持
下一篇: kmp 算法
大大美女女
粉丝 18
博文 60
码字总数 24479
作品 0
昌平
程序员
私信 提问
回溯算法思想与八皇后问题解的个数

八皇后问题: 在88的国际象棋棋盘上,皇后是威力较大的棋子,它可以攻击到与自己同行、同列以及同一斜线上的棋子,如下图,所有橙色格子上的棋子,都可能会被皇后攻击: 而八皇后问题就是在8...

silenceyawen
2018/03/04
24
0
小朋友学经典算法(14):回溯法和八皇后问题

一、回溯法 回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不...

海天一树X
2018/10/09
0
0
迭代回溯 ---8皇后

八皇后问题 就是在8*8格子上放8个皇后 皇后是可以横行竖行斜行行走 他们之间不能存在可以被吃的关系 算法 迭代回溯法 思路是这样 红色框代表put 函数里的if没有通过 就不再有进一步迭代(子树...

Ink_cherry
2017/05/16
0
0
N皇后问题的求解过程

无解 最初接触N皇后问题,对于N皇后问题所牵涉的回溯算法一概不知,大脑处于混沌状态。 穷举法 使用穷举法,先把N皇后在棋盘上的排布的所有情况都列举出来,通过递归程序实现,再定义一个判断...

关山月朦胧
2016/10/30
14
0
回溯法/深度优先遍历的简单优化技巧

深度优先遍历配合回溯,是解决很多问题的好方法,比如八皇后问题。 皇后的排布规则:n个皇后放在n*n的矩阵里,要求一列只有一个,一行只有一个,任一斜线上只有一个(/和)。 通常,我们会把...

刘地
2012/11/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周五乱弹 —— 姑娘馋的口水都留下来了。

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @且无需多言 :分享Fall Out Boy的单曲《Disloyal Order Of Water Buffaloes》 《Disloyal Order Of Water Buffaloes》- Fall Out Boy 手机党...

小小编辑
今天
29
6
vue 对对象的属性进行修改时,不能渲染页面 vue.$set()

我在vue里的方法里给一个对象添加某个属性时,我console.log出来的是已经更改的object ,但是页面始终没有变化 原因如下: **受现代 JavaScript 的限制 (而且 Object.observe 也已经被废弃),...

Js_Mei
今天
2
0
开始看《Java学习笔记》

虽然书买了很久,但一直没看。这其中也写过一些Java程序,但都是基于IDE的帮助和对C#的理解来写的,感觉不踏实。 林信良的书写得蛮好的,能够帮助打好基础,看得出作者是比较用心的。 第1章概...

max佩恩
昨天
12
0
Redux 三大原则

1.单一数据源 在传统的MVC架构中,我们可以根据需要创建无数个Model,而Model之间可以互相监听、触发事件甚至循环或嵌套触发事件,这些在Redux中都是不被允许的。 因为在Redux的思想里,一个...

wenxingjun
昨天
9
0
跟我学Spring Cloud(Finchley版)-12-微服务容错三板斧

至此,我们已实现服务发现、负载均衡,同时,使用Feign也实现了良好的远程调用——我们的代码是可读、可维护的。理论上,我们现在已经能构建一个不错的分布式应用了,但微服务之间是通过网络...

周立_ITMuch
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部