算法：中国象棋中"马"的最少步数走法和不重复周游走法的实现（利用图论算法中的BFS和DFS）

之前发布了许多的图论算法的例子，今天我们结合中国象棋中马的走法，来实践一下图论算法中的BFS（涉及Dijkstra算法）和DFS算法

为什么用中国象棋的马的走法来做例子呢？因为大家都多多少少知道中国象棋，也知道马走斜日象飞田，车走直线炮翻山。马在中国象棋棋盘上的斜日走法，确实值得拿来作为图论算法的例子。以下的算法没有蹩脚马的限制，马只要不出棋盘，可以随便在棋盘上走斜日

如何在程序中记录中国象棋棋盘的点位呢？我们规定，中国象棋棋盘从左到右为X轴的正方向，从1开始，也就是棋盘从左到右1-9；中国象棋棋盘从上到下为Y轴的正方向，从1开始，也就是棋盘从上到下1-10。比如我方从左到右第二个兵，点位坐标就是（3,7）。这个应该不难理解。

今天我们将要实现的算法是：

1、给出马在中国象棋棋盘上的初始点位，计算出到达所有其他点位的最少步数的走法路径图，可能有其他走法，但找不到比当前解法步数还少的走法。经过编程运行，该算法时间复杂度不大，运行时间为秒级就能得到某一点位到其他所有点位的最少步数路径图

2、给出马在中国象棋棋盘上的初始点位，计算出其周游所有其他点位的路径图，路径要经过中国象棋棋盘的所有点位，每个点位只能经过一次且必须经过一次。经过编程运行，该算法的时间复杂度随棋盘点位数总和的增大而呈指数级增长。我的电脑都蓝屏了，都没有得到结果。所以本例就将中国象棋的棋盘缩小为5*5的规格来运行算法

以下是我的算法实现源代码，精髓都在代码和注释中，可复制到IDE中运行（所有的java文件放同一package里就行）：

1、中国象棋上的点位的类：Position.java

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/**
 * 中国象棋上面的点位的类
 * @Author: LiYang
 * @Date: 2019/9/16 12:06
 */
public class Position {

    //国际象棋从左到右的X轴坐标，
    //从左到右分别是1-9
    public int xPos;

    //国际象棋从上到下的Y轴坐标，
    //从上到下分别是1-10
    public int yPos;

    //X轴坐标的最大值，用于判断点位是否在棋盘内
    //如果是运行马的不重复遍历算法，本来应该是9的，
    //但是时间复杂度太高，计算量太大，改棋盘为5×5
    public static final int xPosMax = 9;

    //X轴坐标的最大值，用于判断点位是否在棋盘内
    //如果是运行马的不重复遍历算法，本来应该是10的，
    //但是时间复杂度太高，计算量太大，改棋盘为5×5
    public static final int yPosMax = 10;

    /**
     * 构造方法，用棋盘的X、Y轴来入参
     * @param xPos X轴的坐标
     * @param yPos Y轴的坐标
     */
    public Position(int xPos, int yPos) {
        this.xPos = xPos;
        this.yPos = yPos;
    }

    /**
     * 重写toString方法，把坐标点表示为数学中的格式
     * @return 数学中坐标点的格式
     */
    @Override
    public String toString() {
        return "(" + xPos + "," + yPos + ")";
    }

    /**
     * 将当前点位转化为算法表里面的key的格式
     * @return 算法表里面的key的格式
     */
    public String toKey(){
        return xPos + "-" + yPos;
    }

