1.问题描述
在8*8国际象棋棋盘上,要求在每一行放置一个皇后,且能做到在竖方向,斜方向都没有冲突。国际象棋的棋盘如下图所示:
2.分析
采用逐步试探的方式,先从一个方向往前走,能进则进,不能进则退,尝试另外的路径。首先我们来分析一下国际象棋的规则,这些规则能够限制我们的前进,也就是我们前进途中的障碍物。一个皇后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] = 2; queenList[2] = 4; queenList[3] = 1; queenList[4] = 3;
我们看一下如何设计程序:
首先判断(row,col)是否是安全位置的算法:
bool IsSafe(int col,int row,int[] queenList)
{
//只检查前面的列
for (int tempCol = 0; tempCol < col; tempCol++)
{
int tempRow = queenList[tempCol];
if (tempRow == row)
{
//同一行
return false;
}
if (tempCol == col)
{
//同一列
return false;
}
if (tempRow - tempCol == row - col || tempRow + tempCol == row + col)
{
return false;
}
}
return true;
}
设定一个函数,用于查找col列后的皇后摆放方法:
/// <summary>
/// 在第col列寻找安全的row值
/// </summary>
/// <param name="queenList"></param>
/// <param name="col"></param>
/// <returns></returns>
public bool PlaceQueue(int[] queenList, int col)
{
int row = 0;
bool foundSafePos = 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++;
}
}
}
return foundSafePos;
}
调用方法:
static void Main(string[] args)
{
EightQueen eq = new EightQueen();
int[] queenList = new int[8];
for (int j = 0; j < 8; j++)
{
Console.WriteLine("-----------------"+j+"---------------------");
queenList[0] = j;
bool res = eq.PlaceQueue(queenList, 1);
if (res)
{
Console.Write(" ");
for (int i = 0; i < 8; i++)
{
Console.Write(" " + i.ToString() + " ");
}
Console.WriteLine("");
for (int i = 0; i < 8; i++)
{
Console.Write(" "+i.ToString()+" ");
for (int a = 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列都找
到了安全位置或者找遍这些列都找不到安全位置的时候终止.
分享到:
相关推荐
用非递归解决八皇后的问题,是经典的非递归算法,学习数据结构中很有用
自己写的八皇后递归算法演示程序,c#编写,图形展示,可以学习一下递归算法 结果打印举例如下: 2:1 6 8 3 7 4 2 5 +---+---+---+---+---+---+---+---+ | | | O | | | | | | +---+---+---+---+---+---+---+---+ | ...
八皇后问题的递归求解 C经典算法之一。值得学习。。。
八皇后问题(英文:Eight queens),是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。 该问题是在8×8格的国际象棋棋盘上摆放8个皇后,要求没有一个皇后能够吃掉任何其他一个,也就是使其...
主要给大家介绍了关于利用Python实现八皇后问题的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
八皇后问题:八皇后问题,是一个...最近在学习回溯递归的算法,所以试着用Python实现八皇后的求解问题,刚开始总是走不通,后来发现是走到死节点后,回溯需要将前一步的操作还原,这是我学习过程中一直不太好理解的一
3.八皇后问题 第三章——分治算法 1.归并排序 2.快速排序 3.折半查找 4.选择问题 5.最大子段 第四章——贪心算法 1.背包问题 2.多机调度问题 3.单源最短路径-Dijkstra算法 4.最小代价生成树问题-Prim算法 5.最小代价...
10 .3 拉斯维加斯( Las Vegas)型概率算法 10 .3 .1 八皇后问题 10 .3 .2 整数因子分解问题 10 .4 蒙特卡罗(Monte Ca rlo)型概率算法 10 .4 .1 主元素问题 10 .4 .2 素数测试问题 10 .5 实验项目— — —随机数发生器...
10.9.1 八皇后问题算法 324 10.9.2 八皇后问题求解 325 10.10 寻找假银币 327 10.10.1 寻找假银币算法 327 10.10.2 寻找假银币求解 329 10.11 青蛙过河 331 10.11.1 青蛙过河算法 331 10.11.2 青蛙过河求解 ...
八皇后问题(回溯) 数据结构包 main方法进行测试,部分代码加了注释,后续学习和代码完善 部分代码可能有复习io的知识 leetcode 包 一般已完成网站的题目为主,后续补充完善题目的链接 一些题目解题思路的学习笔记...
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过...9.5 八皇后问题求解 9.6 简易文件加密/解密系统 第10章 算法设计与数据结构面试题精粹 10.1 常见的算法设计题 10.2 常见的数据结构题
recursion里面是递归的案例,迷宫回溯、一些递归测试、八皇后问题 dac 分治算法里面是汉诺塔问题 dynamic dynamic背包问题 search search 二分查找 hashtab hashtab 哈希表实现 tree tree二叉树的前序后序中序遍历及...
在我国学习计算机的人中很少有不知道谭浩强教授的。他善于用容易理解的方法和语言说明复杂的概念。许多人认为他开创了计算机书籍贴近大众的新风,为我国的计算机普及事业做出了重要的贡献。 谭浩强教授曾获全国高校...
在我国学习计算机的人中很少有不知道谭浩强教授的。他善于用容易理解的方法和语言说明复杂的概念。许多人认为他开创了计算机书籍贴近大众的新风,为我国的计算机普及事业做出了重要的贡献。 谭浩强教授曾获全国高校...
杂记专案该资源库包含我在2014-2018年间在清华大学的各种项目,包括:ASM ASM :八皇后问题的解决方案 。C ++ C ++ :Quine-McCluskey算法的实现 。 C ++ :关于操作系统(Windows)的三个项目 。 C ++ :关于数据...
30.2 一个关于生成递归的问题 300 第31章 设计带累积器的函数 304 31.1 认识累积器的必要性 304 31.2 带累积器的函数 305 31.3 把函数转换成带累积器的变体 306 第32章 使用累积器的更多例子 315 32.1 补充练习:...