在8x8的國際棋盤上，按照馬走日的規(guī)則，驗(yàn)證是否能夠走遍棋盤。

1、創(chuàng)建棋盤 chessBoard，是一個(gè)二維數(shù)組。

2、將當(dāng)前位置設(shè)置為已經(jīng)訪問，然后根據(jù)當(dāng)前位置，計(jì)算馬兒還能走哪些位置，并放入到一個(gè)集合中（ArrayList），最多有8個(gè)位置，每走一步，就使用step+1。

3、遍歷ArrayList中存放的所有位置，看看哪個(gè)可以走通，如果走通，就繼續(xù)，走不通，就回溯。

4、判斷馬兒是否完成了任務(wù)，使用step和應(yīng)該走的步數(shù)比較，如果沒有達(dá)到數(shù)量，則表示沒有完成任務(wù)，將整個(gè)棋盤置0。

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ù)//創(chuàng)建一個(gè)數(shù)組，標(biāo)記棋盤的各個(gè)位置是否被訪問過private static boolean visited[];//使用一個(gè)屬性，標(biāo)記是否棋盤的所有位置都被訪問private static boolean finished; // 如果為true,表示成功public static void main(String[] args) {System.out.println("騎士周游算法，開始運(yùn)行~~");//測試騎士周游算法是否正確X = 8;Y = 8;int row = 1; //馬兒初始位置的行，從1開始編號(hào)int column = 1; //馬兒初始位置的列，從1開始編號(hào)//創(chuàng)建棋盤int[][] chessboard = new int[X][Y];visited = new boolean[X * Y];//初始值都是false//測試一下耗時(shí)long start = System.currentTimeMillis();traversalChessboard(chessboard, row - 1, column - 1, 1);long end = System.currentTimeMillis();System.out.println("共耗時(shí): " + (end - start) + " 毫秒");//輸出棋盤的最后情況for(int[] rows : chessboard) {for(int step: rows) {System.out.print(step + "\t");}System.out.println();}}/*** 完成騎士周游問題的算法* @param chessboard 棋盤* @param row 馬兒當(dāng)前的位置的行 從0開始 * @param column 馬兒當(dāng)前的位置的列  從0開始* @param step 是第幾步 ,初始位置就是第1步 */public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {chessboard[row][column] = step;//row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36visited[row * X + column] = true; //標(biāo)記該位置已經(jīng)訪問//獲取當(dāng)前位置可以走的下一個(gè)位置的集合 ArrayList<Point> ps = next(new Point(column, row));//對(duì)ps進(jìn)行排序,排序的規(guī)則就是對(duì)ps的所有的Point對(duì)象的下一步的位置的數(shù)目，進(jìn)行非遞減排序sort(ps);//遍歷 pswhile(!ps.isEmpty()) {Point p = ps.remove(0);//取出下一個(gè)可以走的位置//判斷該點(diǎn)是否已經(jīng)訪問過if(!visited[p.y * X + p.x]) {//說明還沒有訪問過traversalChessboard(chessboard, p.y, p.x, step + 1);}}//判斷馬兒是否完成了任務(wù)，使用   step 和應(yīng)該走的步數(shù)比較 ， //如果沒有達(dá)到數(shù)量，則表示沒有完成任務(wù)，將整個(gè)棋盤置0//說明: step < X * Y  成立的情況有兩種//1. 棋盤到目前位置,仍然沒有走完//2. 棋盤處于一個(gè)回溯過程if(step < X * Y && !finished ) {chessboard[row][column] = 0;visited[row * X + column] = false;} else {finished = true;}}/*** 功能： 根據(jù)當(dāng)前位置(Point對(duì)象)，計(jì)算馬兒還能走哪些位置(Point)，并放入到一個(gè)集合中(ArrayList), 最多有8個(gè)位置* @param curPoint* @return*/public static ArrayList<Point> next(Point curPoint) {//創(chuàng)建一個(gè)ArrayListArrayList<Point> ps = new ArrayList<Point>();//創(chuàng)建一個(gè)PointPoint 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)行非遞減排序, 減少回溯的次數(shù)public static void sort(ArrayList<Point> ps) {ps.sort(new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {// TODO Auto-generated method stub//獲取到o1的下一步的所有位置個(gè)數(shù)int count1 = next(o1).size();//獲取到o2的下一步的所有位置個(gè)數(shù)int count2 = next(o2).size();if(count1 < count2) {return -1;} else if (count1 == count2) {return 0;} else {return 1;}}});}
}