public static void sort(ArrayList<Point> ps) {
?? ??? ?ps.sort(new Comparator<Point>() {
?? ??? ??? ?@Override
?? ??? ??? ?public int compare(Point o1, Point o2) {
?? ??? ??? ??? ?// 獲取o1的下一步的所有位置的個(gè)數(shù)
?? ??? ??? ??? ?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;// 棋盤的列數(shù)
?? ?private static int Y;// 棋盤的行數(shù)
?? ?private static boolean visited[]; // 標(biāo)記棋盤的位置是否被訪問(wèn)過(guò)
?? ?private static boolean finished;// 標(biāo)記棋盤的所有位置都被訪問(wèn)（是否成功）

?? ?public static void main(String[] args) {
?? ??? ?// 測(cè)試騎士周游算法
?? ??? ?X = 8;
?? ??? ?Y = 8;
?? ??? ?int row = 1;// 馬兒的初始位置行
?? ??? ?int column = 1;// 馬兒初始位置列
?? ??? ?// 創(chuàng)建棋盤
?? ??? ?int[][] chessboard = new int[X][Y];
?? ??? ?visited = new boolean[X * Y];
?? ??? ?// 測(cè)試一下耗時(shí)
?? ??? ?long start = System.currentTimeMillis();
?? ??? ?traversalChessboard(chessboard, row - 1, column - 1, 1);
?? ??? ?long end = System.currentTimeMillis();
?? ??? ?System.out.println("耗時(shí)" + (end - start) + "ms");
?? ??? ?// 輸出棋盤最后情況
?? ??? ?for (int[] rows : chessboard) {
?? ??? ??? ?for (int step : rows) {
?? ??? ??? ??? ?System.out.printf("%4d", step);
?? ??? ??? ?}
?? ??? ??? ?System.out.println();
?? ??? ?}

?? ?}

?? ?/**
?? ? * @Method_Name:traversalChessboard
?? ? * @Description: 完成騎士周游問(wèn)題多的算法
?? ? * @param chessboard
?? ? * ? ? ? ? ? ?棋盤
?? ? * @param row
?? ? * ? ? ? ? ? ?馬兒當(dāng)前位置的行 從0開始
?? ? * @param column
?? ? * ? ? ? ? ? ?馬兒當(dāng)前位置的列 從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;// 標(biāo)記該位置已訪問(wèn)
?? ??? ?// 獲取當(dāng)前位置可以走的下一步
?? ??? ?ArrayList<Point> ps = next(new Point(column, row));
?? ??? ?// 對(duì)ps進(jìn)行非遞減排序，
?? ??? ?sort(ps);
?? ??? ?// 遍歷ps
?? ??? ?while (!ps.isEmpty()) {
?? ??? ??? ?Point p = ps.remove(0);// 取出下一個(gè)可以走的位置
?? ??? ??? ?// 判斷是否訪問(wèn)過(guò)
?? ??? ??? ?if (!visited[p.y * X + p.x]) {// 說(shuō)明還沒有訪問(wèn)過(guò)
?? ??? ??? ??? ?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: 計(jì)算馬兒還能走哪些位置，并放入到一個(gè)集合中（ArrayList）
?? ? * @param curPoint
?? ? * @return ArrayList<Point>
?? ? */
?? ?public static ArrayList<Point> next(Point curPoint) {
?? ??? ?// 創(chuàng)建有一個(gè)ArrayList
?? ??? ?ArrayList<Point> ps = new ArrayList<Point>();
?? ??? ?// 創(chuàng)建Point
?? ??? ?Point p1 = new Point();
?? ??? ?// 判斷馬兒可以走5這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走6這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走7這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走0這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走1這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走2這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走3這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?// 判斷馬兒可以走4這個(gè)位置
?? ??? ?if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
?? ??? ??? ?ps.add(new Point(p1));
?? ??? ?}
?? ??? ?return ps;
?? ?}
?? ?// 根據(jù)當(dāng)前這個(gè)一步的所有的下一步的選擇位置，進(jìn)行非遞減排序
?? ?public static void sort(ArrayList<Point> ps) {
?? ??? ?ps.sort(new Comparator<Point>() {

?? ??? ??? ?@Override
?? ??? ??? ?public int compare(Point o1, Point o2) {
?? ??? ??? ??? ?// 獲取o1的下一步的所有位置的個(gè)數(shù)
?? ??? ??? ??? ?int count1 = next(o1).size();
?? ??? ??? ??? ?int count2 = next(o2).size();
?? ??? ??? ??? ?if (count1 < count2) {
?? ??? ??? ??? ??? ?return -1;
?? ??? ??? ??? ?} else if (count1 == count2) {
?? ??? ??? ??? ??? ?return 0;
?? ??? ??? ??? ?} else {
?? ??? ??? ??? ??? ?return 1;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?});
?? ?}
}