java实现马踏棋盘算法(骑士周游问题)

骑士周游问题

在8x8的国际棋盘上,按照马走日的规则,验证是否能够走遍棋盘。

解题思路

1、创建棋盘 chessBoard,是一个二维数组。
2、将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置,每走一步,就使用step+1。
3、遍历ArrayList中存放的所有位置,看看哪个可以走通,如果走通,就继续,走不通,就回溯。
4、判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置0。
5、注意:马儿不同的走法(策略),会得到不同的结果,效率也会有影响(优化)。

使用贪心算法优化

1、我们获取当前位置,可有走的下一个位置的集合
ArrayList 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的下一步的所有位置的个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
}

马踏棋盘算法代码实现

package com.horse;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessboard {
    private static int X;// 棋盘的列数
    private static int Y;// 棋盘的行数
    private static boolean visited[]; // 标记棋盘的位置是否被访问过
    private static boolean finished;// 标记棋盘的所有位置都被访问(是否成功)

    public static void main(String[] args) {
        // 测试骑士周游算法
        X = 8;
        Y = 8;
        int row = 1;// 马儿的初始位置行
        int column = 1;// 马儿初始位置列
        // 创建棋盘
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];
        // 测试一下耗时
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("耗时" + (end - start) + "ms");
        // 输出棋盘最后情况
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.printf("%4d", step);
            }
            System.out.println();
        }

    }

    /**
     * @Method_Name:traversalChessboard
     * @Description: 完成骑士周游问题多的算法
     * @param chessboard
     *            棋盘
     * @param row
     *            马儿当前位置的行 从0开始
     * @param column
     *            马儿当前位置的列 从0开始
     * @param step
     *            void 是第几步,初始位置是第1步
     */
    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);
        // 遍历ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);// 取出下一个可以走的位置
            // 判断是否访问过
            if (!visited[p.y * X + p.x]) {// 说明还没有访问过
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }
        // 判断是否完成
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    /**
     * @Method_Name:next
     * @Description: 计算马儿还能走哪些位置,并放入到一个集合中(ArrayList)
     * @param curPoint
     * @return ArrayList<Point>
     */
    public static ArrayList<Point> next(Point curPoint) {
        // 创建有一个ArrayList
        ArrayList<Point> ps = new ArrayList<Point>();
        // 创建Point
        Point p1 = new Point();
        // 判断马儿可以走5这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走6这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走7这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走0这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走1这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走2这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走3这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        // 判断马儿可以走4这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }
    // 根据当前这个一步的所有的下一步的选择位置,进行非递减排序
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {

            @Override
            public int compare(Point o1, Point o2) {
                // 获取o1的下一步的所有位置的个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Java基于分治算法实现的棋盘覆盖问题示例

    本文实例讲述了Java基于分治算法实现的棋盘覆盖问题.分享给大家供大家参考,具体如下: 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖.四个L型骨牌如下图: 棋盘中的特殊方格如图: 实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不

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

    马踏棋盘或骑士周游问题 1.马踏棋盘算法也被称为骑士周游问题2.将马随机放在国际象棋的 8×8 棋盘 Board[0-7][0-7]的某个方格中,马按走棋规则(马走日字)进行移动.要求每个方格只进入一次,走遍棋盘上全部 64 个方格 思路 会使用到深度优先思想和类似迷宫问题的寻路策略问题,和八皇后问题也有相似. 1.用一个二维数组建立整张棋盘.用另外一个二维数组保存棋盘的每一个位置是否走过2.马在棋盘上有一个初始位置,将这个位置设为已走过,并将步数设为1.3.获得在这个位置上,马下一步能走的位置

  • java数据结构和算法之马踏棋盘算法

    本文实例为大家分享了java实现算法之马踏棋盘的具体代码,供大家参考,具体内容如下 一.马踏棋盘算法介绍 马踏棋盘算法也被称为骑士周游问题将马随机放在国际象棋的8×8棋盘Board[0-7][0-7]的某个方格中,马按走棋规则(马走日字)进行移动.要求每个方格只进入一次,走遍棋盘上全部64个方格 二.骑士周游问题的思路分析 1.创建棋盘 chessBoard , 是一个二维数组2.将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList), 最多

  • java实现马踏棋盘游戏

    用java实现马踏棋盘游戏算法,供大家参考,具体内容如下 在4399小游戏中有这样一个游戏 这是代码实现 package com.HorseChess; import java.awt.*; import java.util.ArrayList; import java.util.Comparator; import java.util.Scanner; public class HorseChess {     private static int X;     private static

  • java数据结构与算法之马踏棋盘

    本文实例为大家分享了java数据结构与算法之马踏棋盘的具体代码,供大家参考,具体内容如下 马踏棋盘算法也被称为骑士周游问题 将马随机放在过期象棋的8x8棋盘的某个方格中,马按走棋规则进行移动,要求每个方格只进入一次,走遍棋盘上全部64个方格 骑士周游问题结局步骤和思路 1.创建棋盘chessBoard,是一个二维数组2.将当前位置设置为已个访问,然后根据当前位置,计算马儿还能走那些位置,并放到一个集合中(ArrayList),最多8个位置3.变量ArrayList存放的所有位置,看看哪个可以走通

  • java实现马踏棋盘的完整版

    本文实例为大家分享了java实现马踏棋盘的具体代码,供大家参考,具体内容如下 马踏棋盘很好实现,但有时运行起来特别慢,还可能出不来结果,在这里要用到贪心算法来优化,即找出最难走的路径,也就是下下步可下棋的位置最少. 下面给出该算法完整代码: /*      * 马踏棋盘问题:(贪婪法求解)      * 棋盘有64个位置,"日"字走法,刚好走满整个棋盘      */     //下一个走法的方向类     class Direction{         int x;        

  • Java实现马踏棋盘算法

    本文实例为大家分享了Java实现马踏棋盘的具体代码,供大家参考,具体内容如下 马在某个点最多可能有8种走法,用递归和回溯实现. 注:代码中,查找下一个可走坐标是从右下第一个开始的,也就是图中的4.可以通过修改a,b...h的值来改变顺序. 代码: /**  * 马踏棋盘算法   * 递归和回溯  *  */ public class HorseStep {          public static int X = 8;     public static int Y = 8;        

  • 基于Java实现马踏棋盘游戏算法

    马踏棋盘很好实现,但有时运行起来特别慢,还可能出不来结果,最常用的就是深度优先遍历+回溯,相信大家都学过数据结构,对图的深度遍历都有了解,下面就是代码的实现,如果对代码理解有困难,可以先熟悉一下图的深度优先遍历 大家可以把棋盘改小一些测试,8x8的确实很慢 import java.util.Arrays; /**  * 骑士周游问题  * @author LM_Code  * @create 2019-03-17-18:57  */ public class KnightProblem {  

  • Java实现两人五子棋游戏(二) 画出棋盘

    本文为大家分享了java画出五子棋游戏棋盘的方法,供大家参考,具体内容如下 棋盘模块: 画五子棋棋盘:19条横线.19条竖线 步骤一:显示棋盘 我有一张名为chessboard.png的棋盘,位置为根目录/res/drawable/chessboard/png,现在我要显示这张图片. DrawChessBoard.java package xchen.test.simpleGobang; import java.awt.Graphics; import java.awt.Image; impor

  • java实现马踏棋盘的算法

    本文实例为大家分享了java实现马踏棋盘的具体代码,供大家参考,具体内容如下 马踏棋盘算法介绍 8X8棋盘,马走日字,要求每个方格只进入一次,走遍棋盘上全部64个方格. 代码: public class HorseChessBoard {     private static int X;//棋盘的列数     private static int Y;//棋盘的行数     //创建一个数组,标记棋盘的各个位置是否被访问过     private static boolean visited[

随机推荐