如何使用java实现马踏棋盘

这篇文章将为大家详细讲解有关如何使用java实现马踏棋盘，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

具体内容如下

• 马踏棋盘算法也被称为骑士周游问题

• 将马随机放在过期象棋的8x8棋盘的某个方格中，马按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格

骑士周游问题结局步骤和思路

创建棋盘chessBoard，是一个二维数组
2.将当前位置设置为已个访问，然后根据当前位置，计算马儿还能走那些位置，并放到一个集合中(ArrayList)，最多8个位置
3.变量ArrayList存放的所有位置，看看哪个可以走通
4.判断马儿是否完成了骑士周游问题

注意：马儿不同的走法，会得到不同的结果，效率也会有影响

代码实现

public class HorseChessBoard {    private static int X;  //棋盘的列数    private static int Y;  //棋盘的行数        //创建数组标记棋盘各个位置是否被访问过    private static boolean[] visited;    //使用一个属性标记是否棋盘的所有位置都被访问过，即是否成功    private static boolean finish;  //如果为true表示成功        public static void main(String[] args) {        X = 8;        Y = 8;        int row = 1;        int col = 1;         int[][] chessboard =  new int[X][Y];        visited = new boolean[X * Y];                long start = System.currentTimeMillis();        traversalChessboard(chessboard, row-1, col-1, 1);        long end = System.currentTimeMillis();        System.out.println(end - start);                for (int[] rows : chessboard) {            for (int step : rows) {                System.out.print(step + "  ");            }            System.out.println();        }    }        //其实周游问题    public static void traversalChessboard(int[][] chessboard, int row, int col, int step) {                if (finish) return;        chessboard[row][col] = step;        visited[row * X + col] = true;  //标记该位置已经访问        //获取当前位置可以走的下一个位置的集合        List<Point> ps = next(new Point(col, row));        sort(ps);                //遍历ps        while (!ps.isEmpty()) {            Point p = ps.remove(0);  //取出下一个可以走的位置            //判断该点是否已经访问过            if (!visited[p.y * X + p.x]) {                traversalChessboard(chessboard, p.y, p.x, step+1);            }        }                //1. 棋盘到目前位置任然未走完        //2. 棋盘处于一个回溯过程        if (step < X * Y && !finish) {            chessboard[row][col] = 0;            visited[row * X + col] = false;        } else {            finish = true;        }    }        //根据当前这一步的所有的下一步的选择位置进行非递减排序    public static void sort(List<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 < count2) {                    return -1;                } else if (count1 == count2) {                    return 0;                } else {                    return 1;                }            }        });    }        //Point:根据当前位置(point对象)    //根据当前位置，计算马儿还能走那些位置，并放到一个集合中(ArrayList)，最多8个位置    public static List<Point> next(Point curPoint) {        //创建list集合        List<Point> ps = new ArrayList<>();        //创建一个point        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;    }}

关于“如何使用java实现马踏棋盘”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。