C++如何实现八皇后问题的方

网址简介:未填写

更新时间:11个月前

访问次数:127

详细介绍

本文实例展示了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++实现八皇后问题的方法,是数据结构与算法中常见的一个经典算法,希望本文所述实例对大家C++算法设计有所帮助。

请发表您的评论