骑士漫游问题

骑士漫游问题 骑士漫游问题 问题描述:国际象棋中骑士按L形进行跳跃，在8*8的棋盘上找到一条路径，从某起始位置出发，不经过重复的格，走遍棋盘上的所有格。 需求分析: 棋盘N*N个格子，由于要不重复路线，所以每个格子要有个标记来表明起已经/未被访问过，故可以一个二维布尔组模拟棋盘。 棋子有属性当前位置，可以用两个整数表示当前位置。跳跃方式，根据国际象棋规则，骑士有8个方向可以跳跃，若当前位置是(x,y),则其可跳跃格为(x+1,y+2)和(x+2,y+1)，用0—7的编号代表其中一种跳跃方式。 概要设计:采用尝试回溯的方法寻找路径。用一个N*N长度的栈保存路径。起始位置进栈，从当前位置出发，即栈顶元素位置，依顺序像八个方向进行试探，若试探方向未被访问且没有越界，则跳跃到此格，此位置进栈，继续进行试探，直到走完怎么棋盘为止。若八个方向均不能跳跃，则当前位置出栈，退回上一步，寻找新的方向继续进行尝试。已走完整个棋盘的条件为栈满，即栈内的元素个数等于栈长度。若栈为空，则说明无可行路径走完棋盘。 对此进行进一步讨论，此方法存在大量回溯，时间代价非常大，在8*8的棋盘上很可能在可容忍的时间类无法找到路径，所以对起进行优化。考虑棋盘，直观的，按骑士走法，中间最容易被访问，边角最难以访问到。进一步考虑棋盘每一格，按骑士走法，能访问到此格的上一格的个数是不同的，把能访问此格的上一格的个数之和称为每格的访问能力。所以优化方法为:尽量先访问访问能力低的格子。为此给棋盘添加一个N*N的二维数组，表示每格的访问能力值。给棋子添加一个8长度的数组，用来表示优先访问顺序。计算每格的访问能力算法:从棋盘上的每格出发，向八个方向进行尝试，若没有超出边界，则此格访问能力加1。优先访问顺序算法:重当前位置想八个方向试探，记录八个位置，比较访问能力数组，找到八个位置的访问能力，若越界，则需要最后访问，所以访问能力可以设为9，最后对八个位置按访问能力进行排序，得到优先访问顺序。 程序代码如下: ------------------------------华丽丽的分割线------------------------- public class SeqStack { //用到的顺序栈类 private Object value[]; private int top; private int length; //栈内元素个数 public SeqStack(int capacity) { value=new Object[capacity]; top=-1; length=0; } public boolean isEmpty(){ return this.top==-1; } public boolean push(E element){ if(element==null) return false; top++; value[top]=element; length++; return true; } public E pop(){ if(!isEmpty()){ E temp=(E)value[top]; value[top]=null; top--; length--; return temp; } else return null; } public E get(){ if(!isEmpty()) return (E)value[top]; else return null; } public int length(){ return this.length; } public int valueLength(){ return this.value.length; } } ------------------------------华丽丽的分割线------------------------- public class Knight { //骑士棋子 int x,y,tempx,tempy; int methodOrder[]; public Knight(int x,int y,int accessiblity[][]) { //构造骑士棋子，位置是(X,Y)，访 问能力数组accessiblity this.x=x; this.y=y; methodOrder=new int[8]; getMethodOrder(accessiblity); } void move(int method){ //移动方法 switch (method){ case 0 : tempx=x+1; tempy=y+2; break; case 1 : tempx=x+1; tempy=y-2; break; case 2 : tempx=x-1; tempy=y+2; break; case 3 : ; tempx=x-1 tempy=y-2; break; case 4 : tempx=x+2; tempy=y+1; break; case 5 : tempx=x+2; tempy=y-1; break; case 6 : tempx=x-2; tempy=y+1; break; case 7 : tempx=x-2; tempy=y-1; break; default : break; } } void moved(){ //移动 this.x=this.tempx; this.y=this.tempy; } void getMethodOrder(int accessiblity[][]){ //获得当前位置的优先访问顺序 int Order[][]=new int [8][2]; //用于保存8种走法的到达格的访问能力,int[][0]表示访问方法编号，int[][1]表示该访问方法的下格的访问能力 for(int i=0;i<8;i++){ move(i); if(tempx>=0 && tempx=0 && tempyOrder[j+1][1]){ int temp1=Order[j][1]; int temp2=Order[j][0]; Order[j][1]=Order[j+1][1]; Order[j][0]r[j+1‎‎=Orde][0];‎‎ Order[j+1][1]=temp1; Order[j+1][0]=temp2; } for(int i=0;i<8;i++) //保存优先访问顺序 methodOrder[i]=Order[i][0]; } } ------------------------------华丽丽的分割线------------------------- public class Chessboard{ //棋盘 boolean a[][]; int width; int accessiblity[][]; //访问能力组 int tempx,tempy; public Chessboard(int width) { //构造一宽，长为width的2维数组表示棋盘， 并获得访问能力组 a=new boolean[width][width]; this.width=width; getAccessiblity(); } void getAccessiblity(){ //获得访问能力组 accessiblity=new int[width][width]; for(int i=0;i=0 && tempx=0 && tempy(width*width); havePath=false; CB.a[firstx][firsty]=true; path.push(new Knight(firstx,firsty,CB.accessiblity)); getpath(); } public void getpath(){ //寻找路径 Knight temp=(Knight)path.get(); //取得栈顶元素，即当前位置。 kn=new Knight(temp.x,temp.y,CB.accessiblity); for(int i=0;i<8;i++){ kn.move(kn.methodOrder[i]); //按优先访问顺序进行尝试 if(kn.tempx>=0 && kn.tempy>=0 && kn.tempx=1;i--){ Knight temp=(Knight)path.pop(); pt[temp.x][temp.y]=i; } for(int i=0;i