    /**
     * 获取马在该点下一步可以跳的其他点
     * @param positionKey 当前位置的算法表key
     * @param chineseChessRouteMap 算法表
     * @return 马可以到达的点位的集合
     */
    public static List<Position> getNeighborPositionList(String positionKey, Map<String, Route> chineseChessRouteMap){
        //下一步点位集合
        List<String> positionKeyList = new ArrayList<>();

		//解析坐标轴
        int xPos = Integer.parseInt(positionKey.split("-")[0]);
        int yPos = Integer.parseInt(positionKey.split("-")[1]);

        //马往左上角跳的情况：
        positionKeyList.add(positionCheck(xPos - 1, yPos - 2));
        positionKeyList.add(positionCheck(xPos - 2, yPos - 1));

        //马往右上角跳的情况：
        positionKeyList.add(positionCheck(xPos + 1, yPos - 2));
        positionKeyList.add(positionCheck(xPos + 2, yPos - 1));

        //马往左下角跳的情况：
        positionKeyList.add(positionCheck(xPos - 1, yPos + 2));
        positionKeyList.add(positionCheck(xPos - 2, yPos + 1));

        //马往右下角跳的情况：
        positionKeyList.add(positionCheck(xPos + 1, yPos + 2));
        positionKeyList.add(positionCheck(xPos + 2, yPos + 1));

        //去除棋盘外的部分
        Iterator<String> iterator = positionKeyList.iterator();

        //迭代去除棋盘外的点位
        while (iterator.hasNext()){
            if ("".equals(iterator.next())){
                iterator.remove();
            }
        }

        //将点位转换成对象
        List<Position> positionList = new ArrayList<>();

        //遍历转换
        for (String posKey : positionKeyList){
            positionList.add(chineseChessRouteMap.get(posKey).position);
        }

        //返回下一步的点位集合
        return positionList;
    }

    /**
     * 验证点位是否在棋盘内
     * @param xPos 横坐标，1开始
     * @param yPos 纵坐标，1开始
     * @return 判断是否在棋盘内，在棋盘内就返回key，否则返回空串
     */
    public static String positionCheck(int xPos, int yPos){
        if(xPos >= 1 && xPos <= xPosMax && yPos >= 1 && yPos <= yPosMax){
            return xPos + "-" + yPos;
        } else {
            return "";
        }
    }

    /**
     * 重写equals方法
     * @param obj
     * @return
     */
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Position)){
            return false;
        }

        //用算法表的key来判断
        return this.toKey().equals(((Position) obj).toKey());
    }

    /**
     * 重写hashCode方法
     * @return
     */
    @Override
    public int hashCode() {
        //用算法表的key的hashCode
        return this.toKey().hashCode();
    }

}

2、中国象棋的路径图的类：Route.java

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 中国象棋的路径图类
 * @Author: LiYang
 * @Date: 2019/9/16 12:04
 */
public class Route {

    //中国象棋的点位信息
    public Position position;

    //该点位是否被访问过，默认为false
    public boolean visited;

    //马走过的步数
    public int step;

    //上一步的点位
    public Position previous;

    /**
     * 初始化中国象棋棋盘（迪杰斯塔拉(Dijkstra)算法表）
     * key的格式：xPos-yPos
     * @return
     */
    public static Map<String, Route> initChineseChessRouteMap(){
        //中国象棋点位的迪杰斯塔拉(Dijkstra)算法表
        Map<String, Route> chineseChessRouteMap = new LinkedHashMap<>();

        //初始化算法表
        for (int xPos = 1; xPos <= Position.xPosMax; xPos++){
            for (int yPos = 1; yPos <= Position.yPosMax; yPos++){
                //中国象棋棋盘，一个点位对应一个Route类
                Route route = new Route();

                //当前点位
                route.position = new Position(xPos, yPos);

                //是否访问。初始化为false
                route.visited = false;

                //马走过的步数，默认为无穷大
                route.step = Integer.MAX_VALUE;

                //当前点位的前一个点位，默认为空
                route.previous = null;

                //以 xPos-yPos 为键，比如 "3-2"，装入算法表
                chineseChessRouteMap.put(xPos + "-" + yPos, route);
            }
        }

        //返回初始化好了的中国象棋棋盘（迪杰斯塔拉(Dijkstra)算法表）
        return chineseChessRouteMap;
    }

