package algorithm ;
public class Empress {
private int n ; //皇后个数
private int[] x ; //当前解
private long sum ; //当前已找到的可行方案数
private static int h ; //记录遍历方案序数
public Empress(){
this.sum = 0 ; //初始化方案数为1,当回溯到最佳方案的时候,就自增1
this.n = 8 ; //求n皇后问题,由自己定义
this.x = new int[n+1]; //x[i]表示皇后i放在棋盘的第i行的第x[i]列
h = 1 ; //这个是我额外定义的变量,用于遍历方案的个数,请看backTrace()中h变量的作用,这里将它定义为static静态变量
}
public boolean place (int k){
for (int j = 1 ; j < k ; j++){
//这个主要是刷选符合皇后条件的解,因为皇后可以攻击与之同一行同一列的或同一斜线上的棋子
if ( (Math.abs(k - j)) == (Math.abs(x[j]-x[k])) || (x[j] == x[k]) ){
return false ; //如果是与之同一行同一列的或同一斜线上的棋子,返回false;
}
}
return true ;//如果不是与之同一行同一列的或同一斜线上的棋子,返回true;
}
public void backTrace (int t){
if (t > n){ //当t>n时,算法搜索到叶节点,得到一个新的n皇后互不攻击放置方案,方案数加1
sum ++ ; //方案数自增1
System.out.println ("方案" + (h++) + "");
print(x);
System.out.print ("\n----------------\n");//华丽的分割线
}else { //当t<=n时,当前扩展的结点Z是解空间中的内部结点,该节点有x[i]=1,2,…,n共n个子结点,
//对于当前扩展结点Z的每一个儿子结点,由place()方法检测其可行性,
//并以深度优先的方式递归地对可行子树搜索,或剪去不可行子数
for (int i = 1 ; i <= n ; i++){
x[t] = i ;
if (place (t)){ //检查结点是否符合条件
backTrace (t+1); //递归调用
}
}
}
}
public void print (int[] a){ //打印数组,没啥的
for (int i = 1 ; i < a.length ; i++){
System.out.print ("皇后" + i + "在" + i + "行" +a[i] + "列、");
}
}
public static void main (String[] args){
Empress em = new Empress();
em.backTrace(1); //从1开始回溯
System.out.println ("\n详细方案如上所示,"+"可行个数为:" + em.sum);
}
}/*output:八皇后问题只有92种方案,这里只给出其中的三个方案
方案1
皇后1在1行1列、皇后2在2行5列、皇后3在3行8列、皇后4在4行6列、皇后5在5行3列、皇后6在6行7列、皇后7在7行2列、皇后8在8行4列、
----------------
方案2
皇后1在1行1列、皇后2在2行6列、皇后3在3行8列、皇后4在4行3列、皇后5在5行7列、皇后6在6行4列、皇后7在7行2列、皇后8在8行5列、
----------------
.
.
.
方案92
皇后1在1行8列、皇后2在2行4列、皇后3在3行1列、皇后4在4行3列、皇后5在5行6列、皇后6在6行2列、皇后7在7行7列、皇后8在8行5列、
----------------
*///~
分享到:
相关推荐
八皇后问题的MonteCarlo算法与回溯法的混合实现,代码精确实现,实验报告或者说论文有详细的阐述!
Java实现八皇后问题,两重循环,检查左右斜对角线,有压栈,回溯
8皇后问题算法实现,基于Java的8皇后问题
用Java代码实现的八皇后问题,在回溯算法中使用了递归。
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一...
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。有多种方法可以解决此问题,这次利用java语言和递归以及回溯算法解决,至于其他语言见后续资源
八皇后Java的图形界面实现,采用回溯法,演示可控。
用java写了一个回溯法求解迷宫的程序,还有一个八皇后的问题,因为水平一般,不敢说一定正确,但是希望对你有一些提示。
通过回溯算法实现八皇后所有情况,并显示出所有情况的皇后排列位置
主要介绍了Java基于循环递归回溯实现八皇后问题算法,结合具体实例形式分析了java的遍历、递归、回溯等算法实现八皇后问题的具体步骤与相关操作技巧,需要的朋友可以参考下
皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一...
用Java编写的八皇后问题 八皇后问题 将八皇后扩展为N皇后问题
递归回溯算法解决八皇后问题,并分析回溯思想的相关理解,以及八皇后问题的代码分析,有一定的代码注释。有良好的代码风格。
八皇后问题图形版,动态演示了八皇后问题的求解过程,采用了回溯算法,延时动态执行
利用回溯的递归方式解决八皇后问题,给出所有的解法;代码有详细注释,我花了一个晚上弄明白的,尽量写得让大家都能看懂:-)
利用回溯法求解八皇后问题,从八皇后问题延伸到n皇后问题。利用水平,主对角线,反对角线三个数组简化算法。 使用方法: 输入要求解的n皇后数目,程序自动输出每种具体方案和总的方法数。
解决八皇后问题。从第一行开始,放第一个皇后,放好皇后以后,她所在的行,列和对角线上的每一个位置就是她的...//回溯求八皇后问题的所有解,皇后协调算法 void queenCoordinate(); //输出所有解 void printResult();
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或...
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...