JAVA实现八皇后问题-(使用回溯加双端算法)

Java代码分享 收藏
0 85

八皇后描述-图解

20191216220209399
写法思路 使用回溯和栈或双端队列实现
 提示:
  1. 存储每一次回溯对应的索引信息
  2. 每次都要判断当前层索引与之前回溯层的索引是否有冲突( 判断是否在同一列上,或同一斜线上)
  3. 不管在某一层上循环一次都要更新当前层的索引信息

八皇后规则:
     * 思路:
     *      同一行上怎么判断:   其实就是判断每一层的索引是否有相同的 有相同就代表有同一行的
     *      同一斜线上怎么处理: 如果列差==行差就是同一斜线上
     *          如何判断列差:当前原循环层对应的索引-当前层准备添加的索引 就是列差
     *          如果判断行差:当前原循环层数-当前原循环最大层数

代码实现
//八皇后演示
public class EightQueenDemo {

    public static void main(String[] args) {

        List<List> eightQueenGroupWay = EightQueen.getEightQueenGroupWay(8);
        System.out.println("一共有:"+eightQueenGroupWay.size()+"种方式");
        for(List arr:eightQueenGroupWay){
            System.out.println(arr.toString());
        }
    }
}


//创建一个八皇后类
class EightQueen{


    //创建一个获取八皇后的组合方法
    public static List<List> getEightQueenGroupWay(Integer chessboardSize){

        //创建一个组合结果集集合
        List<List> resultList=new ArrayList<>();
        //创建一个Deque双端队列
        Deque layerIndexs=new ConcurrentLinkedDeque<>();
        //调用实现
        getEightQueenGroupWay(chessboardSize,resultList,layerIndexs);

        return resultList;
    }
    //创建一个获取八皇后的组合方法实现
    private static void getEightQueenGroupWay(Integer chessboardSize,List<List> resultList,Deque layerIndexs){

        //循环遍历当前一个棋盘索引
        for(int index=0;index<chessboardSize;index++){

            //判断当前新添加指定的位置是否符合皇后的规则
            if(EightQueenRuleJudge(layerIndexs,index)){

                //将当前回溯层对应的索引存储到layerIndexs中
                layerIndexs.addLast(index);

                //判断是否已经回溯到chessboardSize层
                if(chessboardSize==layerIndexs.size())  {

                    //创建一个当前组合好的皇后集合
                    List queenGroupList=new ArrayList<>();
                    for(Integer currIndex:layerIndexs.toArray(new Integer[layerIndexs.size()])){
                        queenGroupList.add(currIndex);
                    }
                    resultList.add(queenGroupList);
                }else{
                    //由于还是没有回溯到最后一层继续回溯
                    getEightQueenGroupWay(chessboardSize,resultList,layerIndexs);
                }
                //将当前层对应的索引更新移除
                layerIndexs.removeLast();
            }
        }

    }
    //8皇后规则判断  2个棋子不能在同一行或同一斜线上
    /**
     * @param layerIndexs       之前层对应的每一层的索引
     * @param currentLayerIndex 当前层对应的索引
     * @return  true符合规则        false 不符合规则
     *
     * 思路:
     *      同一行上怎么判断:   其实就是判断每一层的索引是否有相同的 有相同就代表有同一行的
     *      同一斜线上怎么处理:  如果列差==行差就是同一斜线上
     *          如何判断列差:当前原循环层对应的索引-当前层准备添加的索引 就是列差
     *          如果判断行差:当前原循环层数-当前原循环最大层数
     */
    private static boolean EightQueenRuleJudge(Deque layerIndexs,Integer currentLayerIndex){

        //判断是否在同一条线上(是否索引相同)
        if(layerIndexs.contains(currentLayerIndex)){
            return false;
        }
        //将当前每一层的索引转换成数组
        Object[] layerIndexsArr=layerIndexs.toArray();
        for(int index=0;index<layerIndexsArr.length;index++){

            //判断是否在同一斜线上(如果列差==行差就是同一斜线上)
            if(Math.abs(index-layerIndexsArr.length)==Math.abs(((Integer)layerIndexsArr[index])-currentLayerIndex)){
                return false;
            }
        }
        return true;
    }
}


结果

20200325212616871






版权声明:本文为「丿旧城以西」的原创文章,遵循 CC 4.0 BY-SA 版权协议
原文链接:https://blog.csdn.net/weixin_44698882/article/details/103571107



    暂时没有人评论
0