八皇后问题一直都给人感觉是非常神秘的东西,想当年学人工智能,由于编程技术不足所以一直没动手实现过这个程序。
最近研究算法,编程技术暴增,搞定八个皇后自然是小菜一碟了。O(∩_∩)O~
原出处:靖空间http://blog.csdn.net/kenden23/article/details/14455915
今天用了回溯法实现一下这个程序。
在棋盘上放八皇后规则:
1. 行和列都不能有两个以上皇后
2. 对角线不能有两个以上的皇后
然后根据这些规则在棋盘上摆放皇后,如果能把所有皇后都摆上,那么就是有解,否则,无解。
之所以叫8皇后,是因为以前人们一直都在研究8个皇后的级数,后来8皇后解决之后,到16皇后,32皇后了,还是沿用这个名字了。
数量大了之后,就不是回溯法能搞定的了,要用到模拟退火法等高级的人工智能算法了。以后抽时间一并搞定。
本算法16皇后还是很轻松的,但是到了20个皇后之后就开始很吃力了,运行时间过长,如果是32个皇后的话,直接算不出来,呵呵,大家认为自己电脑牛逼的话可以试一试,不过应该都不可以。能用回溯法算出64皇后的电脑也许要等到量子计算机出现才可以了。
解决问题的关键就是主函数的循环写法,难点如下:
1 用一维数组代表棋盘,列数代表放置皇后的棋盘行,其值代表填在该行第几列
2. 用k表示填写到第几行了,一行一行地填写
3. 每到达新的行,这一行的vi值肯定是QUEENFREE,如果过发生回溯,那么这一行的值也重置为QUEENFREE。回到上一行的时候,这一行的值已经是前面填写的值了,因为通过判断这一行的值是否是QUEENFREE,而判断是否发生了回溯。回溯到上一行时,那么这行就不能填写被之前更小的值了,否则会发生无限循环。
4. 利用判断当前行是否达到了最大列数,判断这一行时候有合适值,如果没有就需要回溯到上一行了,回溯上一行前,记得重置当前行值为QUEENFREE。
5. 最后一行填写完毕,代表解完成了。
下面是完整的C++程序。
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
const static int QUEENFREE = INT_MAX;
bool eightQueens(vector<int> &vi, int n = 8)
{
vi.clear();
vi.resize(n, QUEENFREE);
int k = 0;
while (k>=0)
{ //k代表即将需要填入皇后的行数
int i = 0;
for (; i < n; i++) //i代表在这一行填入皇后的列数
{
if(islegalMove(vi, k, i))
{
//如果vi[k]不等于QUEEFREE那么就是说明,这是从下一层返回来的k值。
//第一次进入该层就应该满足条件就填写了,但是如果是下一层返回来的话,
//就不能填写比前值更小的值了,这也是Backtracking算法的一个特征:
//是按一定循序的值循环探索适合的解。
//这里不用栈,只用k执行了差不都是栈的功能。
if(vi[k] == QUEENFREE || vi[k]<i)
{
vi[k] = i;
//判断已经填到了最后一行了,那么就是成功了。
if (k == n-1) return true;
k++;
break;
}
}
}
if (i == n)
{
//k行填写了所有可能的值都不符合要求,那么就返回上一层,
//这时候需要把k行还原为原始状态,代表返回了上一行,这样方便上面判断
vi[k] = QUEENFREE;
k--;
}
}
//最后Backtracking到了根,那么就是没有解了。
return false;
}
bool islegalMove(vector<int> &vi, int row, int col)
{
//判断列是否符合规定
for (int i = 0; i < vi.size(); i++)
{
if(i != row && vi[i] == col)
return false;
}
//判断对角线是否符合规定,后面的判定公式费点神。
for(int i = 0; i < vi.size(); i++)
{
if(i != row && (vi[i]-i == col-row || vi[i]+i == col+row))
{
return false;
}
}
//不用判断行了,因为默认是一行只填一个queen的。
return true;
}
};
int main()
{
vector<int> queen;
Solution solu;
if(solu.eightQueens(queen,8))
for(auto x: queen)
{
for (int i = 0; i < queen.size(); i++)
{
if (i == x)
{
cout<<x<<"QUEEN"<<"\t";
}
else
{
cout<<"#"<<"\t";
}
}
cout<<endl;
}
else cout<<"No solution!";
cout<<endl;
return 0;
}
结果:
4皇后:
8皇后:
16皇后:
分享到:
相关推荐
供学习的八皇后问题C++源码程序,主要是用递归实现的,供大家学习参考~~~
经典的八皇后问题是学习算法及程序设计语言的必经之路,这里提供一种算法
小弟申请ID不久,资源分用的很快,自己写点程序借此赚分以备使用。初出茅庐,学识尚浅。请各路朋友多多指点,不胜感激。
解决八皇后问题的程序。 (2)程序设计说明 ① 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是19世纪著名的数学家高斯1850年提出:在8×8格的国际象棋上摆放8个皇后,使其不能相互共计,即任意...
c++实验设计--八皇后问题,以程序为主,代码也有,在dos界面下运行。
八皇后问题的C++程序,很齐全的,我运行出来了的,很好的东西,一起分享了
c++递归实现八皇后。程序求出了满足八皇后条件的所有情况,总共是92这情况。
八皇后问题 C++解决程序 供有兴趣的人参考
八皇后问题的C++源程序 #include #define N 8 void main() { void move(int a[][N],int n); int Judge(int a[][N]); //a[N][N]表示棋盘,每个元素表示一个位置,为0表示没有放置皇后,为1表示放置皇后 //...
c++八皇后课程设计,很不错哦!
八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题要求在一个8*8的棋盘上放上8个皇后,使得每一个皇后既攻击不到另外七个皇后,也不被另外七个皇后所攻击.按照国际...
C++实现八皇后问题,键盘输入第一个皇后位置,然后显示所有结果。保证可运行。文件为压缩包,内含VS工程文件和项目源码。
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
八皇后课程设计3种方法,递归法、穷举法、回溯法,完整程序
c++写的《八皇后》程序问题,解决八皇后问题的程序。
按八皇后问题中的布局规则设计并实现一个游戏程序。在Windows操作系统环境下实现,操作界面可以采用图形界面,也可以使用字符界面,使用Visual C++ 或其他面向对象的开发工具为开发平台。 在图形方式下,具体要求是...
经典的c++八皇后问题,适合初学者及对程序经典算法想要了解的网友
8皇后问题 用回溯法求解 C++源程序 本人自己写的,大家指教
适合于初学者,主要是数组和栈的应用。 该程序有个不足之处就是在于只找到了64中情况,还没有找到所有的情况。 qq:360765409 希望与之交流。
用MFC写的一个八皇后演示程序,支持多种情形的八皇后问题:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。