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

/**
 * @author 执笔
 * @version 1.0
 */
public class HorseChessBoard {

    private static int X  = 6;//表示col
    private static int Y  = 6;//表示row
    private static int[][] chessBoard = new int[Y][X];//棋盘大小
    private static boolean[] visited = new boolean[X * Y];//记录某个位置是否走过
    private static boolean finished = false;//是否完成遍历棋盘


    public static void main(String[] args) {

        int row = 5;
        int col = 5;
        //测试
        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) {//step 表示应该走的第几步
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    //对ps的各个位置 可以走的下一个位置的次数进行排序 把可能走的下一个位置从小到大排序
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size() - next(o2).size();
            }
        });
    }

    //最核心的算法 遍历棋盘 如果遍历成功 就把 finished设置为true
    //并将走的每一步step 记录到chessBoard
    public static void traversalChessBoard(int[][] chessBoard, int row, int col, int step) {

        //先把step 记录到 chessBoard
        chessBoard[row][col] = step;
        //把这个位置 设置为已经访问
        visited[row * X + col] = true;
        //获取当前位置可以走的下一个位置有哪些
        ArrayList<Point> ps = next(new Point(col, row));// col --> X, row --> Y
        //排序
        sort(ps);
        //遍历
        while(!ps.isEmpty()) {
            //取出当前ps的第一个位置(点)
            Point p = ps.remove(0);
            //判断该位置是否走过 如果没有走过就递归遍历
            if(!visited[p.y * X + p.x]) {
                //递归遍历
                traversalChessBoard(chessBoard, p.y, p.x, step + 1);
            }
        }
        //当退出while循环后 是否遍历成功， 如果没有成功就重置相应的值 然后进行回溯
        if (step < X * Y && !finished) {
            //重置
            chessBoard[row][col] = 0;
            visited[row * X + col] = false;
        } else {
            finished = true;
        }
    }

    //编写方法，可以获取当前位置 可以走的下一步的所有位置(Point表示 x,y)
    public static ArrayList<Point> next(Point curPoint) {// curPoint 当前位置点

        //创建一个ArrayList
        ArrayList<Point> ps = new ArrayList<>();

        //创建一个 Point对象(点/位置) 准备放入到 ps中
        Point p = new Point();

        //判断在该位置 能否走如下位置 如果可以就将该点(Point) 放入到ps
        //判断5点的位置
        if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        //判断6点的位置
        if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        //判断7点的位置
        if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        //判断0点的位置
        if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        //判断1点的位置
        if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        //判断2点的位置
        if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        //判断3点的位置
        if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        //判断4点的位置
        if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p));//这里需要新建一个点 不然会被覆盖
        }
        return ps;
    }
}