骑士周游问题

骑士周游问题

1)马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。

2)如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了53个点，如图：走到了第53个，坐标（1,0），发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回溯…… ，思路分析+代码实现

3)分析第一种方式的问题，并使用贪心算法（greedyalgorithm）进行优化。解决马踏棋盘问题.

4)使用前面的游戏来验证算法是否正确。

package horse;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.awt.*;
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;//马儿初始位置的行,从1开始编号
        int column=1;
        //创建棋盘
        int [][]chessboard=new int[X][Y];
        visited=new boolean[X*Y];//初始值都是false

        long start = System.currentTimeMillis();
        traversalChessboard(chessboard,row-1,column-1,1);
        long end=System.currentTimeMillis();
        System.out.println("共耗时："+(end-start)+"毫秒");

        //输出棋盘的最后情况
        for(int[]rows:chessboard){
            for(int step:rows){
                System.out.print(step+"\t");
            }
            System.out.println();
        }

    }

    /**
     * 完成骑士周游问题的算法
     * @param chessboard 棋盘
     * @param row 马儿当前位置的行 从0开始
     * @param column 当前位置的列 从0开始
     * @param step 是第几步，初始位置是第一步
     */
    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进行排序，排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
        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);
            }
        }
        //判断是否完成了任务，是哟了那个 step 和应该走的步数比较
        //如果没有达到数量，则表示没有完成任务，将整个棋盘置0
        if(step<X*Y&&!finished){
            chessboard[row][column]=0;
            visited[row*X+column]=false;
        }else {
            finished=true;
        }

    }

    /**
     * @param curPoint 根据当前的位置，计算马儿还能走哪些位置，并放入到一个集合中，最多有8个位置
     * @return
     */
    public static ArrayList<Point> next(Point curPoint) {

        ArrayList<Point> ps = new ArrayList<>();

        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();
                return Integer.compare(count1, count2);
            }
        });
    }


}