文档章节

回溯法 解决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


© 著作权归作者所有

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

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

silenceyawen
03/04
24
0
迭代回溯 ---8皇后

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

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

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

关山月朦胧
2016/10/30
14
0
JavaScript之八皇后问题(递归)

  八皇后问题,是一个古老而著名的问题,该问题最早由国际西洋棋棋手马克斯·贝瑟尔(Max Bezzel)于1848年提出。八皇后问题的具体描述为:在8×8的国际象棋上摆放8个皇后,使其不能互相攻击...

jclian91
01/16
0
0
DFS算法

DFS算法 三个经典例子 1 排列数 问题: 生成1~n的排列 思路: 一颗N层的树 每层节点为n^n个 在生成结果数组前把重复的去掉 DFS出口: 遍历到排列结果数组长度 DFS实现: 尝试安排数字给结果数组 ...

hakase
2016/10/27
15
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux 中不适用功能键切换TTY

本简要指南介绍了在类 Unix 操作系统中如何在不使用功能键的情况下切换 TTY。在进一步讨论之前,我们将了解 TTY 是什么。正如在 AskUbuntu 论坛的一个答案[1]中所提到的,TTY这个词来自 Tele...

问题终结者
3分钟前
0
0
OSChina 周三乱弹 —— 我自己总觉得我的灵魂有毒

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @Devoes :分享王菲的单曲《匆匆那年 (Fleet of Time)》 《匆匆那年 (Fleet of Time)》- 王菲 手机党少年们想听歌,请使劲儿戳(这里) 天长地...

小小编辑
9分钟前
3
3
深度学习与图像处理实例:人像背景虚化与背景替换

简单人像背景虚化处理思路如下: 对图像内容分割,提取人像,背景 背景模糊处理 人像与模糊处理后的背景融合 本实例使用DeepLabV3图像分割深度学习模型实现。代码如下: import numpy as np...

IOTService
昨天
0
0
八月新增开源项目:假装自己是图形界面的 Git 命令行工具

每月新增开源项目。顾名思义,每月更新一期。我们会从社区上个月新收录的开源项目中,挑选出有价值的、有用的、优秀的、或者好玩的开源项目来和大家分享。数量不多,但我们力求推荐的都是精品...

编辑部的故事
昨天
7
0
20180918 find命令与Linux文件扩展名

命令find 用来查找搜索文件。 搜索文件相关命令: which 从环境变量里的目录中去搜索 whereis(不常用) 从一个固定的库中搜索 locate(需要单独安装 yum install -y mlocate) 查询时会从/var/...

野雪球
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部