文档章节

回溯法 解决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
03/04
24
0
小朋友学经典算法(14):回溯法和八皇后问题

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

海天一树X
10/09
0
0
N皇后问题的求解过程

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

关山月朦胧
2016/10/30
14
0
迭代回溯 ---8皇后

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

Ink_cherry
2017/05/16
0
0
回溯法/深度优先遍历的简单优化技巧

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

刘地
2012/11/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot源码:启动过程分析(二)

接着上篇继续分析 SpringBoot 的启动过程。 SpringBoot的版本为:2.1.0 release,最新版本。 一.时序图 一样的,我们先把时序图贴上来,方便理解: 二.源码分析 回顾一下,前面我们分析到了下...

Jacktanger
昨天
0
0
Apache防盗链配置,Directory访问控制,FilesMatch进行访问控制

防盗链配置 通过限制referer来实现防盗链的功能 配置前,使用curl -e 指定referer [root@test-a test-webroot]# curl -e "http://www.test.com/1.html" -x127.0.0.1:80 "www.test.com/1.jpg......

野雪球
昨天
2
0
RxJava threading

因为Rx针对异步系统设计,并且Rx也自然支持多线程,所以新的Rx开发人员有时会假设Rx默认是多线程的。在其他任何事情之前,重要的是澄清Rx默认是单线程的。 除非另有说明,否则每次调用onNex...

woshixin
昨天
0
0
Python的安装及文件类型、变量

一、为什么学习python 服务于大数据、人工智能、自动化运维。 简单易学 代码简洁 薪资高 近几年越来越火 二、Python的安装 linux 系统默认安装, CentOS7 默认安装了python2.7 安装ipython y...

枫叶云
昨天
1
0
JeeSite 4.x 树形结构的表设计和用法

有些同仁对于 JeeSite 4 中的树表设计不太了解,本应简单的方法就可实现,却写了很多复杂的语句和代码,所以有了这篇文章。 在 JeeSite 4 中的树表设计我还是相对满意的,这种设计比较容易理...

ThinkGem
昨天
31
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部