    /**
     * 找到当前路径图中未访问的路径中步数最小的点位的键
     * @param chineseChessRouteMap 中国象棋棋盘（迪杰斯塔拉(Dijkstra)算法表）
     * @return 未访问的路径中步数最小的点位的键
     */
    public static String findMinimumRouteMapKey(Map<String, Route> chineseChessRouteMap){
        //最小步数
        int minimum = Integer.MAX_VALUE;

        //先找到最小步数
        for (Map.Entry<String, Route> item : chineseChessRouteMap.entrySet()){

            //如果是已经访问过了的，则跳过
            if (item.getValue().visited){
                continue;
            }

            //如果当前步数小于最小步数
            if (item.getValue().step < minimum){
                //就更新最小步数
                minimum = item.getValue().step;
            }
        }

        //根据最小步数，找到其对应的键
        for (Map.Entry<String, Route> item : chineseChessRouteMap.entrySet()){

            //如果是已经访问过了的，则跳过
            if (item.getValue().visited){
                continue;
            }

            //如果当前点位等于最小步数
            if (item.getValue().step == minimum){
                //返回当前点位的键
                return item.getKey();
            }
        }

        //如果找不到就返回空串，但是事实上不会到这里
        //因为后续的算法会判断是否全部访问
        //下面返回空串，只是为了程序的完整
        return "";
    }

    /**
     * 检查是否还未全部访问过
     * @param chineseChessRouteMap （迪杰斯塔拉(Dijkstra)算法表）
     * @return 是否还未全部访问过
     */
    public static boolean isNotAllKnown(Map<String, Route> chineseChessRouteMap){
        //遍历迪杰斯塔拉(Dijkstra)算法表
        for (Map.Entry<String, Route> item : chineseChessRouteMap.entrySet()){

            //如果找到了一个未访问的点位
            if (!item.getValue().visited){
                //返回：未全部访问过为真
                return true;
            }
        }

        //找完了还没有找到一个未访问过的点位
        //返回：未全部访问过为假
        return false;
    }

    /**
     * 重写toString方法，
     * @return
     */
    @Override
    public String toString() {
        return "Route{" +
                "position=" + position +
                ", visited=" + visited +
                ", step=" + step +
                ", previous=" + previous +
                };
    }

}

3、中国象棋类，里面包含马的两种算法的实现：ChineseChess.java

import java.util.*;

/**
 * 中国象棋类
 * BFS：计算马从任意点位开始，跳到其他所有点位的最少步骤走法
 * DFS：计算马从任意点位开始，不重复走过其他所有点位的走法
 * @Author: LiYang
 * @Date: 2019/9/16 12:03
 */
public class ChineseChess {

    /**
     * 重要方法：通过BFS的思想，用迪杰斯塔拉(Dijkstra)算法来实现
     * 马从任意点位开始，跳到其他所有点位的最少步骤走法
     * @param startPosition 计算马最短跳法的起始点位
     */
    public static void calculateHorseShortestStep(String startPosition){
        //先获取初始化的中国象棋迪杰斯塔拉(Dijkstra)算法表
        Map<String, Route> routeMap = Route.initChineseChessRouteMap();

        //将起点，步数设置为0
        routeMap.get(startPosition).step = 0;

        //如果还有未访问到的点位
        while (Route.isNotAllKnown(routeMap)){
            //找出最小的
            String minimumKey = Route.findMinimumRouteMapKey(routeMap);

            //标记为已访问
            routeMap.get(minimumKey).visited = true;

            //获取当前位置的步数
            int currentStep = routeMap.get(minimumKey).step;

            //获得它的下一步的地方
            List<Position> nextList = Position.getNeighborPositionList(minimumKey, routeMap);

            //遍历下一步
            for (Position nextPos : nextList){
                //如果已访问，则跳过
                if (routeMap.get(nextPos.toKey()).visited){
                    continue;
                }

                //未访问，则取出其步数
                int nextPosStep = routeMap.get(nextPos.toKey()).step;

                //如果当前位置的步数+1比下一步的步数还小的话，那就更新下一步的步数
                if (currentStep + 1 < nextPosStep){

                    //下一个点位的步数更新为当前点位步数+1
                    routeMap.get(nextPos.toKey()).step = currentStep + 1;

                    //下一个点位的前一个点位更新为当前点位
                    routeMap.get(nextPos.toKey()).previous = routeMap.get(minimumKey).position;
                }
            }
        }

        //处理结果
        for (Map.Entry<String, Route> item : routeMap.entrySet()){
            dealWithResult(startPosition, item.getKey(), routeMap);
        }
    }

