Java马踏棋盘算法
CmdSmith 人气:0马在某个点最多可能有8种走法,用递归和回溯实现。
注:代码中,查找下一个可走坐标是从右下第一个开始的,也就是图中的4。可以通过修改a,b...h的值来改变顺序。
代码:
/** * 马踏棋盘算法 * 递归和回溯 * */ 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; } }
结果:
如果从(0,0)开始的话
加载全部内容