|
四、用Java实现算法
本例声明Horse类，成员变量mat以二维数组表示棋盘，show表示是否显示中间结果，内部类Position中的成员变量x和y表示棋盘上一格的位置，x和y从1开始计数。
public class Horse
{private int mat[][]; //二维数组表示棋盘
boolean show; //是否显示中间结果
class Position //内部类
{int x,y; //表示棋盘上一格的位置
Position (int x,int y)
{this.x=x;
this.y=y;}
Position ()
{this(1,1);}
Position (Position p)
{this.x=p.x;
this.y=p.y;
}}
public Horse(int n,int x,int y,boolean show) //数组比实际棋盘多两行两列
{ mat=new int[n+2*2][n+2*2]:
this.show=show;
inition(); //棋盘初始化
play(x,y);}
public Horse(int n,int x,int y)
{ this(n,x,y,false);}
public Horse(int n)
{ this(n,1,1);}
public Horse()
{ this(8,1,1);}
public void inition() //棋盘初始化
{ int i,j;
for(i=0;i<=1;i++)
{ for(j=0;j<mat.length;j++) //顶边两行
mat[i][j]=-1;
for(j=0;j<mat.length;j++) //底边两行
mat[mat.length-1-i][j]=-1;
for(j=0;j<mat.length;j++) //左边两列
mat[j][i]=-1;
for(j=o;j<mat.length;j++)
mat[j][mat.length-1-i]=-1;}}
public int get(Position p) //获得p格的值
{ return mat[p.x+1][p.y+1];}
public void set(Position p,int i) //设置p格的值为i
{ mat[p.x+1][p.y+1]=i];}
public void play(int x,int y) //从（x,y）格开始遍历
{ int n=mat.length-4;
Position current=new Position(x,y);
int count=1;
int i,j,k=1;
while(count<=n*n&&k!=0)
{ set(current,count);
if(this.show)
System.out.print(”第”+count+”步 ”);
k=select(current); //试探，选择一个方向
if(k==0&&count<n*n)
System.out.println(”第”+count+”步无路可通！”)；}}
else
{count++;
corrent=goaStep(current,k);}}}
public boolean isValid(Position p) //判断p是否在棋盘内且未被访问过
{int n=mat.length-4;
if(p!=null&&p.x>=1&&p.x<=n&&p.y>=1&&p.y<=n&&get(p)==0)
return true;}
else
return false;}
public Position goaStep(Position p,int k) //返回p位置按k方向的下一位置
{int x=p.x;
int y=p.y;
switch(k)
{ case 1:x-=2;y++;break;
case 2:x--;y+=2;break;
case 3:x++;y+=2;break;
case 4:x+=2;y++;break;
case 5:x+=2;y--;break;
case 6:x++;y-=2;break;
case 7:x--;y-=2;break;
case 8:x-=2;y--;break;}
return new Position(x,y);}
public int select（Position p）//选择p位置到达下一位置next1应走的方向k
//试探next1的8个方向位置next2的可通路数road,road的最小值为minroad
{ int i=0,j=0,k=0,road=0,minroad=8;
Position next1=null,next2=null;
if(this.show)
{ System.out.println(“当前位置:（”+p.x+”,”+p.y+”）”);
this.output();
System.out.println(”方向 下一位置 可通方向 可通路数”)；}
for(i=1;i<8;i++)
{ road=0;
next1=goaStep(p,i);
if(isValid(next1))
{ if(this.show)
system.out.print(“ “+i+”\t(“+next1.x+”,”+next1.y+”)\t”);
for(j=1;j<=8;j++)
{ next2=goaStep(next1,j);
if(isValid(next2))
{road++;
if(this.show)
System.out.print(j+”,”);)}
if(road<minroad)
{minroad=road;
k=i;}
if(this.show)
System.out.println(“\t”+road);}}
if(this.show)
System.out.println(“选定下一个方向 k=”+k+”\r\n”);
return k;}
public void output()
{ int i,j,n=mat.length;
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{ if（mat[i][j]&&mat[i][j]<10）
System.out.print(” ”+mat[i][j]);
else
System.out.print(“ “+mat[i][j]);}
System.out.println();}
public static void main(String args[])
{ Horse h1=new Horse(8,1,1,false);
h1.output();}}
五、结论
该算法在Java环境下通过了测试，证明了算法的正确性。
预见算法虽然在每一格上选择下一步的方向需要花费一定的时间，但它针对性强，减少了许多盲目的试探，总的选择次数少，从而缩短了运行时间。
参考文献
[1] 张居敏,石礼娟,龙翔. Java程序设计经典教程(融合上机操作实例) [M].北京: 电子工业出版社,2008.
[2] Bruce Eckel.Java . 编程思想(第4版) [M].北京:机械工业出版社,2007.
[3] 叶核亚 . 数据结构（Java版）[M].北京: 电子工业出版社,2004.
[4] 黄晓东 . JAVA课程设计案例精编[M].北京:中国水利水电出版社,2004.
|