    /**
     * 根据计算出来的中国象棋版的迪杰斯塔拉(Dijkstra)算法表，
     * 打印从起始点位到目的点位马的最少步骤的走法路径
     * @param startPosition 马的起始点位
     * @param endPosition 马的目的点位
     * @param routeMap 中国象棋版的迪杰斯塔拉(Dijkstra)算法表
     */
    public static void dealWithResult(String startPosition, String endPosition, Map<String, Route> routeMap){
        //路径集合
        List<Position> routeList = new ArrayList<>();

        //加入目的点位（先是逆序存放）
        routeList.add(routeMap.get(endPosition).position);

        //当前点位的key
        String currentPositionKey = endPosition;

        //如果当前点位的上一个点位不为null，也就是还没到起始点位
        while (routeMap.get(currentPositionKey).previous != null){

            //获得上一个点位
            Position previousPosition = routeMap.get(currentPositionKey).previous;

            //装入路径集合
            routeList.add(previousPosition);

            //获取上一个点位的key，并更新为当前点位的key，进行下一次循环
            currentPositionKey = previousPosition.toKey();
        }

        //循环完毕后，由于是逆序，所以需要将集合反序
        Collections.reverse(routeList);

        //以下是输出路径图的打印逻辑
        System.out.print(routeMap.get(startPosition).position + " -> "
                + routeMap.get(endPosition).position + "：" );

        for (int i = 0; i < routeList.size(); i++) {
            if (i == 0){
                System.out.print(routeList.get(i));
            } else {
                System.out.print(" -> " + routeList.get(i));
            }

            if (i == routeList.size() - 1){
                System.out.println();
            }
        }
    }

    /**
     * 重要方法：通过DFS的思想，用递归算法来实现
     * 马从任意点位开始，遍历其他所有点的走法，每个
     * 点位只能经过一次
     * @param routeMap 迪杰斯塔拉(Dijkstra)算法表作为辅助
     * @param routeSet 马的遍历走法点位路径记录集合
     * @param currentPosKey 当前要尝试遍历的点位
     */
    public static void chineseChessHorseDFS(Map<String, Route> routeMap, LinkedHashSet<Position> routeSet, String currentPosKey){
        //如果集合已经装了所有步骤的路径图，就差最后一步了
        //注意，递归进入到这个方法前，是判断了重复了的
        if (routeSet.size() == (Position.xPosMax * Position.yPosMax - 1)){

            //把这最后一步加上
            routeSet.add(routeMap.get(currentPosKey).position);

            //拼凑路径的字符串表达方式
            String route = routeSet.toString().replaceAll(", ", " -> ");
            route = route.substring(1, route.length() - 1);

            //打印结果
            System.out.println("找到路线了：" + route);

            //结束递归
            return;
        }

        //如果还没找到头，找其下一步的节点
        List<Position> nextList = Position.getNeighborPositionList(currentPosKey, routeMap);

        //把当前节点加入到路径图中
        routeSet.add(routeMap.get(currentPosKey).position);

        //筛除掉下一步的节点不可用的部分
        Iterator<Position> iterator = nextList.iterator();

        //用迭代器来删除
        while (iterator.hasNext()){
            Position position = iterator.next();
            if (routeSet.contains(position)){
                iterator.remove();
            }
        }

        //如果筛除完毕后，变成空集合了，那递归也就进行不下去了
        //马到了现在的情况已无路可走了，结束当前分支的递归
        if (nextList.size() == 0){
            return;
        }

        //如果马还没走到头，况且还有下一步可以走
        for (Position nextPos : nextList){
            //递归调用本方法，对每一个下一步进行尝试探索
            chineseChessHorseDFS(routeMap, setShallowCopy(routeSet), nextPos.toKey());
        }
    }

    /**
     * 浅拷贝一个当前路径图集合的副本
     * @param source 当前路径图集合（拷贝源）
     * @return 当前路径图集合的浅拷贝副本
     */
    public static LinkedHashSet<Position> setShallowCopy(LinkedHashSet<Position> source){
        //全新的集合
        LinkedHashSet<Position> copy = new LinkedHashSet<>();

        //将原来路径图的集合里面的点位指针，都重新赋给新集合
        for (Position item : source){
            copy.add(item);
        }

        //返回浅拷贝的新集合
        return copy;
    }

