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)是否是安全位置的算法:
//判断位置(row,col)是否是安全的
boolean 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列后的皇后摆放方法:
/**查找col列后的皇后摆放方法:在第col列寻找安全的row值
* @param queenList
* @param col
* @return
* */
public boolean placeQueen(int[] queenList,int col){
int row=0;
boolean foundSafePos=false;
if(col==8){
//处理完第8列的完成
foundSafePos=true;
}else{
while(col<8&&!foundSafePos){
if(isSafe(col,row,queenList)){
//找到安全位置
queenList[col]=row;
//找下一个安全位置
foundSafePos=placeQueen(queenList,col+1);
if(!foundSafePos){
row++;
}
}else{
row++;
}
}
}
return foundSafePos;
}
主函数:
public static void main(String[] args) {
EightQueen eq=new EightQueen();
int[] queenList=new int[8];
for(int j=0;j<8;j++){
System.out.println("----------------"+j+"----------------");
queenList[0]=j;
boolean res=eq.placeQueen(queenList, 1);
if(res){
System.out.print(" ");
for(int i=0;i<8;i++){
System.out.print(" "+i+" ");
}
System.out.println("");
for (int i = 0; i < 8; i++){
System.out.print(+i+"");
for (int a = 0; a < 8; a++){
if (i == queenList[a]){
System.out.print(" q ");
}
else{
System.out.print(" * ");
}
}
System.out.println("");
}
System.out.println("---------------------------------------");
}else{
System.out.println("不能完成棋局,棋局失败!");
}
}
}
分享到:
相关推荐
八皇后问题,作为计算机方面的一个古老问题,有很大的研究吸引力
### 八皇后问题Java实现详解 #### 一、八皇后问题概述 八皇后问题是一个经典的回溯算法案例,它的目标是在一个8×8的棋盘上放置八个皇后,使得任意两个皇后之间都不在同一行、同一列或同一斜线上。这个问题在...
递 归 算 法 举 例——八皇后问题详解,和大家分享~
《遗传算法解八皇后问题详解》 八皇后问题是一个经典的回溯法问题,它要求在8×8的棋盘上放置8个皇后,使得任意两个皇后都不能在同一行、同一列或同一条对角线上。这个问题的解决方案数量为92种,而通过遗传算法...
对经典算法八皇后问题的说明,以及代码示例,代码中有详尽的注释,有助于读者充分理解其递归调用的逻辑!
下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了。 function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var n...
### 八皇后问题详解 #### 一、八皇后问题背景 八皇后问题是一个经典的计算机科学问题,也是数学领域中一个有趣的挑战。这个问题来源于国际象棋的背景:如何在一个8×8的国际象棋棋盘上放置八个皇后,使得没有任何...
《Scheme实现的八皇后问题详解》 八皇后问题是一个经典的计算机科学问题,它涉及到回溯算法、排列组合以及编程设计模式。在这个问题中,我们需要在8×8的棋盘上放置8个皇后,使得任意两个皇后都不能在同一行、同一...
以下是对"数学建模十大算法详解"中可能包含的一些重要算法的详细介绍: 1. **线性规划**:这是最基础的优化算法之一,用于在满足一组线性约束条件下,最大化或最小化一个线性目标函数。例如,资源分配问题、生产...
8. **回溯与分支限界**:解释回溯法的原理,如八皇后问题,以及分支限界法在解决组合优化问题中的应用。 9. **数据结构基础**:涉及数组、链表、栈、队列、堆、树(二叉树、平衡树如AVL和红黑树)、图等常用数据...
《C#实现八皇后问题详解》 八皇后问题是一个经典的回溯算法问题,它源于19世纪由数学家鲁道夫·路德维希·卡尔·莫里斯·莱昂哈德·欧拉提出,旨在在8×8的棋盘上放置8个皇后,使得任意两个皇后都无法在同一行、同...
《八皇后问题详解与实现——以“demo.rar_DEMO_八皇后 _八皇后问题”为例》 八皇后问题,这是一个经典且有趣的编程挑战,源于19世纪由国际象棋大师马克斯·贝瑟尔提出。它的问题核心在于:如何在8×8的棋盘上放置8...
### Python 实现八皇后问题详解 #### 一、八皇后问题背景及定义 八皇后问题是一个经典的计算机科学问题,最早由国际象棋爱好者马克斯·贝瑟尔在1848年提出。该问题是在一个8×8的国际象棋棋盘上放置8个皇后,使得...
#### 二、八皇后问题详解 ##### (一)问题描述 八皇后问题要求在一个8×8的棋盘上放置8个皇后,使得这些皇后彼此之间不会相互攻击,即任意两个皇后都不能处在同一行、同一列或相同的对角线上。 ##### (二)解的...
### 八皇后问题详解 #### 一、问题背景与历史 八皇后问题是一个经典而古老的问题,最早由德国数学家卡尔·弗里德里希·高斯于1850年提出,随后在1854年,这个问题在柏林的一本象棋杂志上引起了广泛的关注。高斯...
### 八皇后问题详解及其MATLAB与C语言实现 #### 一、八皇后问题概述 八皇后问题是一个经典的计算机科学问题,它最早由国际象棋爱好者马克斯·贝瑟尔在1848年提出,并在1850年由弗朗西斯·高特在《德文杂志》上推广...
《八皇后问题与VC++实现详解》 八皇后问题是一个经典的计算机科学问题,源自19世纪的数学家弗里德里希·高斯提出的一个挑战。这个问题的基本目标是在一个8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法...
5. **回溯法**:八皇后问题、N皇后问题、棋盘覆盖等,回溯法是一种试探性的解决问题方法,通过撤销最近的选择来尝试其他可能的路径。 6. **字符串处理**:KMP算法、Rabin-Karp字符串匹配、Manacher's Algorithm等,...
《数据结构中的八皇后问题详解》 数据结构是计算机科学中的基础学科,它研究如何高效地存储和处理数据。在众多的数据结构问题中,八皇后问题是一个经典且富有挑战性的例子,它涉及到回溯算法、排列组合以及二维数组...