关于骑士的游历的问题的Java实现

在编程语言中，有一个关于骑士的游历的问题，在棋盘中，马走日字，如何让马在不重复走任一点的情况下，遍历整个棋盘。如下图：

 <!--EndFragment-->

在某一点，马最多有八种走法，如果直接用循环测试每一种走法是否可行是不行的，这样可能性太多，计算机速度跟不上。

这里我用了贪心策略来减少下一步走法的可能。下面是详细的介绍。

这里的贪心策略的意思是当马在A点时，它能不重复的情况下能走的点是B集合中的某个元素，那么如何确定是那个呢？是B集合中元素的点的走法的个数最小的那个。

这样，我们就需要一个方法，统计某点的走法，一个方法去得到下一个点的真正的走法，一个方法循环调用前两个方法，使每个点都能走到。

这里我们设置当棋盘为8*8的风格时。

代码实现如下：

设置两个一维数组和一个二维数组，分别代表行的增量（从当前点到下一点的数组的下标的差），列的增量，棋盘。如下：

//行与列的增量数组，考虑八个方向

private int[] AddRow=   {2,1,2,1,-2,-1,-2,-1};

private int[] AddColumn={1,2,-1,-2,1,2,-1,-2};

//用数组存储棋盘的点

private int Chess[][]=new int[8][8];

第一个方法：统计某点的可行的出口数目。

在这个方法中，用数组a存储到达这个出口的增量

马走到的点不能越界，也不能是已经走过的点

/**

 * 得到点（i，j）的出口数

 * @param i 行数

 * @param j 列数

 * @param a 不同的出口所用的增量的下标

 * @return  点（i，j）的出口个数

 */

public int getCount(int i,int j,int[] a){

//出口数

int count,k;

//检验不同的增量下的出口可行否

for(count=k=0;k<8;k++){

//得到下一个出口的座标

int i1=i+AddRow[k];

int j1=j+AddColumn[k];

//是否是出口 ，能则count加1，

if(i1>=0&&i1<8&&j1>=0&&j1<8&&Chess[i1][j1]==0){

a[count++]=k;

}

}

//得到出口数

return count;

}

 

第二个方法：利用得到的下一个出口数，比较下一个出口的出口数，选择最小的一个。

/**

 * 得到下一个要走的出口

 * @param i 点的行

 * @param j 点的列

 * @return 下一个出口所用的增量的数组下标

 */

public int getNext(int i,int j){

//最小出口数min，下一个出口所用的增量的数组下标minPoint

int min=9,minPoint = 0;

//存储出口下标的数组a

int[] a=new int[8];

//存储出口下标的数组b

int[] b=new int[8];

//得到点（i，j）的出口数

int m=getCount(i,j,a);

//如果没有出口

if(m==0){

return -1;

}

//得到下一个出口是最小出口数的增量数组的下标

for(int k=0;k<m;k++){

//得到下一个出口出口数

int temp=getCount(i+AddRow[a[k]],j+AddColumn[a[k]],b);

if(temp<min){

min=temp;

//下一个出口所用的增量的数组下标

minPoint=a[k];

}

}

 

return minPoint;

}

第三个方法：循环调用第二个方法，达到马要遍历棋盘的目的。

当马走到某点时，将该的元素设置为马的第几步，以改变初始值，

/**

 * 从某点开始考查

 * @param xi 行数

 * @param yj 列数

 */

public  void startCheck(int xi,int yj){

//设置行列i，j，步数step，出口所用的增量的数组下标num

int i = xi,j = yj,step,num;

//重设数组元素为0

for(int a=0;a<8;a++){

for(int b=0;b<8;b++){

Chess[a][b]=0;

}

}

//数组开始的点为1

Chess[i][j]=1;

//开始遍历每一个点

for(step=2;step<=64;step++){

//如果没有出口，跳出循环

if((num=getNext(i,j))==-1){

break;

}

//到下一个出口

i+=AddRow[num];

j+=AddColumn[num];

//设置些点是第几步

Chess[i][j]=step;

}

//如果符合完全遍历，打印

if(step==65){

for(int x=0;x<8;x++){

for(int y=0;y<8;y++){

System.out.print(Chess[x][y]+"  ");

}

System.out.println();

System.out.println();

}

}

}

 

第四个方法：将不同的点作为马的起始点。

/**

 * 每一个点作为起点，进行遍历

 */

public void travelEveryOne(){

for(int i=0;i<8;i++){

for(int j=0;j<8;j++){

//调用遍历

startCheck(i,j);

System.out.println(i*8+j+1+"==================================" +i+

"================================");

}

}

}

 

 

这样，只要调用第四个方法，就能将马在不同的起始点下遍历整个棋盘的走法了。

某个走法如下截图：

 

 

<!--EndFragment-->