马踏棋盘算法（使用贪心算法优化）（Java）

马踏棋盘介绍

马踏棋盘问题是旅行商问题（TSP）或哈密顿回路问题（HCP）的一个特例。在 8×8 的国际象棋棋盘上，用一个马按照马步跳遍整个棋盘，要求每个格子都只跳到一次，最后回到出发点。这是一个 NP问题，通常采用回溯法或启发式搜索类算法求解。在 9×10 的中国象棋棋盘上也可以实现马步遍历。

代码实现：

编写一个马的类：

package com.athome.horse;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/19 20:10
 */
public class Horse {
    int x;//表示行
    int y;//表示列
    int[][] checkerboard;//表示棋盘
    boolean[][] passed;//记录是否走过
    boolean finished;

    public Horse(int x, int y) {
        this.x = x;
        this.y = y;
        checkerboard = new int[this.x][this.y];
        passed = new boolean[this.x][this.y];
    }

    /**
     * 获取所有下一步的集合
     *
     * @param curLocation 当前位置
     * @return 返回由下一个可行位置构成的集合
     */
    public List<Lattice> getNext(Lattice curLocation) {
        List<Lattice> list = new ArrayList<>();
        //存放可以走的坐标
        int x;
        int y;
        //判断1，2号位置是否能走
        if ((x = curLocation.x - 1) >= 0 && (y = curLocation.y - 2) >= 0) {
            list.add(new Lattice(x, y));
        }
        if ((x = curLocation.x - 2) >= 0 && (y = curLocation.y - 1) >= 0) {
            list.add(new Lattice(x, y));
        }
        //判断3，4号位置是否能走
        if ((x = curLocation.x - 2) >= 0 && (y = curLocation.y + 1) < this.y) {
            list.add(new Lattice(x, y));
        }
        if ((x = curLocation.x - 1) >= 0 && (y = curLocation.y + 2) < this.y) {
            list.add(new Lattice(x, y));
        }
        //判断5，6号位置受否能走
        if ((x = curLocation.x + 1) < this.x && (y = curLocation.y + 2) < this.y) {
            list.add(new Lattice(x, y));
        }
        if ((x = curLocation.x + 2) < this.x && (y = curLocation.y + 1) < this.y) {
            list.add(new Lattice(x, y));
        }
        //判断7，8号位置是否能走
        if ((x = curLocation.x + 2) < this.x && (y = curLocation.y - 1) >= 0) {
            list.add(new Lattice(x, y));
        }
        if ((x = curLocation.x + 1) < this.x && (y = curLocation.y - 2) >= 0) {
            list.add(new Lattice(x, y));
        }
        return list;
    }

    /**
     * 马踏棋盘算法，（使用贪心算法优化后）
     *
     * @param x    表示行
     * @param y    表示列
     * @param step 表示步数
     */
    private void horseRun(int x, int y, int step) {
        checkerboard[x][y] = step;
        passed[x][y] = true;
        //得到下一步可走的格子集合
        List<Lattice> lattices = getNext(new Lattice(x, y));
        sort(lattices);
        while (!lattices.isEmpty()) {
            Lattice next = lattices.remove(0);
            if (!passed[next.x][next.y]) {
                horseRun(next.x, next.y, step + 1);
            }
        }
        if (step < this.x * this.y && !finished) {
            checkerboard[x][y] = 0;
            passed[x][y] = false;
        } else {
            finished = true;
        }
    }

    /**
     * 重载horseRun方法
     *
     * @param x 行
     * @param y 列
     */
    public void horseRun(int x, int y) {
        System.out.println("马踏棋盘开始计算,请稍等......");
        int step = 1;
        horseRun(x - 1, y - 1, step);
    }

    /**
     * 展示
     */
    public void show() {
        for (int[] ints : checkerboard) {
            for (int i : ints) {
                System.out.print(i + "t");
            }
            System.out.println();
        }
    }

    /**
     * 定制排序，体现贪心算法
     *
     * @param list 封装下一个节点的集合
     */
    public void sort(List<Lattice> list) {
        list.sort(new Comparator<Lattice>() {
            @Override
            public int compare(Lattice o1, Lattice o2) {
                List<Lattice> next1 = getNext(o1);
                List<Lattice> next2 = getNext(o2);
                return next1.size() - next2.size();
            }
        });
    }
}

编写表示格子的类：

package com.athome.horse;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/19 20:08
 */
public class Lattice {
    int x;//表示行
    int y;//表示列

    public Lattice(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Lattice{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

主方法中测试：

package com.athome.horse;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/19 19:54
 */
public class Checkerboard {
    public static void main(String[] args) {
        Horse horse = new Horse(8, 8);
        long start = System.currentTimeMillis();
        horse.horseRun(4, 4);
        long end = System.currentTimeMillis();
        horse.show();
        System.out.println("本次计算耗时: " + (end - start) + "毫秒");
    }
}

结语

只要能收获甜蜜，荆棘丛中也有蜜蜂忙碌的身影，未来的你一定会感谢现在努力的自己。