一个用回溯法解决问题的小例子,完整理顺了思路,感觉挺好的,解决思路如下。
N皇后问题:在n x n的棋盘上放置彼此不受攻击的n个皇后,彼此之间满足如下规则:任意两个棋子不同行,不同列,并且不在一条斜线上。
以4 x 4的棋盘为例,按照回溯法逐步回溯的思路如下:
第一步:在第一行放一个棋子,放在第一列。
第二步:在第二行放棋子,由于第二行的棋子既不能与第一行棋子同列也不能同在一条斜线上,所以只能放在第三列或第四列,假设放在第三列。
第三步:按同样的规则判断第三行的棋子的放法,会发现第三行没有位置满足要求,则此路径不通,回退到第二步。
第四步:回退到第二步后,将第二行的棋子放到第四列,再放第三行棋子,此时只能放第二列,再放第四行棋子,发现没有满足条件的位置,则此处只能再回退到上一步,执行其他的选项,如果整行位置都不满足条件,则向上回退。依次类
推,针对所有的可能性,执行判断。
实现算法时,我们用数组x来表示当前解,x[1]……x[4]依次表示1到4行放棋子的列数。用k表示当前执行判断的行,如果当前的行中x[k]即棋子的列数不符合条件,则列数加1,直到找到合适的列号。如果X[K]>4或k=4,则k--,向上回溯,否则k++,向下一行继续查找判断。
具体算法实现过程如下:
public class NQueen {
public static void main(String args[]){
NQueen n=new NQueen();
System.out.println("请输出棋盘宽高为:");
Scanner s=new Scanner(System.in);
int i=s.nextInt();
x=new int[i+1];
n.find();
}
/*
* 测试数组第m行的皇后是否与前面的m-1行的皇后相互处于攻击位置
*/
public boolean place(int m){
for(int i=1;i<m;i++){
if(x[i]==x[m]||Math.abs(i-m)==Math.abs(x[i]-x[m])){
return false;
}
}
return true;
}
/*
* 回溯法找出n皇后问题中的解
*/
public void find(){
int k=1;
while(k>0){
x[k]=x[k]+1;
while(place(k)==false&&x[k]<x.length){
x[k]=x[k]+1;
}
if(x[k]==x.length){
x[k]=0;
k--;
}else{
if(k==x.length-1){
String s="当前第"+count+"个解为";
s1=s;
for(int i=1;i<x.length;i++){
s1=s1+"->"+x[i];
}
System.out.println(s1);
count++;
x[k]=0;
k--;
}else{
k++;
}
}
}
}
private static int[] x;//当前解的数组x
private int count;//解的个数
private String s1;//
测试结果为:
4x4的棋盘解为:
5x5的棋盘解为:
- 大小: 2 KB
- 大小: 2.5 KB
- 大小: 7.3 KB
- 大小: 8.1 KB
- 大小: 4 KB
分享到:
相关推荐
n皇后问题的三种算法,n^n穷举,n!穷举,回溯法,比较它们的效率
N皇后问题求解,分别是递归方法实现和非递归方法实现,后者采用回溯方法,C语言实现的
算法设计作业,用c++编写的,回溯法求解n皇后问题 运行环境VC6.0
使用递归方法解决了n皇后问题,初学递归的朋友可以参考一下!
算法分析的实验,n皇后,c语言,以矩阵形式列出
n*n 格的棋盘上放置彼此不受攻击的N个皇后。有回溯法实现N后问题,
回溯算法——n皇后问题
通用搜索算法及实现 状态空间树的搜索 N皇后问题 排列树的搜索 跳马问题 子集和数问题 水杯问题 。。。。。。。。。。。。
把状态放在一个 4 字节的 int 整型变量中,并且使用位运算——这样,速度会比朴素算法的快很多。 #include using namespace std; // sum用来记录皇后放置成功的不同布局数;upperlim用来标记所有列都已经放置好了...
N皇后问题 采用循环双向链表, 能实现多个长整型进行加法运算 插入排序法 程序设计:哈希表的一个应用 多维数组下标操作符重载一法 汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵...
N皇后问题 采用循环双向链表, 能实现多个长整型进行加法运算 插入排序法 程序设计:哈希表的一个应用 多维数组下标操作符重载一法 汉诺塔的非递归 回朔法一例 几道有趣的算法题 阶梯问题的递归解法 精确迭代法 矩阵...
这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题。 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解...
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列——应用广泛的小技巧。而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位...
N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt 万年历的算法 .txt 乘方函数桃子猴.txt 乘法矩阵.txt 二分查找1.txt 二分查找2.txt 二叉排序树.txt 二叉树.txt ...
☆ N皇后问题 ☆ 采用循环双向链表, 能实现多个长整型进行加法运算 ☆ 插入排序法 ☆ 程序设计:哈希表的一个应用 ☆ 多维数组下标操作符重载一法 ☆ 汉诺塔的非递归 ☆ 何谓数据结构 ☆ 回朔法一例 ☆ 几道有趣的...
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过C语言程序设计的人士继续深造的理想读物,也可作为具有一定经验的程序设计人员巩固和提高编程水平,查阅相关算法实现和数据结构知识的参考...
《C/C++常用算法手册》对每一个知识点都给出了相应的算法及应用示例。虽然这些例子都是以C语言来编写的,但是算法并不局限于C语言。如果读者采用其他编程语言,例如C++、C#、VB、Java等,根据其语法格式进行适当的...
本文实例讲述了Python解决八皇后...这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方法来解决冲突检测问题,即不能令棋子处于能相互吃掉的位置——相邻、左右对角线。 其次,运用回溯的方法,
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...