    /**
     * 重要方法：用DFS来递归求得马的遍历算法
     * @param startPosition 马的起始点位key
     */
    public static void chineseChessHorseDFS(String startPosition){
        //获得用于辅助的中国象棋版的迪杰斯塔拉(Dijkstra)算法表
        Map<String, Route> routeMap = Route.initChineseChessRouteMap();

        //初始的路径图集合
        LinkedHashSet<Position> routeSet = new LinkedHashSet<>();

        //开始递归调用重要的子方法
        chineseChessHorseDFS(routeMap, routeSet, startPosition);

        //代码执行到了这里，表示已经寻找完毕了
        System.out.println("寻找完毕");
    }

    /**
     * 运行中国象棋马的最少步路径算法和不重复遍历路径算法
     * 注意，这两个方法要分开执行，还要修改Position类的参数
     * 执行一个的时候，需要注释掉另外一个。本例中我们的马
     * 的起始位置都在左上角，大家可自行修改参数，运行代码
     * @param args
     */
    public static void main(String[] args) {
        //执行马的最少步路径算法，因为这个算法时间复杂度不高，
        //所以用中国象棋的整个棋盘，也就是修改Position类的参数如下：
        //public static final int xPosMax = 9;
        //public static final int yPosMax = 10;
        calculateHorseShortestStep("1-1");

        //执行马的不重复遍历路径算法，因为这个算法时间复杂度太高，
        //所以将中国象棋棋盘缩小为5*5，也就是修改Position类的参数如下：
        //public static final int xPosMax = 5;
        //public static final int yPosMax = 5;
        chineseChessHorseDFS("1-1");
    }

}

运行第一个方法（注意要同时注释第二个方法，否则你的计算机就停不下来了，我还蓝屏了。注意，此时Position类的xPosMax = 9，yPosMax = 10，马起始点在左上角），得到路径图（马从中国象棋的左上角开始计算到其他所有点的最少步数到达的路径图），以下是控制台输出的路径图：

