java学习笔记之马踏棋盘算法

马踏棋盘或骑士周游问题

1、马踏棋盘算法也被称为骑士周游问题
2、将马随机放在国际象棋的 8×8 棋盘 Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格

思路

会使用到深度优先思想和类似迷宫问题的寻路策略问题，和八皇后问题也有相似。

1、用一个二维数组建立整张棋盘。用另外一个二维数组保存棋盘的每一个位置是否走过
2、马在棋盘上有一个初始位置，将这个位置设为已走过，并将步数设为1.
3、获得在这个位置上，马下一步能走的位置集合。
4、遍历集合里的所有位置，如果那个位置没走过，下一步（步数+1）就走它（递归）
5、设置递归结束的标志.用一个布尔变量标志游戏是否成功。当游戏成功时，步数应该等于棋盘格子数。假如某一次，马走完了所有能走的下一步位置，步数还小于棋盘格子数并且还没成功，说明这个位置不能成功的完成游戏，就把这个位置恢复原样（棋盘设为0，设为未走过），接下来的递归会重新去寻找合适的路。如果步数等于棋盘总格子数，说明游戏成功，把标志的布尔变量设为true，这样在层层返回时就不会再进入上面的条件，递归就会逐渐结束而不会深入下去。

涉及到的方法：

根据此时的位置，判断马接下来能走的位置集合。
x的值代表列而y的值代表行
马是按照日字走的，所有当它在中间时最多有8种位置可以走，一 一判断那个位置是否超过棋盘边界。
每种可能都是if，而不是if-else if，因为要获得所有的可能性，而不是找出一个
假如list时一定要新建一个坐标，不能使用同一个，不然值就会互相影响

/**
     * 根据现在的坐标返回可以走的坐标 x列y行
     *
     * @param current
     * @return
     */
    public static ArrayList<Point> findWay(Point current) {
        ArrayList<Point> res = new ArrayList<>();
        //可以走的坐标
        Point p = new Point();
        //5
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //6
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //7
        if ((p.x = current.x + 1) < X && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //0
        if ((p.x = current.x + 2) < X && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //1
        if ((p.x = current.x + 2) < X && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        //2
        if ((p.x = current.x + 1) < X && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //3
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //4
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        return res;
    }

马塔棋盘

不能单纯以step < X * Y来判断是否完成游戏，因为递归回溯时步数也会回溯，所以要设置一个变量

 /**
     * 马踏棋盘算法
     *
     * @param chess 棋盘
     * @param row   坐标行
     * @param col   坐标列
     * @param step  步数
     */
    public static void traversalChessboard(int[][] chess, int row, int col, int step) {
        //先走一步
        chess[row][col] = step;
        visit[row][col] = true;
        //下一步能走的地
        ArrayList<Point> way = findWay(new Point(col, row));
        while (!way.isEmpty()) {
            //取出一个能走的地方
            Point point = way.remove(0);
            //走下一步
            if (!visit[point.y][point.x]) {
                traversalChessboard(chess, point.y, point.x, step + 1);
            }

        }
        //判断是否完成游戏，如果没完成就要回溯
        if (step < X * Y && !finshed) {
            chess[row][col] = 0;
            visit[row][col] = false;
        }else {
            finshed=true;
        }
    }

优化

这样计算效率比较低，算法比较慢。实际上当我们获得下一步可以走的位置数组时是按照固定的56701234顺序排列的，但是这样效率不高，我们在考虑到走下一步时，应该先走对应下一步的可能性最少的那一步，比如如果7的下一步有3种可能，而5的下一步有6种可能，那先7后5的效率会更高。

所以我们可以使用贪心算法对获得的这个步数集合根据他们下一步的可能性进行由小到大的排序。

/**
     * 贪心算法优化
     * @param ps
     */
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int way1 = findWay(o1).size();
                int way2 = findWay(o2).size();
                if(way1<way2){
                    return -1;
                }else if(way1==way2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
}

对Comparetor.compare(o1, o2)方法的返回值，如果返回的值小于零，则不交换两个o1和o2的位置；如果返回的值大于零，则交换o1和o2的位置。 注意，不论在compare(o1, o2)中是如何实现的（第一种实现方式是 o1-02, 第二种实现方式是 o2 - o1），都遵循上述原则，即返回值小于零，则交换o1和o2的位置；返回值大于零，则不交换o1和o2的位置。 所以，如果采用第一种实现方式，即 o1 - o2, 那么将是升序排序。因为在原始排序中o1在o2的前边，如果o1小于o2，那么o1 - o2小于零，即返回值是小于零，但是小于零是不会交换o1和o2的位置的，所以o1依然排在o2的前边，是升序；如果o1大于o2，那么o1 - o2大于零，即返回值是大于零，大于零是要交换o1和o2的位置的，所以要改变原始排序中o1和o2的位置，那么依然是升序

最终代码

package algorithm;

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

/**
 * 马踏棋盘算法
 */
public class HorseChessboard {
    static int X;//列
    static int Y;//行
    static boolean[][] visit;
    static boolean finshed;

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        visit = new boolean[X][Y];
        finshed = false;
        int[][] chess = new int[X][Y];
        long s = System.currentTimeMillis();

        traversalChessboard(chess, 2, 0, 1);
        long e=System.currentTimeMillis();
        System.out.println(e-s);

        for (int i = 0; i < chess.length; i++) {
            System.out.println(Arrays.toString(chess[i]));
        }

    }

    /**
     * 马踏棋盘算法
     *
     * @param chess 棋盘
     * @param row   坐标行
     * @param col   坐标列
     * @param step  步数
     */
    public static void traversalChessboard(int[][] chess, int row, int col, int step) {
        //先走一步
        chess[row][col] = step;
        visit[row][col] = true;
        //下一步能走的地
        ArrayList<Point> way = findWay(new Point(col, row));
        sort(way);
        while (!way.isEmpty()) {
            //取出一个能走的地方
            Point point = way.remove(0);
            //走下一步
            if (!visit[point.y][point.x]) {
                traversalChessboard(chess, point.y, point.x, step + 1);
            }

        }
        if (step < X * Y && !finshed) {
            chess[row][col] = 0;
            visit[row][col] = false;
        }else {
            finshed=true;
        }
    }

    /**
     * 根据现在的坐标返回可以走的坐标 x列y行
     *
     * @param current
     * @return
     */
    public static ArrayList<Point> findWay(Point current) {
        ArrayList<Point> res = new ArrayList<>();
        //可以走的坐标
        Point p = new Point();
        //5
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //6
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //7
        if ((p.x = current.x + 1) < X && (p.y = current.y - 2) >= 0) {
            res.add(new Point(p));
        }
        //0
        if ((p.x = current.x + 2) < X && (p.y = current.y - 1) >= 0) {
            res.add(new Point(p));
        }
        //1
        if ((p.x = current.x + 2) < X && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        //2
        if ((p.x = current.x + 1) < X && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //3
        if ((p.x = current.x - 1) >= 0 && (p.y = current.y + 2) < Y) {
            res.add(new Point(p));
        }
        //4
        if ((p.x = current.x - 2) >= 0 && (p.y = current.y + 1) < Y) {
            res.add(new Point(p));
        }
        return res;
    }

    /**
     * 贪心算法优化
     * @param ps
     */
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int way1 = findWay(o1).size();
                int way2 = findWay(o2).size();
                if(way1<way2){
                    return -1;
                }else if(way1==way2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持猪先飞。