/**
?* 馬踏棋盤算法?
?* 遞歸和回溯
?*
?*/
public class HorseStep {
?? ?
?? ?public static int X = 8;
?? ?public static int Y = 8;
?? ?
?? ?public static int returnCount = 0;
?? ?
?? ?/**
?? ? * 棋盤
?? ? */
?? ?public static int chess[][] = new int[X][Y];
?? ?
?? ?
?? ?/**
?? ? * 找到基于（x,y）位置的下一個可走位置
?? ? * @param x
?? ? * @param y
?? ? * @param count
?? ? * @return
?? ? */
?? ?public static int nextxy(XY xy,int count){
?? ??? ?
?? ??? ?final int a=0,
?? ??? ??? ??? ?b=1,
?? ??? ??? ??? ?c=2,
?? ??? ??? ??? ?d=3,
?? ??? ??? ??? ?e=4,
?? ??? ??? ??? ?f=5,
?? ??? ??? ??? ?g=6,
?? ??? ??? ??? ?h=7;
?? ??? ?
?? ??? ?int x = xy.getX();
?? ??? ?int y = xy.getY();
?? ??? ?
?? ??? ?int returnInt = 0;
?? ??? ?
?? ??? ?switch (count) {
?? ??? ?
//?? ??? ?從以x,y為軸心的 右下 開始
?? ??? ?
?? ??? ?case a:
?? ??? ??? ?if( x+2<=X-1 && y+1<=Y-1 && chess[y+1][x+2]==0){
?? ??? ??? ??? ?x +=2;
?? ??? ??? ??? ?y +=1;
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?break;
?? ??? ??? ?
?? ??? ?case b:
?? ??? ??? ?if( x+1<=X-1 && y+2<=Y-1 && chess[y+2][x+1]==0){
?? ??? ??? ??? ?x +=1;
?? ??? ??? ??? ?y +=2;
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?break;
?? ??? ??? ?
?? ??? ?case c:
?? ??? ??? ?if( x-1>=0 && y+2<=Y-1 && chess[y+2][x-1]==0){
?? ??? ??? ??? ?x -=1;
?? ??? ??? ??? ?y +=2;
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?break;
?? ??? ??? ?
?? ??? ?case d:
?? ??? ??? ?if( x-2>=0 && y+1<=Y-1 && chess[y+1][x-2]==0){
?? ??? ??? ??? ?x -=2;
?? ??? ??? ??? ?y +=1;
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?break;
?? ??? ?
?? ??? ?case e:
?? ??? ??? ?if( x-2>=0 && y-1>=0 && chess[y-1][x-2]==0){
?? ??? ??? ??? ?x -=2;
?? ??? ??? ??? ?y -=1;
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?break;
?? ??? ??? ?
?? ??? ?case f:
?? ??? ??? ?if( x-1>=0 && y-2>=0 && chess[y-2][x-1]==0){
?? ??? ??? ??? ?x -=1;
?? ??? ??? ??? ?y -=2;
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?break;
?? ??? ??? ?
?? ??? ?case g:
?? ??? ??? ?if( x+1<=X-1 && y-2>=0 && chess[y-2][x+1]==0){
?? ??? ??? ??? ?x +=1;
?? ??? ??? ??? ?y -=2;
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?break;
?? ??? ??? ?
?? ??? ?case h:
?? ??? ??? ?if( x+2<=X-1 && y-1>=0 && chess[y-1][x+2]==0){
?? ??? ??? ??? ?x +=2;
?? ??? ??? ??? ?y -=1;
?? ??? ??? ??? ?
?? ??? ??? ??? ?returnInt = 1;
?? ??? ??? ?}
?? ??? ??? ?break;
?? ??? ??? ?
?? ??? ?default:
?? ??? ??? ?break;
?? ??? ?}
?? ??? ?
?? ??? ?if(returnInt == 1){
?? ??? ??? ?xy.setX(x);
?? ??? ??? ?xy.setY(y);
?? ??? ??? ?
?? ??? ??? ?return 1;
?? ??? ?}
?
?? ??? ?return 0;
?? ?}
?? ?
?? ?/**
?? ? * 打印棋盤
?? ? */
?? ?public static void print(){
?? ??? ?for(int i=0;i<X;i++){
?? ??? ??? ?for(int j=0;j<Y;j++){
?? ??? ??? ??? ?
?? ??? ??? ??? ?if(chess[i][j]<10)
?? ??? ??? ??? ??? ?System.out.print(chess[i][j]+" ?");
?? ??? ??? ??? ?else
?? ??? ??? ??? ??? ?System.out.print(chess[i][j]+" ");
?? ??? ??? ??? ?
?? ??? ??? ?}
?? ??? ??? ?System.out.println();
?? ??? ?}
?? ??? ?
?? ?}
?? ?
?? ?/**
?? ? * 深度優(yōu)先遍歷棋盤
?? ? * @param x
?? ? * @param y
?? ? * @param tag
?? ? * @return
?? ? * （x,y)為位置坐標
?? ? * tag是標記變量，每走一步 tag+1。
?? ? */
?? ?public static int TravelChessBoard(XY xy,int tag){
?? ??? ?
//?? ??? ?馬在某個點有八種可能的方向，用來約束查找小于八種的變量
?? ??? ?Integer count = 0;
?? ??? ?
//?? ??? ?馬所在位置是否可以再跳向下一個位置，0有，1無（條件：1，不出邊界，2.沒有走過）
?? ??? ?int haveNextXy = 0;
?? ??? ?
?? ??? ?int x = xy.getX();
?? ??? ?int y = xy.getY();
?? ??? ?
//?? ??? ?x是橫軸，y是豎軸，左上角為0,0點，往右和往下遞增
?? ??? ?chess[y][x] = tag;
?? ??? ?
//?? ??? ?最后一步，遞歸的終止條件
?? ??? ?if(X*Y == tag){
//?? ??? ??? ?打印棋盤
?? ??? ??? ?print();
?? ??? ??? ?return 1;
?? ??? ?}
?? ??? ?
//?? ??? ?找到馬的下一個可走坐標（x1,y1)，如果找到為1，否則為0.
?? ??? ?haveNextXy = nextxy(xy, count);
?? ??? ?
?? ??? ?while( 0==haveNextXy && count<7){
?? ??? ??? ?count ++;
?? ??? ??? ?haveNextXy = nextxy(xy, count);
?? ??? ?}
?? ??? ?
?? ??? ?while(haveNextXy==1){
?? ??? ??? ?if(TravelChessBoard(xy, tag+1)==1){
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?
//?? ??? ??? ?回退后，把當前點也設置為回退后的位置
?? ??? ??? ?xy.setX(x);
?? ??? ??? ?xy.setY(y);
?? ??? ??? ?
?? ??? ??? ?count++;
?? ??? ??? ?
//?? ??? ??? ?找到馬的下一個可走坐標（x1,y1)，如果找到flag=1，否則為0.
?? ??? ??? ?haveNextXy = nextxy(xy, count);
?? ??? ??? ?
?? ??? ??? ?while( 0==haveNextXy && count<7){
?? ??? ??? ??? ?count ++;
?? ??? ??? ??? ?haveNextXy = nextxy(xy, count);
?? ??? ??? ?}
?? ??? ?}
?? ??? ?
//?? ??? ?回退
?? ??? ?if(haveNextXy==0){
?? ??? ??? ?chess[y][x]=0;
?? ??? ??? ?returnCount++;
?? ??? ?}
?? ??? ?
?? ??? ?return 0 ;
?? ?}
?? ?
?? ?public static void main(String[] args) {
?? ??? ?long begin = System.currentTimeMillis();
?? ??? ?
//?? ??? ?馬所在位置的坐標，x是橫軸，y是豎軸，左上角為0,0點，往右和往下遞增
?? ??? ?XY xy = new XY();
?? ??? ?xy.setX(1);
?? ??? ?xy.setY(0);
?? ??? ?
?? ??? ?if(TravelChessBoard(xy, 1)==0){
?? ??? ??? ?System.out.println("馬踏棋盤失敗");
?? ??? ?}
?? ??? ?
?? ??? ?long time = System.currentTimeMillis()-begin;
?? ??? ?
?? ??? ?System.out.println("耗時"+time+"毫秒");
?? ??? ?System.out.println(returnCount);
?? ?}
?? ?
}
?
?
class XY{
?? ?private int x;
?? ?private int y;
?? ?public int getX() {
?? ??? ?return x;
?? ?}
?? ?public void setX(int x) {
?? ??? ?this.x = x;
?? ?}
?? ?public int getY() {
?? ??? ?return y;
?? ?}
?? ?public void setY(int y) {
?? ??? ?this.y = y;
?? ?}
?? ?
?? ?
}