1.引子
中国有一句古话,叫做“不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走。然后再继续尝试向前。通过这样的波浪式前进方法,最终达到目的地。当然整个过程需要很多往返,这样的前进方式,效率比较低下。
2.适用范围
适用于那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题。
3.应用场景
在8*8国际象棋棋盘上,要求在每一行放置一个皇后,且能做到在竖方向,斜方向都没有冲突。国际象棋的棋盘如下图所示:
4.分析
基本思路如上面分析一致,我们采用逐步试探的方式,先从一个方向往前走,能进则进,不能进则退,尝试另外的路径。首先我们来分析一下国际象棋的规则,这些规则能够限制我们的前进,也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉
1)x=row(在纵向不能有两个皇后)
2) y=col(横向)
3)col + row = y+x;(斜向正方向)
4) col - row = y-x;(斜向反方向)
遇到上述问题之一的时候,说明我们已经遇到了障碍,不能继续向前了。我们需要退回来,尝试其他路径。
我们将棋盘看作是一个8*8的数组,这样可以使用一种蛮干的思路去解决这个问题,这样我们就是在8*8=64个格子中取出8个的组合,C(64,80) = 4426165368,显然这个数非常大,在蛮干的基础上我们可以增加回溯,从第0列开始,我们逐列进行,从第0行到第7行找到一个不受任何已经现有皇后攻击的位置,而第五列,我们会发现找不到皇后的安全位置了,前面四列的摆放如下:
第五列的时候,摆放任何行都会上图所示已经存在的皇后的攻击,这时候我们认为我们撞了南墙了,是回头的时候了,我们后退一列,将原来摆放在第四列的皇后(3,4)拿走,从(3,4)这个位置开始,我们再第四列中寻找下一个安全位置为(7,4),再继续到第五列,发现第五列仍然没有安全位置,回溯到第四列,此时第四列也是一个死胡同了,我们再回溯到第三列,这样前进几步,回退一步,最终直到在第8列上找到一个安全位置(成功)或者第一列已经是死胡同,但是第8列仍然没有找到安全位置为止
总结一下,用回溯的方法解决8皇后问题的步骤为:
1)从第一列开始,为皇后找到安全位置,然后跳到下一列
2)如果在第n列出现死胡同,如果该列为第一列,棋局失败,否则后退到上一列,在进行回溯
3)如果在第8列上找到了安全位置,则棋局成功。
8个皇后都找到了安全位置代表棋局的成功,用一个长度为8的整数数组queenList代表成功摆放的8个皇后,数组索引代表棋盘的col向量,而数组的值为棋盘的row向
量,所以(row,col)的皇后可以表示为(queenList[col],col),如上图中的几个皇后可表示为:
queenList[0] = 0; queenList[1] = 3; queenList[2] = 1; queenList[3] = 4; queenList = 2;
我们看一下如何设计程序:
首先判断(row,col)是否是安全位置的算法:
boolIsSafe(intcol,introw,int[]queenList)
{
//只检查前面的列
for(inttempCol=0;tempCol<col;tempCol++)
{
inttempRow=queenList[tempCol];
if(tempRow==row)
{
//同一行
returnfalse;
}
if(tempCol==col)
{
//同一列
returnfalse;
}
if(tempRow-tempCol==row-col||tempRow+tempCol==row+col)
{
returnfalse;
}
}
returntrue;
}
设定一个函数,用于查找col列后的皇后摆放方法:
///<summary>
///在第col列寻找安全的row值
///</summary>
///<paramname="queenList"></param>
///<paramname="col"></param>
///<returns></returns>publicboolPlaceQueue(int[]queenList,intcol)
{
introw=0;
boolfoundSafePos=false;
if(col==8)//结束标志
{
//当处理完第8列的完成
foundSafePos=true;
}
else
{
while(row<8&&!foundSafePos)
{
if(IsSafe(col,row,queenList))
{
//找到安全位置
queenList[col]=row;
//找下一列的安全位置
foundSafePos=PlaceQueue(queenList,col+1);
if(!foundSafePos)
{
row++;
}
}
else
{
row++;
}
}
}
returnfoundSafePos;
}
调用方法:
staticvoidMain(string[]args)
{
EightQueeneq=newEightQueen();
int[]queenList=newint[8];
for(intj=0;j<8;j++)
{
Console.WriteLine("-----------------"+j+"---------------------");
queenList[0]=j;
boolres=eq.PlaceQueue(queenList,1);
if(res)
{
Console.Write("");
for(inti=0;i<8;i++)
{
Console.Write(""+i.ToString()+"");
}
Console.WriteLine("");
for(inti=0;i<8;i++)
{
Console.Write(""+i.ToString()+"");
for(inta=0;a<8;a++)
{
if(i==queenList[a])
{
Console.Write("q");
}
else
{
Console.Write("*");
}
}
Console.WriteLine("");
}
Console.WriteLine("---------------------------------------");
}
else
{
Console.WriteLine("不能完成棋局,棋局失败!");
}
}
Console.Read();
}
递归算法PlaceQueue,完成这样的功能:它寻找第col列后的皇后的安全摆放位置,如果该函数返回了false,表示当前进入了死胡同,需要进行回溯,直到为0-7列都找
到了安全位置或者找遍这些列都找不到安全位置的时候终止。
用递归算法解决8皇后问题的示例程序:
/Files/jillzhang/EightQueens.rar
欢迎大家下载;
-----------------------------------------------------------------------------------------------------------------
递归算法到这篇为止,已经学习到了分而治之,动态编程,回溯等重要思想,也用这些问题解决了一些具体问题,比如排序,背包,8皇后问题等,通过对理论的学习
和对实际问题的解决,充分理解递归算法的使用方法。
相关推荐
八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++
八皇后问题课程设计论文
解决八皇后问题的源码,带有注释,由于数据结构即算法的学习,如有其他需要,请留言
作业代码,汇编写八皇后问题,自己写了一份,在网上找的也在里面
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
解决八皇后问题。利用mfc加了界面,输出结果放在一个文档中。
linux c语言实现八皇后问题。希望对你的学习
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一...
C++面向对象编程八皇后问题 BOOL CMyqueenApp::InitInstance() { AfxEnableControlContainer(); // Standard initialization // If you are not using these features and wish to reduce the size // of your ...
这个文档关于八皇后问题,一共两种代码,输出分别为0和1的矩阵或者直接输出位置序号两种输出结果。代码是C++语言编写。
八皇后问题 递归算法 可以输入皇后的值 输出排列的结果
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
经典的算法,八皇后问题,c++实现,回溯法
这是通过遗传算法求解八皇后问题的例子(比较经典) 步骤: 1,先是随机生成一定种群数量的染色体; 2,从种群中选择较为优秀的染色体个体; 3,按顺序让两个父染色体生成两个子染色体,理论上,子染色体会随着...
八皇后问题详细的解法-23页 PPT PDF版.pdf
包含prolog求解修八皇后问题的实验报告、源代码及试验运行截图
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
个人写的一个八皇后问题,有需要的,可以下载。用C++编写的!
八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构八皇后问题 数据结构
C语言八皇后问题