public class HorseChessBoard {

?? ?private static int X; ?//棋盤的列數
?? ?private static int Y; ?//棋盤的行數
?? ?
?? ?//創(chuàng)建數組標記棋盤各個位置是否被訪問過
?? ?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) {
?? ??? ?//創(chuàng)建list集合
?? ??? ?List<Point> ps = new ArrayList<>();
?? ??? ?//創(chuàng)建一個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;
?? ?}

}