文档章节

回溯法 解决8皇后问题

大大美女女
 大大美女女
发布于 2013/11/26 15:49
字数 128
阅读 41
收藏 0
点赞 0
评论 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
回溯法/深度优先遍历的简单优化技巧

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

刘地
2012/11/17
0
0
八皇后问题的递归解法(最易理解的版本)

八皇后问题是一个古来而著名的问题,该问题是19世纪著名的数学家高斯同学提出来的。在8*8的国际象棋上摆放八个皇后,使其不能互相的攻击,也就是说,任意的两个皇后不能放在同一行或则是同一...

simpower
07/10
0
0
算法题:背包最大承重为20,算出装满水果后价格最高的组合,水果不能重复。

这是一个面试笔试题,要求在1个钟之内完成,虽然我花了三天想办法解决了,但是我还是不能够在1个钟之内回想起来写出我的算法,因为算法很复杂,我不禁觉得出这题的公司是不是想招天才。 水果...

Awisper
2015/05/21
0
2
python 回溯法 记录

一直不是太理解回溯法,这几天集中学习了一下,记录如下。 回溯法有“通用的解题法”之称。 1.定义: 也叫试探法,它是一种系统地搜索问题的解的方法。 2.基本思想: 从一条路往前走,能进则...

罗兵
2017/05/29
0
0
八皇后和N皇后以及ios实现界面动态寻找解

一、用枚举法实现 思路:枚举所有的可能来,可以看成一个树形结构,到了叶子节点再去判断是不是可行解 二、用回溯法实现 思路:在枚举法的基础上先进行判断是不是可以放的点,再去进行递归 ...

Tonyliu_
2017/11/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

matplotlib 保存图片时的参数

简单绘图 import matplotlib.pyplot as pltplt.plot(range(10)) 保存为csv格式,放大后依然很清晰 plt.savefig('t1.svg') 普通保存放大后会有点模糊文件大小20多k plt.savefig('t5.p...

阿豪boy
6分钟前
0
0
java 8 复合Lambda 表达式

comparator 比较器复合 //排序Comparator.comparing(Apple::getWeight);List<Apple> list = Stream.of(new Apple(1, "a"), new Apple(2, "b"), new Apple(3, "c")) .collect(......

Canaan_
昨天
0
0
nginx负载均衡

一、nginx 负载均衡 拓扑图: 主机信息: 1、负载均衡器1(lb1):192.168.10.205 RHEL7.5 2、负载均衡器2(lb2):192.168.10.206 RHEL7.5 3、web服务器1(web01):192.168.10.207 Centos...

人在艹木中
昨天
0
0
做了一个小网站

做了一个小网站 www.kanxs123.com

叶落花开
昨天
0
0
继社会佩奇之后,又尝试了可爱的蓝胖子,有趣 Python

#哆啦A梦# !/usr/bin/env python3# -*- coding: utf-8 -*-# @Author: dong dong# @Env: python 3.6from turtle import *# 无轨迹跳跃def my_goto(x, y): penup(...

Py爱好
昨天
0
0
shell及python脚本方式登录服务器

一、问题 在工作过程中,经常会遇见需要登录服务器,并且因为安全的原因,需要使用交互的方式登录,而且shell、python在工作中也经常用到,并且可以提供交互的功能。都是利用了expect、spawn...

yangjianzhou
昨天
0
0
upstream sent too big header while reading...

nginx 报错:1736 upstream sent too big header while reading response header from upstream 1. 一般处理 location ~ \.php$ { #增加下面两句 fastcgi_buffer_size 128k; ......

dubox
昨天
0
0
Python解析配置文件模块:ConfigPhaser

import configparser as pa# [SectionA]# a = aa# b = bb# c = cc# [SectionB]# optionint = 1# optionfloat = 1.1# optionstring = string#https://www.cnblogs.com/a......

易野
昨天
0
0
Java基础——面向对象

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 Object的方法: clone() Object 克隆 to Strin...

凯哥学堂
昨天
0
0
rabbitmq学习记录(八)消息发布确认机制

RabbitMQ服务器崩了导致的消息数据丢失,已经持久化的消息数据我们可以通过消息持久化来预防。但是,如果消息从生产者发送到vhosts过程中出现了问题,持久化消息数据的方案就无效了。 Rabbit...

人觉非常君
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部