Java實現馬踏棋盤算法

/**
 * 馬踏棋盤算法 
 * 遞歸和回溯
 *
 */
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();
        }
        
    }
    
    /**
     * 深度優先遍歷棋盤
     * @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;
    }
    
    
}