骑士周游问题，马踏棋盘算法

该问题实际上是图的深度优先搜索的应用。

package com.horsechess;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessBoard {

    private static int X;//棋盘的列
    private static int Y;//棋盘的行

    //创建一个数组，标记棋盘的各个位置是否被访问过
    public static boolean[] visited;

    //标记棋盘的所有位置是否都被访问过
    public static boolean finished;

    public static void main(String[] args) {
        System.out.println("骑士周游算法开始计算！");
        X = 8;
        Y = 8;
        int row = 1;//马儿初始位置的行，从1开始编号
        int column = 1;//马儿初始位置的列，从1开始编号

        //创建棋盘
        int[][] chessboard = new int[Y][X];
        visited = new boolean[X * Y];
        System.out.println(next(new Point(0,0)));
        //测试一下耗时
        long start = System.currentTimeMillis();
        traversalChessBoard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("一共耗时: " + (end-start));

        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }

    }


    /*
     * chessboard: 棋盘
     * row: 马儿当前所在的行
     * colu: 马儿当前所在的列
     * step: 第几步，初始位置就是第一步
     */
    public static void traversalChessBoard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;

        visited[row * X + column] = true;


        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps = next(new Point(column, row));
        //对ps进行排序
        sort(ps);
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);
            //判断该点是否被访问过
            if (!visited[p.y * X + p.x]) {
                traversalChessBoard(chessboard, p.y, p.x, step + 1);
            }
        }

        //判断是否为完成了任务，使用step与应该走的步数比较，
        //如果没有达到数量，任务就没有完成，则将棋盘置0
        //说明:step<X*Y有两种情况: 一种是棋盘棋盘目前位置仍然没有走完
        //                        另一种是处于回溯过程
        if (step < X * Y && !finished) {//这里的step是通过传参进来的，就意味着每层step是不一样的，
                                        //所以含需要一个finished变量，把step定义为类成员变量，就不要finished变量
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }


    //Point是java中自带的类
    /*
     * 功能: 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList)，做多有八个位置
     */
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();

        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }

        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }

        return ps;
    }

    /*
     * 使用贪心算法进行优化
     * 1.我们获取当前位置可以走的下一位置的集合
     *   ArrayList<Point> ps = next(new Point(column, row))
     * 2.我们需要对ps中所有的point的下一步所有集合的数目，进行非递减排序
     */

    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                //获取o1和o2下一步所有位置个数
                int count1=next(o1).size();
                int count2=next(o2).size();
                if(count1<count1){
                    return -1;
                }else if (count1==count2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });


    }


}

有什么疑问，可以评论或私信我

更多数据结构问题代码实现请查看一下链接

JavaTest/denglianbin/src/com · 邓联斌/deng_study - 码云 - 开源中国 (gitee.com)