转载请注明出处:http://hi.baidu.com/ipress/
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名
的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即
任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后
来有人用图论的方法解出92种结果。事实上就是有92种解法。
了解了基本的原理后,我们开始分析:
1.我们需要一个数据存放已经放置皇后的位置,用指针表示的一维数据*position,长度为N(N为放置的皇后总数),可能有人会问为什么不用二维数组,用下票i,j准备定位,事实是这样的,因为该问题是每行,每列,每组对角线只可能出现一个皇后,所以用一维数据position+i中的i则能代码第几行,而值*(position+i)则表示该行中的列值,其实质与二维数组无异.
2.判断每行可放置皇后,假设要判断第n行,则从position中从0到n-1每一个已放皇后的位置判断(列,对角线)
具体算法如下:
// 转载请注明出处 http://hi.baidu.com/ipress/
#include <iostream>
#include <math.h>
#include <malloc.h>
using namespace std;
int *position; //放置的位置
int queen; //皇后数目
int count; //第N种可能性
//判断第n行是否放置皇后
bool SignPoint(int n)
{
for (int i=0;i<n;i++)
{
if (*(position+i) == *(position+n)) //该列已经放置过皇后了
return false;
if (abs(*(position+i) - *(position+n)) == n-i) //对角线已经放置过了
return false;
}
return true;
}
//设置皇后
void SetQueen(int n=0)
{
if (queen==n)
{
//该处可以改成自己想要的显示方式
printf("NO.%d: ",++count);
printf("\n");
for (int i=0;i<queen;i++)
{
for (int j=0;j<queen;j++)
{
if (j == position[i])
{
printf("* ");
}
else
{
printf("0 ");
}
}
printf("\n");
}
printf("\n");
return;
}
else
{
for (int i=0;i<queen;i++)
{
position[n] = i;
if(SignPoint(n))//如果该位置放置皇后正确的话,则到下一行
{
SetQueen(n+1);
}
}
}
}
int main(int argc, char argv[])
{
cout<<"请输入皇后的总数:"<<endl;
cin>>queen;
position = (int*)malloc(sizeof(int));
SetQueen();
cout<<"摆放完毕"<<endl;
cin.get();
cin.get();
return 0;
}
相关推荐
八皇后是一个经典问题,本文件用C++实现了八皇后问题
经典的算法,八皇后问题,c++实现,回溯法
C++经典回溯问题八皇后问题源代码visual c++实现
八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++
八皇后问题的C++算法,利用回溯算法输出全部可行解。
八皇后问题 MFC 经典C++回溯问题 用MFC实现了八皇后问题 是C++的经典回溯问题
n皇后问题C++源码。{典型的8皇后问题的扩展)
C++实现八皇后问题 用递归的方法,实现八皇后问题
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
八皇后问题的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++编写的,回溯法求解n皇后问题 运行环境VC6.0
C++实现八皇后问题,键盘输入第一个皇后位置,然后显示所有结果。保证可运行。文件为压缩包,内含VS工程文件和项目源码。
经典的八皇后问题是学习算法及程序设计语言的必经之路,这里提供一种算法
算法:用c++实现了八皇后问题int main(){ for(int l=0;l<N;l++){ queen[l]=-1; } search(0); for(int k=0;k<N;k++){ cout[k]; } }
小弟申请ID不久,资源分用的很快,自己写点程序借此赚分以备使用。初出茅庐,学识尚浅。请各路朋友多多指点,不胜感激。
c++ 算法学习 用回溯法解决经典的N皇后问题。
① 八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是19世纪著名的数学家高斯1850年提出:在8×8格的国际象棋上摆放8个皇后,使其不能相互共计,即任意两个皇后都不能处于同一行、同一列或同一斜线...
八皇后问题的C++算法,可以求解任意N维皇后问题。谢谢下载
本资源使用c++代码实现N-皇后问题并附上研究小论文,实现算法有:回溯法(递归),回溯法(递归)的镜像优化,回溯法(非递归),回溯法(非递归)的镜像优化,位运算算法,位运算算法的镜像优化。N-皇后问题是八皇后问题的...