淘先锋技术网

首页 1 2 3 4 5 6 7

骑士周游问题/马踏棋盘问题

骑士周游问题的解决步骤和思路分析

  1. 创建棋盘chessBoard,是二维数组
  2. 将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入一个集合中(ArrayList),每走一步,使用step+1
  3. 遍历ArrayList中存放的所有位置,看看那个可以走,如果可以走通,就继续走,走不通,就回溯
  4. 判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘设置为0

注意:马儿走的策略不同,得到的结果也不一样,效率也不一样

在这里插入图片描述

优化分析:

  1. 我们现在走的下一个位置,是按照我们顺时针来挑选位置,因此选择的这个点的下一个可以走的位置的个数是不确定的
  2. 优化思路是:我们应该选择下一个的下一个可以走的位置较少的点,开始走,这样可以减少回溯的次数
  3. 代码:对我们ps集合按照可以走的下一个位置的次数进行排序,升序排序
@SuppressWarnings("all")
public class HorseChessBoard {

    //定义属性
    private static final int X = 6;//表示列
    private static final int Y = 6;//表示行
    private static int[][] chessBoard = new int[Y][X];//棋盘
    private static boolean[] visited = new boolean[X * Y];//记录某个位置走过
    private static boolean finished = false;//记录马儿是否遍历完棋盘

    public static void main(String[] args) {

        int row = 3;
        int col = 3;
        long l = System.currentTimeMillis();
        traversalChessBoard(chessBoard,row - 1,col - 1,1);
        long l1 = System.currentTimeMillis();
        System.out.println("耗时:"+ (l1 - l));
        //输入当前棋盘的情况
        for (int[] rows : chessBoard) {
            for (int step : rows) {//step,表示,该位置是马儿应该走的第几步
                System.out.print(step+"\t");
            }
            System.out.println();
        }

    }

    //编写最核心的算法,遍历棋盘,如果遍历成功,就把finished 设置为true
    public static void traversalChessBoard(int[][] chessBoard,int row,int col,int step){
        //先把step 记录到chessBoard
        chessBoard[row][col] = step;//将二维数组中当前位置,设置为走的第几步
        //把这个位置,设置为已经访问
        visited[row * X + col] = true;
        //获取当前位置可以走的下一个位置有哪些
        ArrayList<Point> ps = next(new Point(col, row));//col - X   row - Y
        sort(ps);
        //遍历
        while (!ps.isEmpty()){
            //取出当前这个ps,第一个位置(点)
            Point p = ps.remove(0);
            //判断该位置是否走过,如果没有走过,我们就递归遍历
            if(!visited[p.y * X + p.x]){
                //递归遍历
                traversalChessBoard(chessBoard,p.y,p.x,step+1);
            }
        }
        //当退出while循环,看看是否遍历成功,如果没有成功,就重置相应的值,然后进行回溯
        if (step < X * Y && !finished){
            //重置
            chessBoard[row][col] = 0;
            visited[row * X + col] = false;
        }else{
            finished = true;
        }


    }

    //写一个方法,对ps的各个位置,可以走的下一个位置的次数进行排序,把可能走的下一个位置从小到大排序
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                    return next(o1).size() - next(o2).size();
            }
        });
    }

    //编写方法,可以获取当前位置,可以走的下一步的所有位置(Point表示 x,y)
    public static ArrayList<Point> next(Point curPoint){
        ArrayList<Point> ps = new ArrayList<>();
        //创建一个Point对象(点/位置),准备放入到ps
        //public Point() {//Point的无参构造器
        //        this(0, 0);
        //    }
        //public Point(Point p) {//Point的有参构造器,传入一个Point对象
        //        this(p.x, p.y);
        //    }
        //public Point(int x, int y) {//Point的有参构造器,传入x,y值
        //        this.x = x;
        //        this.y = y;
        //    }
        Point p1 = new Point();
        //判断在curPoint 是否可以走如下位置,如果可以走,就将该点,放入到ps中
        //判断是否可以走5位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0){
            ps.add(new Point(p1));
        }
        //判断是否可以走6位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0){
            ps.add(new Point(p1));
        }
        //判断是否可以走7位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0){
            ps.add(new Point(p1));
        }
        //判断是否可以走0位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0){
            ps.add(new Point(p1));
        }
        //判断是否可以走1位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y){
            ps.add(new Point(p1));
        }
        //判断是否可以走2位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y){
            ps.add(new Point(p1));
        }
        //判断是否可以走3位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y){
            ps.add(new Point(p1));
        }
        //判断是否可以走4位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y){
            ps.add(new Point(p1));
        }


        return  ps;

    }
}