(1,1) -> (1,1)：(1,1)
(1,1) -> (1,2)：(1,1) -> (3,2) -> (2,4) -> (1,2)
(1,1) -> (1,3)：(1,1) -> (3,2) -> (1,3)
(1,1) -> (1,4)：(1,1) -> (2,3) -> (3,5) -> (1,4)
(1,1) -> (1,5)：(1,1) -> (2,3) -> (1,5)
(1,1) -> (1,6)：(1,1) -> (3,2) -> (2,4) -> (1,6)
(1,1) -> (1,7)：(1,1) -> (3,2) -> (1,3) -> (2,5) -> (1,7)
(1,1) -> (1,8)：(1,1) -> (2,3) -> (3,5) -> (1,4) -> (2,6) -> (1,8)
(1,1) -> (1,9)：(1,1) -> (2,3) -> (1,5) -> (2,7) -> (1,9)
(1,1) -> (1,10)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (2,8) -> (1,10)
(1,1) -> (2,1)：(1,1) -> (3,2) -> (1,3) -> (2,1)
(1,1) -> (2,2)：(1,1) -> (2,3) -> (3,5) -> (1,4) -> (2,2)
(1,1) -> (2,3)：(1,1) -> (2,3)
(1,1) -> (2,4)：(1,1) -> (3,2) -> (2,4)
(1,1) -> (2,5)：(1,1) -> (3,2) -> (1,3) -> (2,5)
(1,1) -> (2,6)：(1,1) -> (2,3) -> (3,5) -> (1,4) -> (2,6)
(1,1) -> (2,7)：(1,1) -> (2,3) -> (1,5) -> (2,7)
(1,1) -> (2,8)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (2,8)
(1,1) -> (2,9)：(1,1) -> (3,2) -> (1,3) -> (2,5) -> (1,7) -> (2,9)
(1,1) -> (2,10)：(1,1) -> (2,3) -> (3,5) -> (1,4) -> (2,6) -> (1,8) -> (2,10)
(1,1) -> (3,1)：(1,1) -> (2,3) -> (3,1)
(1,1) -> (3,2)：(1,1) -> (3,2)
(1,1) -> (3,3)：(1,1) -> (3,2) -> (2,4) -> (1,2) -> (3,3)
(1,1) -> (3,4)：(1,1) -> (3,2) -> (1,3) -> (3,4)
(1,1) -> (3,5)：(1,1) -> (2,3) -> (3,5)
(1,1) -> (3,6)：(1,1) -> (2,3) -> (1,5) -> (3,6)
(1,1) -> (3,7)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (3,7)
(1,1) -> (3,8)：(1,1) -> (3,2) -> (1,3) -> (2,5) -> (1,7) -> (3,8)
(1,1) -> (3,9)：(1,1) -> (2,3) -> (1,5) -> (2,7) -> (3,9)
(1,1) -> (3,10)：(1,1) -> (2,3) -> (1,5) -> (2,7) -> (1,9) -> (3,10)
(1,1) -> (4,1)：(1,1) -> (3,2) -> (5,3) -> (4,1)
(1,1) -> (4,2)：(1,1) -> (2,3) -> (4,2)
(1,1) -> (4,3)：(1,1) -> (3,2) -> (2,4) -> (4,3)
(1,1) -> (4,4)：(1,1) -> (2,3) -> (4,4)
(1,1) -> (4,5)：(1,1) -> (3,2) -> (2,4) -> (4,5)
(1,1) -> (4,6)：(1,1) -> (3,2) -> (1,3) -> (2,5) -> (4,6)
(1,1) -> (4,7)：(1,1) -> (2,3) -> (3,5) -> (4,7)
(1,1) -> (4,8)：(1,1) -> (2,3) -> (1,5) -> (2,7) -> (4,8)
(1,1) -> (4,9)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (2,8) -> (4,9)
(1,1) -> (4,10)：(1,1) -> (3,2) -> (1,3) -> (2,5) -> (1,7) -> (2,9) -> (4,10)
(1,1) -> (5,1)：(1,1) -> (3,2) -> (5,1)
(1,1) -> (5,2)：(1,1) -> (2,3) -> (3,1) -> (5,2)
(1,1) -> (5,3)：(1,1) -> (3,2) -> (5,3)
(1,1) -> (5,4)：(1,1) -> (2,3) -> (3,5) -> (5,4)
(1,1) -> (5,5)：(1,1) -> (3,2) -> (1,3) -> (3,4) -> (5,5)
(1,1) -> (5,6)：(1,1) -> (2,3) -> (3,5) -> (5,6)
(1,1) -> (5,7)：(1,1) -> (2,3) -> (1,5) -> (3,6) -> (5,7)
(1,1) -> (5,8)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (3,7) -> (5,8)
(1,1) -> (5,9)：(1,1) -> (2,3) -> (3,5) -> (4,7) -> (5,9)
(1,1) -> (5,10)：(1,1) -> (2,3) -> (1,5) -> (2,7) -> (3,9) -> (5,10)
(1,1) -> (6,1)：(1,1) -> (2,3) -> (4,2) -> (6,1)
(1,1) -> (6,2)：(1,1) -> (3,2) -> (5,3) -> (4,1) -> (6,2)
(1,1) -> (6,3)：(1,1) -> (2,3) -> (4,2) -> (6,3)
(1,1) -> (6,4)：(1,1) -> (3,2) -> (2,4) -> (4,3) -> (6,4)
(1,1) -> (6,5)：(1,1) -> (2,3) -> (4,4) -> (6,5)
(1,1) -> (6,6)：(1,1) -> (3,2) -> (2,4) -> (4,5) -> (6,6)
(1,1) -> (6,7)：(1,1) -> (3,2) -> (1,3) -> (2,5) -> (4,6) -> (6,7)
(1,1) -> (6,8)：(1,1) -> (2,3) -> (3,5) -> (4,7) -> (6,8)
(1,1) -> (6,9)：(1,1) -> (2,3) -> (1,5) -> (2,7) -> (4,8) -> (6,9)
(1,1) -> (6,10)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (2,8) -> (4,9) -> (6,10)
(1,1) -> (7,1)：(1,1) -> (2,3) -> (3,1) -> (5,2) -> (7,1)
(1,1) -> (7,2)：(1,1) -> (3,2) -> (5,1) -> (7,2)
(1,1) -> (7,3)：(1,1) -> (2,3) -> (3,1) -> (5,2) -> (7,3)
(1,1) -> (7,4)：(1,1) -> (3,2) -> (5,3) -> (7,4)
(1,1) -> (7,5)：(1,1) -> (2,3) -> (3,5) -> (5,4) -> (7,5)
(1,1) -> (7,6)：(1,1) -> (3,2) -> (1,3) -> (3,4) -> (5,5) -> (7,6)
(1,1) -> (7,7)：(1,1) -> (2,3) -> (3,5) -> (5,6) -> (7,7)
(1,1) -> (7,8)：(1,1) -> (2,3) -> (1,5) -> (3,6) -> (5,7) -> (7,8)
(1,1) -> (7,9)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (3,7) -> (5,8) -> (7,9)
(1,1) -> (7,10)：(1,1) -> (2,3) -> (3,5) -> (4,7) -> (5,9) -> (7,10)
(1,1) -> (8,1)：(1,1) -> (3,2) -> (5,3) -> (4,1) -> (6,2) -> (8,1)
(1,1) -> (8,2)：(1,1) -> (2,3) -> (4,2) -> (6,1) -> (8,2)
(1,1) -> (8,3)：(1,1) -> (3,2) -> (5,3) -> (4,1) -> (6,2) -> (8,3)
(1,1) -> (8,4)：(1,1) -> (2,3) -> (4,2) -> (6,3) -> (8,4)
(1,1) -> (8,5)：(1,1) -> (3,2) -> (2,4) -> (4,3) -> (6,4) -> (8,5)
(1,1) -> (8,6)：(1,1) -> (2,3) -> (4,4) -> (6,5) -> (8,6)
(1,1) -> (8,7)：(1,1) -> (3,2) -> (2,4) -> (4,5) -> (6,6) -> (8,7)
(1,1) -> (8,8)：(1,1) -> (3,2) -> (1,3) -> (2,5) -> (4,6) -> (6,7) -> (8,8)
(1,1) -> (8,9)：(1,1) -> (2,3) -> (3,5) -> (4,7) -> (6,8) -> (8,9)
(1,1) -> (8,10)：(1,1) -> (2,3) -> (1,5) -> (2,7) -> (4,8) -> (6,9) -> (8,10)
(1,1) -> (9,1)：(1,1) -> (3,2) -> (5,1) -> (7,2) -> (9,1)
(1,1) -> (9,2)：(1,1) -> (2,3) -> (3,1) -> (5,2) -> (7,1) -> (9,2)
(1,1) -> (9,3)：(1,1) -> (3,2) -> (5,1) -> (7,2) -> (9,3)
(1,1) -> (9,4)：(1,1) -> (2,3) -> (3,1) -> (5,2) -> (7,3) -> (9,4)
(1,1) -> (9,5)：(1,1) -> (3,2) -> (5,3) -> (7,4) -> (9,5)
(1,1) -> (9,6)：(1,1) -> (2,3) -> (3,5) -> (5,4) -> (7,5) -> (9,6)
(1,1) -> (9,7)：(1,1) -> (3,2) -> (1,3) -> (3,4) -> (5,5) -> (7,6) -> (9,7)
(1,1) -> (9,8)：(1,1) -> (2,3) -> (3,5) -> (5,6) -> (7,7) -> (9,8)
(1,1) -> (9,9)：(1,1) -> (2,3) -> (1,5) -> (3,6) -> (5,7) -> (7,8) -> (9,9)
(1,1) -> (9,10)：(1,1) -> (3,2) -> (2,4) -> (1,6) -> (3,7) -> (5,8) -> (7,9) -> (9,10)

