经典问题,教科书式解题过程,可是在判断布局的合法性上徘徊了很久,逻辑一如既往的混乱,希望这只是由于太累的缘故,其实也只是为了练练手,感觉回溯那部分的代码十分好写,主要还是逻辑上的问题比较费劲。
public class EightQueen {
private int[][] chess;
private int[] used;//列数已用标记,在构造函数中初始化为-1
private int length;
public static void main(String[] args) {
EightQueen eq = new EightQueen(4);
eq.trial(0);
}
public EightQueen(int n) {
this.chess = new int[n][n];
this.used = new int[n];
for (int i = 0; i < n; i++)
used[i] = -1;
this.length = n;
}
public void trial(int i) {
//输出当前布局
if (i == length) {
System.out.println("——————————————");
for (int r = 0; r < length; r++) {
System.out.print("|");
for (int c = 0; c < length; c++) {
if(chess[r][c]==1)
System.out.print(" X ");
else
System.out.print(" O ");
}
System.out.println("|");
}
System.out.println("——————————————");
} else
for (int j = 0; j < length; j++) {
chess[i][j] = 1;//在第i行第j列放置皇后
if (condition(i, j)) {//布局合法则把此列标记为此行的行数
used[j] = i;
trial(i + 1);//向下递归
}
//回溯
if (used[j] == i)
used[j] = -1;//当回溯到i行时,撤销对此行的列标记
chess[i][j] = 0;//移走皇后
}
}
public boolean condition(int i, int j) {
boolean var = true;
if (i > 0) {
if (used[j] != -1) {
var = false;//一列只能有一个皇后
}
else {
if (j != 0 && j != length - 1) {
if (chess[i - 1][j - 1] == 1 || chess[i - 1][j + 1] == 1)
var = false;//非边界的皇后的左上对角或右上对角不能有皇后
}
//边界上的皇后合法性判定
if (j == 0) {
if (chess[i - 1][j + 1] == 1)
var = false;
}
if (j == length - 1) {
if (chess[i - 1][j - 1] == 1)
var = false;
}
}
}
return var;
}
}
分享到:
相关推荐
八皇后问题是一种回溯思想的体现,可以用C语言里面的递归算法实现
八皇后问题的两种解法,包含c方式和c++方式
用回溯求解法求解八皇后问题,经典问题matlab实现,欢迎大家下载
八皇后问题 c源代码 回溯法 通过更改N的值可以演变成为N皇后 不过当N大于一定的数值时 电脑会花费比较长的时间哦
八皇后问题的C语言程序解法,利用了回溯的思想
使用C#编写回溯法解决8皇后问题的实验报告和程序 有图形界面,可以查看任意一种解法
八皇后问题,回溯算法,92种解法均有,且结果真观易懂
代码打包 博文链接:https://eastsun.iteye.com/blog/194608
没有用栈,用的方法很直观,代码有70行
java--八皇后问题的势力范围解法: 用的是eclipse运行的,特色在于运用势力范围,每当放置一个皇后就会将其下面影响到的空格的势力值加1,每次回溯的时候减1,用一个2维数组保存,相当直观。
这是一个Qt八皇后的demo演示样例,由于用界面呈现,所以比较容易看出算法得到的结果是否正确,详细关于解法的分析可以参看http://blog.csdn.net/satanzw/article/details/8106409
利用回溯的递归方式解决八皇后问题,给出所有的解法;代码有详细注释,我花了一个晚上弄明白的,尽量写得让大家都能看懂:-)
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
详细描述的八皇后问题的四种风格的解法,绝对可用
本文实例讲述了python基于右递归解决八皇后问题的方法。分享给大家供大家参考。具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法...
用回溯法解决数独,参考八皇后的解法,即先将9个1分别插入到9行中,如果某行有1则跳过这一行;再将9个2分别插入到9行中,如果某行有2则跳过这一行...依次类推。
八皇后问题要求在一个8*8的棋盘上放上8个皇后,使得每一个皇后既攻击不到另外七个皇后,也不被另外七个皇后所攻击.按照国际象棋的规则,一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子....
八皇后问题描述:在一个8:multiplication_sign:8的棋盘上,任意摆放8个棋子,要求任意两个棋子不能在同一行,同一列,同一斜线上,问有多少种解法。 规则分析: 任意两个棋子不能在同一行比较好办,设置一个队列,...