时间:2021-05-20
本文实例展示了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++算法设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
最近看Python看得都不用tab键了,哈哈。今天看了一个经典问题--八皇后问题,说实话,以前学C、C++的时候有这个问题,但是当时不爱学,没搞会,后来算法课上
本文实例讲述了C语言八皇后问题解决方法。分享给大家供大家参考,具体如下:1.概述:八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八
这篇文章主要介绍了如何基于java语言实现八皇后问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下八皇后问题
本文实例讲述了Python基于生成器迭代实现的八皇后问题。分享给大家供大家参考,具体如下:问题:有一个棋盘和8个要放到上面的皇后,唯一的要求是皇后之间不能形成威
关于八皇后问题的JavaScript解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了背景八皇后问题是一个以国际象棋为背景的问题:如何能够在8