找到路线了：(1,1) -> (3,2) -> (5,1) -> (4,3) -> (2,4) -> (4,5) -> (5,3) -> (4,1) -> (2,2) -> (1,4) -> (3,5) -> (5,4) -> (3,3) -> (1,2) -> (3,1) -> (5,2) -> (4,4) -> (2,5) -> (1,3) -> (2,1) -> (4,2) -> (2,3) -> (1,5) -> (3,4) -> (5,5)
找到路线了：(1,1) -> (3,2) -> (5,1) -> (4,3) -> (5,5) -> (3,4) -> (1,5) -> (2,3) -> (3,1) -> (5,2) -> (4,4) -> (2,5) -> (1,3) -> (2,1) -> (3,3) -> (1,2) -> (2,4) -> (4,5) -> (5,3) -> (4,1) -> (2,2) -> (1,4) -> (3,5) -> (5,4) -> (4,2)
找到路线了：(1,1) -> (3,2) -> (5,1) -> (4,3) -> (5,5) -> (3,4) -> (1,5) -> (2,3) -> (3,1) -> (5,2) -> (4,4) -> (2,5) -> (1,3) -> (2,1) -> (4,2) -> (5,4) -> (3,3) -> (1,2) -> (2,4) -> (4,5) -> (5,3) -> (4,1) -> (2,2) -> (1,4) -> (3,5)
找到路线了：(1,1) -> (3,2) -> (5,1) -> (4,3) -> (5,5) -> (3,4) -> (1,5) -> (2,3) -> (3,1) -> (5,2) -> (4,4) -> (2,5) -> (1,3) -> (2,1) -> (4,2) -> (5,4) -> (3,5) -> (1,4) -> (2,2) -> (4,1) -> (5,3) -> (4,5) -> (3,3) -> (1,2) -> (2,4)
找到路线了：(1,1) -> (3,2) -> (5,1) -> (4,3) -> (5,5) -> (3,4) -> (1,5) -> (2,3) -> (3,1) -> (5,2) -> (4,4) -> (2,5) -> (1,3) -> (2,1) -> (4,2) -> (5,4) -> (3,5) -> (1,4) -> (2,2) -> (4,1) -> (5,3) -> (4,5) -> (2,4) -> (1,2) -> (3,3)
找到路线了：(1,1) -> (3,2) -> (5,1) -> (4,3) -> (5,5) -> (3,4) -> (1,5) -> (2,3) -> (3,1) -> (5,2) -> (4,4) -> (2,5) -> (1,3) -> (2,1) -> (4,2) -> (5,4) -> (3,5) -> (1,4) -> (3,3) -> (1,2) -> (2,4) -> (4,5) -> (5,3) -> (4,1) -> (2,2)
找到路线了：(1,1) -> (3,2) -> (5,1) -> (4,3) -> (5,5) -> (3,4) -> (1,5) -> (2,3) -> (3,1) -> (5,2) -> (4,4) -> (2,5) -> (3,3) -> (1,2) -> (2,4) -> (4,5) -> (5,3) -> (4,1) -> (2,2) -> (1,4) -> (3,5) -> (5,4) -> (4,2) -> (2,1) -> (1,3)

