频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
C++之八皇后问题解析
2018-10-16 10:39:27           
收藏   我要投稿
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

#include

#include

#include

using namespace std;

class Queen

{

public:

int count;

Queen(int num);

~Queen();

void showQueen(int n);

void setQueen(int x,int y);

bool isClash();

bool checkClash(int nRow);

void enumQueenPostion(int &nSloution);

void putQueen(int nRow, int &nSloution);

private:

//每一个数组元素代表一个皇后的位置,queenArr[0] = 4;第一行第五格

int len;

int *queenArr;

};

Queen::Queen(int num)

{

this->len = num;

this->queenArr = (int*)malloc(sizeof(int)*num);

memset(this->queenArr,0,sizeof(int)*num);

}

Queen::~Queen()

{

delete[]queenArr;

}

//打印每一种可能情况

void Queen::showQueen(int n)

{

cout << "***************Queen position,sloution:"<= len || y < 0 || y >= len)

{

return;

}

queenArr[x] = y;

}

//判断冲突

bool Queen::isClash()

{

for (int i = 1; i <= len; ++i)

{

for (int j = 0; j <= i - 1; j++)

{

if (queenArr[i] == queenArr[j]) //说明在同一列相同值,不满足条件

{

return true;

}

if(abs(queenArr[i] - queenArr[j]) == abs(i - j)) //不可成45度角排列

{

return true;

}

}

}

return false;

}

//枚举法解决八皇后问题,枚举所有皇后可能所在的位置,将每一种可能情况列举出来

/*局限:

1.效率太低

2.不能解决n皇后问题

*/

void Queen::enumQueenPostion(int &nSloution)

{

for (queenArr[0] = 0; queenArr[0] < 8; queenArr[0]++)

for (queenArr[1] = 0; queenArr[1] < 8; queenArr[1]++)

for (queenArr[2] = 0; queenArr[2] < 8; queenArr[2]++)

for (queenArr[3] = 0; queenArr[3] < 8; queenArr[3]++)

for (queenArr[4] = 0; queenArr[4] < 8; queenArr[4]++)

for (queenArr[5] = 0; queenArr[5] < 8; queenArr[5]++)

for (queenArr[6] = 0; queenArr[6] < 8; queenArr[6]++)

for (queenArr[7] = 0; queenArr[7] < 8; queenArr[7]++)

{

count++;

if (isClash())

{

continue;

}

else

{

nSloution++;

showQueen(nSloution);

}

}

}

//检测当前当前行的状态

bool Queen::checkClash(int nRow)

{

for (int nColumn = 0; nColumn < nRow; nColumn++)

{

if (queenArr[nColumn] == queenArr[nRow])

{

return true;

}

if (abs(queenArr[nColumn] - queenArr[nRow]) == abs(nColumn - nRow))

{

return true;

}

}

return false;

}

//回溯法

void Queen::putQueen(int nRow,int &nSloution)

{

for (int i = 0; i < len; ++i)

{

queenArr[nRow] = i; //把循环放在当前循环的位置

//检查冲突

if (!checkClash(nRow))

{

if (nRow == len - 1)

{

nSloution++;

showQueen(nSloution);

}

else

{

//下一行位置

putQueen(nRow + 1,nSloution);

}

}

}

}

int main()

{

Queen queen(8);

//queen.setQueen(0,4);

//queen.setQueen(3,3);

//queen.setQueen(6,4);

int sloution = 0;

//queen.enumQueenPostion(sloution);

//queen.showQueen(sloution);

queen.putQueen(0,sloution);

return 0;

}

点击复制链接 与好友分享!回本站首页
上一篇: 编程语言Python的基础背景知识
下一篇:在高并发的核心技术中如何实现幂等性
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站