import java.util.HashMap; import java.util.Map; /** * 八皇后问题 * * @author Watson Xu * @since 2016年4月8日 v1.0.0 */ public class Queens { private Integer queens; // 同栏是否有皇后,1表示有 private Integer[] column; // 右上至左下是否有皇后 private Integer[] rup; // 左上至右下是否有皇后 private Integer[] lup; // 解答 private Integer[] queen; // 独立解 及其对称图形 private Map<String, String> results = new HashMap<String, String>(); // 解答编号 private int num; public Queens(int queens) { this.queens = queens; column = new Integer[queens + 1]; rup = new Integer[(2 * queens) + 1]; lup = new Integer[(2 * queens) + 1]; queen = new Integer[queens + 1]; for (int i = 0; i <= queens; i++) { column[i] = queen[i] = 0; } for (int i = 0; i <= (2 * queens); i++) { rup[i] = lup[i] = 0; // 初始定义全部无皇后 } } public void backtrack(int i) { if (i > queens) { showAnswer(); } else { for (int j = 1; j <= queens; j++) { if ((column[j] == 0) && (rup[i + j] == 0) && (lup[i - j + queens] == 0)) { // 若无皇后 queen[i] = j; // 设定为占用 column[j] = rup[i + j] = lup[i - j + queens] = 1; backtrack(i + 1); // 循环调用 column[j] = rup[i + j] = lup[i - j + queens] = 0; } } } } protected void showAnswer() { num++; if(!isIndependence(num)) return; System.out.println("解答" + num + ":"); for (int y = 1; y <= queens; y++) { for (int x = 1; x <= queens; x++) { if (queen[y] == x) { System.out.print(" Q"); } else { System.out.print(" ."); } } System.out.println(" "); } System.out.println(); } protected boolean isIndependence(int number) { // 自身 String newSolution = resultToString(queen); String flag = results.get(newSolution); if (flag != null) { //System.out.println("非独立解答解答, 同解答 " + flag + " 对称。"); return false; } // 左右对称 Integer[] leftRight = new Integer[queen.length]; // 上下对称 Integer[] upDown = new Integer[queen.length]; // 左上右下对称 Integer[] lurd = new Integer[queen.length]; // 右上左下对称 Integer[] ruld = new Integer[queen.length]; // 顺时针第1次旋转 Integer[] cw1 = new Integer[queen.length]; for (int i = 1; i < queen.length; i++) { leftRight[i] = queen[queen.length - i]; upDown[i] = queen.length - queen[i]; lurd[queen.length - queen[i]] = queen.length - i; ruld[queen[i]] = i; cw1[queen[i]] = queen.length - i; } // 顺时针第2次旋转 Integer[] cw2 = new Integer[queen.length]; for (int i = 1; i < queen.length; i++) { cw2[cw1[i]] = queen.length - i; } // 顺时针第3次旋转 Integer[] cw3 = new Integer[queen.length]; for (int i = 1; i < queen.length; i++) { cw3[cw2[i]] = queen.length - i; } results.put(newSolution, number + "_self"); putNewSolution(leftRight, number + "_lr"); putNewSolution(upDown, number + "_ud"); putNewSolution(lurd, number + "_lurd"); putNewSolution(ruld, number + "_ruld"); putNewSolution(cw1, number + "_cw1"); putNewSolution(cw2, number + "_cw2"); putNewSolution(cw3, number + "_cw3"); return true; } protected void putNewSolution(Integer[] temp, String mark) { String newSolution = resultToString(temp); String flag = results.get(newSolution); if(flag == null) { results.put(newSolution, mark); } } protected String resultToString(Integer[] result) { StringBuilder sb = new StringBuilder(); for (int i = 1; i < queen.length; i++) { sb.append(result[i]); } return sb.toString(); } // 计算复杂度 15720 public static void main(String[] args) { Queens queen = new Queens(8); queen.backtrack(1); } }
相关推荐
算法设计源程序 java代码实现八皇后问题求解
八皇后java实现。八皇后问题是经典的回溯算法的应用,8x8的棋盘我们可以按行或者按列确定皇后的位置,比如我这边是按行安排皇后的位置,那么堆栈里存放的则是其所在列数。
八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。有多种方法可以解决此问题,这次利用java语言和递归以及回溯算法解决,至于其他语言见后续资源
八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八皇后问题 最简单dfs模板代码八...
C语言求解出八皇后所有解,稍作修改可以推至n皇后问题
n皇后问题的没有同义的解。用java语言实现n-queens算法
用JAVA实现的八皇后问题。学习JAVA时练手写的程序,分享下。我真是各种喜欢写八皇后算法
这是Java语言编写的八皇后问题求解程序的源代码及其输出结果。(能得到全部92种不同的解)
用回溯法解决八皇后问题,利用java的泛型栈,有兴趣的欢迎参考
经典八皇后问题,结构简单,算法不是最优的
八皇后问题 回溯法求解 Java程序设计 !!!!!! !!!!!!!!!! !!
八皇后的递归解法,欢迎改进讨论。 下载后把java 类放到想要的package 下即可运行
八皇后问题的实现代码,经过测试 可以用
遗传算法实现N皇后-java代码
这个文档关于八皇后问题,一共两种代码,输出分别为0和1的矩阵或者直接输出位置序号两种输出结果。代码是C++语言编写。
Java实现八皇后问题,两重循环,检查左右斜对角线,有压栈,回溯
用Java编程实现八皇后问题,程序中采用了回溯法实现八皇后这一传统问题。
0 资源分 八皇后 的三种解法 (java编写)