C++实现八皇后问题的方法

本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法。分享给大家供大家参考之用。具体方法如下:

一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数。皇后的攻击范围为整行,整列,以及其斜对角线。

由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后。八皇后问题是回溯法的典型问题。这里我们用的方法很简单:

从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置。如果发现某行没有安全位置,则返回上一行继续检索安全位置;如果发现在最后一行找到了安全位置则输出整个棋盘。

原理很简单,整个程序中表现了这个思想的函数是void Solve()

下面是实现的代码:

 //八皇后问题的实现
#include <iostream>
#include <string>
using namespace std;
//QueenChess类声明
class QueenChess
{
   public:
       QueenChess();     //构造函数
       void Solve();     //求解八皇后问题,并给出放置成功的棋盘总个数
   private:
       string chessState[8];     //用于存放棋盘状态
       int solves;          //八个皇后放置成功的棋盘解的总个数
       bool SafeJudge(int row,int col) const;  //判断位置(row,col)是否安全
       void PlaceQueen(int row);         //在第row行放置一个皇后
       void DrawChess() const;          //打印八个皇后放置成功的棋盘
};

//构造函数,将棋盘初始化
QueenChess::QueenChess()
{
   solves=0;
   int i=0,j=0;
   for(;i<8;++i)
   chessState[i]="--------";
}

//求解八皇后问题,并给出放置成功的棋盘总个数
void QueenChess::Solve()
{
   //从第0行开始放置皇后
   PlaceQueen(0);
   cout<<"/n八皇后问题总共的解的个数是:"<<solves<<endl;
}

//在第row行的各列放置皇后
void QueenChess::PlaceQueen(int row)
{
   //穷尽第row行的所有列
   for(int col=0;col<8;col++)
   {
       if(SafeJudge(row,col))
       {
           //位置(row,col)安全,则放一皇后
           chessState[row][col]='Q';
           //若还没有放到第八行,则尝试下一行
           if(row<7)
            PlaceQueen(row+1);
           //已经放置了八个皇后,打印出成功的棋盘,并将解数加1
           else
           {
             solves++;
             DrawChess();
           }
       }//end if
       //不安全,将该处的皇后拿走,尝试下一列位置
       chessState[row]="--------";
   }
}

//判断是否(row,col)是安全位置
bool QueenChess::SafeJudge(int row,int col) const
{
   int qRow,qCol;
   //检查前面各行,看与前面的皇后是否发生攻击
   for(qRow=0;qRow<row;qRow++)
   {
      string rowState=chessState[qRow];
      //寻找第qRow行放置皇后的列数
      qCol=rowState.find("Q");
      //如果两个皇后在同一行、同一列或两条对角线上,则说明该位置不安全
      if(qRow==row||qCol==col||(qCol-qRow)==(col-row)||(qCol+qRow)==(col+row))
       return false;
   } //end if
   return true;
}

//打印成功的棋盘
void QueenChess::DrawChess() const
{
   int i,j;
   cout<<"/n八皇后问题的第"<<solves<<" 个解为:"<<endl;
   cout<<" 0 1 2 3 4 5 6 7"<<endl;
   for(i=0;i<8;++i)
   {
      cout<<i<<" ";
      for(j=0;j<8;++j)
      cout<<chessState[i][j]<<" ";
      cout<<endl;
   } //end for
   //每打印一个成功的八皇后棋盘,暂停一下
   //system("pause");
}

//main函数进行测试
int main()
{
  QueenChess chess;
  chess.Solve();
  system("pause");
  return 0;
}

希望本文所述实例对大家C++算法设计有所帮助。

(0)