当然你也可以随意改变棋盘大小，运行第二个方法（比如马还是左上角，Position类的xPosMax = 3，yPosMax = 4），然后控制台输出两个周游方案（找完了，程序会打印 “寻找完毕”）：

找到路线了：(1,1) -> (2,3) -> (3,1) -> (1,2) -> (2,4) -> (3,2) -> (1,3) -> (2,1) -> (3,3) -> (1,4) -> (2,2) -> (3,4)
找到路线了：(1,1) -> (2,3) -> (3,1) -> (1,2) -> (2,4) -> (3,2) -> (1,3) -> (3,4) -> (2,2) -> (1,4) -> (3,3) -> (2,1)
寻找完毕

最后再说一句，本算法不一定绝对有解：如果棋盘是某些情况，比如3×3的棋盘，马在左上角，则你怎么都跳不到中间那个点位去，也就是你从(1,1)点位出发，在3×3的棋盘上永远也跳不到(2,2)的点位。同理第一个算法，3×3的棋盘就不存在左上角到中间的最短路径，因为距离是无穷大，也就是非连通图（第二个算法执行，马还是左上角，Position类的xPosMax = 3，yPosMax = 3）。改完Position参数后运行第二个方法，控制台输出：

寻找完毕

程序没有输出任何周游的路径图，表示程序在递归回溯的过程中没有找到符合条件的路径图，所以无解