[工作准备--算法] 八皇后问题--递归求解

xiaoxiao2021-02-28  9

目标

在8*8的的国际象棋中摆上八个皇后 使其不能相互攻击

问题分析

问题的解向量:(x0,x2,x3,….,x7)

采用数组的下标i 表示皇后的所在行采用数组元素x[i]表示皇后的所在列向量

约束条件

显示约束 (对解向量的直接约束) xi=1,2,3…n隐示约束1 :任意两个皇后不同列 : xi=xj x i =≠ x j 隐示约束2 :两个皇后不处于同一对角线 : |ij||xixj| | i − j | ≠ | x i − x j |
/** *递归调用函数 放置第t 行的皇后 * @param t */ public void Backtrack(int t) { //递归终止条件 即第九行的皇后即结束(八皇后问题 注意数组的下标从0开始) if (t>7) { //输出放置皇后情况并且count++ output(x); } else { //循环是遍历在第一行上放置皇后 for(int i=0;i<8;i++) { x[t] = i; //如果符合约束条件 就放置下一行的皇后 if(Bound(t)) { Backtrack(t+1); } } } } /** * 判断 k行第 i列放置皇后 是否在约束条件中 * @param k 第几行要放置皇后 * @return */ public boolean Bound(int k ) { for(int i =0;i<k ;i++) { if((Math.abs(k-i)==Math.abs(x[k]-x[i]))||x[i]==x[k]) { return false; } } return true; }

最后的整体调用和类的实现代码如下(完整代码)

public class Queen { private int count =0; private int[] x = new int [8]; public static void main(String [] args) { Queen q = new Queen(); q.Backtrack(0); System.out.println(q.count); } /** * 判断当前放置的 k = i 是否在约束条件中 * @param k 第几行要放置皇后 * @return */ public boolean Bound(int k ) { for(int i =0;i<k ;i++) { if((Math.abs(k-i)==Math.abs(x[k]-x[i]))||x[i]==x[k]) { return false; } } return true; } /** *递归调用函数 放置第t 行的皇后 * @param t */ public void Backtrack(int t) { //递归终止条件 即第九行的皇后即结束(八皇后问题 注意数组的下标从0开始) if (t>7) { //输出放置皇后情况并且count++ output(x); } else { //循环是遍历在第一行上放置皇后 for(int i=0;i<8;i++) { x[t] = i; //如果符合约束条件 就放置下一行的皇后 if(Bound(t)) { Backtrack(t+1); } } } } private void output(int []x) { count++; for(int x1 :x) { System.out.print(x1+" "); } System.out.println(); } }

思路总结

这里使用了递归调用使得设计思想的时候更加简便和易读易懂了.但是递归调用在效率上因为要压栈(jvm栈–>线程安全的)等一系列的操作,使得效率不高效,同时所有的递归调用都可以用循环完成,只是不容易思考的设计而已.在使用递归调用时候一定要注意到递归结束标志,如果没有递归结束标志就会一直递归下去当遇到大量的数据时候最好不要使用递归调用,因为递归调用占用jvm栈的空间,而栈的空间是有限的.需要合理的使用.即循环递归嵌套层数不宜太多.
转载请注明原文地址: https://www.6miu.com/read-2349996.html

最新回复(0)