相关推荐

  • C语言使用回溯法解旅行售货员问题与图的m着色问题

    旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线(或总的旅费)最小.数学模型为给定一个无向图,求遍历每一个顶点一次且仅一次的一条回路,最后回到起点的最小花费. 2.输入要求: 输入的第一行为测试样例的个数T( T < 120 ),接下来有T个测试样例.每个测试样例的第一行是无向图的顶点数n.边数m( n < 12,m < 100 )

  • C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • 采用C++实现区间图着色问题(贪心算法)实例详解

    本文所述算法即假设要用很多个教室对一组活动进行调度.我们希望使用尽可能少的教室来调度所有活动.采用C++的贪心算法,来确定哪一个活动使用哪一间教室. 对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少. 具体实现代码如下: //贪心算法 #include "stdafx.h" #include<iostream> #define N 100 using namespace std; struct Activity { int n

  • 八皇后问题的相关C++代码解答示例

    八皇后问题即指在一个8*8的棋盘上放置8个皇后,不允许任何两个皇后在棋盘的同一行.同一列和同一对角线上.关键字:递归.上溯.通用技巧: 经观察发现,对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7) 其主对角线(即左上至右下)上的每个点的i-j+7的值(范围在(0,14))均相等: 其从对角线(即右上至左下)上的每个点的i+j的值(范围在(0,14))均相等: 且每个主对角线之间的i-j+7的值均不同,每个从对角线之间的i-j+7的值亦不同: 如a[3][4]: 主:3-4+7

  • 基于C++的农夫过河问题算法设计与实现方法

    本文实例讲述了基于C++的农夫过河问题算法设计与实现方法.分享给大家供大家参考,具体如下: 问题描述: 一个农夫带着-只狼.一只羊和-棵白菜,身处河的南岸.他要把这些东西全部运到北岸.他面前只有一条小船,船只能容下他和-件物品,另外只有农夫才能撑船.如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜.请求出农夫将所有的东西运过河的方案. 实现上述求解的搜索过程可以采用两种不同的策略:一种广度优先搜索,另一种

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

    还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那

  • C++三色球问题描述与算法分析

    本文实例讲述了C++三色球问题.分享给大家供大家参考,具体如下: /* * 作 者:刘同宾 * 完成日期:2012 年 11 月 15 日 * 版 本 号:v1.0 * * 输入描述: * 问题描述:三色球问题:若一个口袋中放有12个球,其中有3个红的.3个白的和6个黒的,问从中任取8个共有多少种不同的颜色搭配? * 提示: 设任取的红球个数为i,白球个数为j,则黒球个数为8-i-j,根据题意红球和白球个数的取值范围是0~3, * 在红球和白球个数确定的条件下,黒球个数取值应为8-i-j<=6.

  • C++回溯法实例分析

    本文实例讲述了C++的回溯法,分享给大家供大家参考之用.具体方法分析如下: 一般来说,回溯法是一种枚举状态空间中所有可能状态的系统方法,它是一个一般性的算法框架. 解向量a=(a1, a2, ..., an),其中每个元素ai取自一个有限序列集Si,这样的解向量可以表示一个排列,其中ai是排列中的第i个元素,也可以表示子集S,其中ai为真当且仅当全集中的第i个元素在S中:甚至可以表示游戏的行动序列或者图中的路径. 在回溯法的每一步,我们从一个给定的部分解a={a1, a2, ..., ak}开始

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • C++实现八皇后问题的方法

    本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没

  • C语言基于回溯算法解决八皇后问题的方法

    本文实例讲述了C语言基于回溯算法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 问题描述: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行:若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可

  • JavaScript解八皇后问题的方法总结

    关于八皇后问题的 JavaScript 解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了 背景 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上 八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为 n×n ,而皇后个数也变成n .当且仅当n = 1或n ≥ 4时问题有解 盲目的枚举算法 通过N重循环,枚举满足约束条件的解(

  • Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • python八皇后问题的解决方法

    本文为大家分享了python八皇后问题的解决方法,供大家参考,具体内容如下 题目: 给定一个 N*N 正方形棋盘,在上面放置 N个棋子,又叫皇后,使每两个棋子都不在同一条横线上.竖线上.斜线上.一般我们都讨论8皇后,但是只要N > 4,都会存在解的. 分析: 方法1:根据定义来处理,即每往棋盘中放置皇后的时候,都要判断哪些位置可以放新加入的皇后,而哪些地方如果放置皇后的话,会造成冲突.我下面写的这个代码就是基于此. 方法2.我看了下别人的优化,主要是采用位运算来实现计算复杂度降低的,我没有用Py

  • C语言八皇后问题解决方法示例【暴力法与回溯法】

    本文实例讲述了C语言八皇后问题解决方法.分享给大家供大家参考,具体如下: 1.概述: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上. 2.暴力法求解: #include<cstdio> #include<cmath> const int maxn=11; int count=0; //P为当前排列,hashTable记录整数x是否已经在

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • java实现八皇后问题示例分享

    问题描述:将八个皇后放在棋盘上,任何两个皇后都不能互相攻击(即没有任何两个皇后在同一行.同一列或者同一对角线上)如图所示   在本文中,对于两道题采用了稍微不同的解决方式,但都使用的是一维数组.6.20中,要求求出一种有效布局,我建立了一个 有八个元素的一位数组,通过随意打乱数组的值,通过值与下标的比较,直至得出一个有效布局:6.22中,要求求出所有有效布局,这里我使用了八进制数,遍历了  从001234567-076543210的所有数字,通过将其转化为八进制字符串,每位与其下标相比较,输出满

随机推荐