当前位置:  编程技术>c/c++/嵌入式

c++递归实现n皇后问题代码(八皇后问题)

    来源: 互联网  发布时间:2014-10-23

    本文导语:  还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 扩展到N皇后问题是一样的。一看,似乎要用到二维数组...

还是先来看看最基础的8皇后问题:

在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

扩展到N皇后问题是一样的。
一看,似乎要用到二维数组。其实不需要。一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列——应用广泛的小技巧。而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可。

这种思路的实现方式网上大把,包括前面提到的那位同学,所以也就不要纠结有没有改善有没有提高之类的了,权当一次练习即可。

直接上代码好了,觉得递归方法没什么好说的,空间想想能力好一点儿很容易理解。明天有空再写写非递归实现吧。

代码如下:

/*
 * NQueen.cpp
 *
 *  Created on: 2013年12月23日
 *      Author: nerohwang
 */
//形参rowCurrent表示当前所到的行数
#include
#include
#include
#include
using namespace std;
bool Check(int rowCurrent,int *&NQueen);                         //判断函数
void Print(ofstream &os,int n,int *&NQueen);                                  //打印函数
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os);           //N皇后问题处理函数,index一般初值为0


//判断函数,凡是横竖有冲突,或是斜线上有冲突,返回FALSE
bool Check(int rowCurrent,int *&NQueen)
{
    int i = 0;
    while(i < rowCurrent)
    {
        if(NQueen[i] == NQueen[rowCurrent] || (abs(NQueen[i]-NQueen[rowCurrent]) == abs(i-rowCurrent)) )
        {
            return false;
        }
        i++;
    }
    return true;
}

//将所有可能出现的结果输出文本文档
void Print(ofstream &os,int n,int *&NQueen)
{
    os


    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • php递归示例 php递归函数代码
  • php递归使用示例(php递归函数)
  • 使用C语言递归与非递归实现字符串反转函数char *reverse(char *str)的方法
  • 先序遍历二叉树的递归实现与非递归实现深入解析
  • 如何使用递归和非递归方式反转单向链表
  • 使用python实现递归版汉诺塔示例(汉诺塔递归算法) iis7站长之家
  • php+mysql不用递归实现的无限级分类实例(非递归)
  • C# 实现阶乘 (递归,非递归) 实现代码
  • 递归形式与非递归形式的斐波那契数列的用法分析
  • java 汉诺塔Hanoi递归、非递归(仿系统递归)和非递归规律 实现代码
  • 使用python实现递归版汉诺塔示例(汉诺塔递归算法)
  • C 二分查找 递归与非递归的实现代码
  • 归并排序的递归实现与非递归实现代码
  • php递归函数小例子
  • 请问java里可有递归吗?
  • PHP递归函数返回值使用实例
  • php递归创建目录小例子
  • php递归函数使用return问题
  • php递归函数求阶乘
  • 使用递归实现数组求和示例分享




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3