在编程语言中,有一个关于骑士的游历的问题,在棋盘中,马走日字,如何让马在不重复走任一点的情况下,遍历整个棋盘。如下图:
<!--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-->
- 大小: 3.6 KB
- 大小: 22.3 KB
分享到:
相关推荐
骑士游历java代码 实验 课程设计
通过研究骑士游历的规则对问题进行数学模型抽象,通过研究骑士游历的方向与可到达情况,将骑士的空间移动抽象成数学表达式,进而映射到程序中所需对应的数据结构形式,最后通过利用JAVA语言得以实现骑士游历问题中...
骑士游历,java实现,启发式算法,这是我的一个作业,但是我觉得对大家应该挺有帮助的
骑士游历问题 C# 控制台程序 参考:数据结构java版 电子工业大学出版社
很好用的一个案例,无数据库,很简单!使用Java写的!
JAVA课程设计中的一部分,有一些文字性的描述,主要为源代码,。
用Java做的骑士游历小游戏,需要的可以下载下来看看学学!
骑士游历程序的开发 java 课程设计 骑士游历程序的开发 java 课程设计
java课程设计源代码,骑士游历程序的开发 大学课程设计可以用这个..真的很不错.
运行速度比较快的骑士问题(马周游问题)的Java源程序,配合GUI,显示整个回溯过程!
骑士游历java课程设计
骑士游历程序 可以游历棋盘的每一个空格 这是一款小游戏,骑士游历。适合JAVA初学者
这是一款小游戏,骑士游历。适合JAVA初学者。
java编程游戏之骑士游历
KnighTour 骑士游历原代码 JAVA程序 能够在ECLIPSE中完成运行
用JAVA写的一个骑士游历程序的开发,包括课程设计要求的文字描述及源代码
通过研究骑士游历的规则对问题进行数学模型抽象,通过研究骑士游历的方向与可到达情况,将骑士的空间移动抽象成数学表达式,进而映射到程序中所需对应的数据结构形式,最后通过利用JAVA语言得以实现骑士游历问题中...
java课程设计--骑士游历程序的开发
本人十余年JAVA从业经验,精通JAVA高可用、分布式、高并发系统架构设计。有志于做JAVA职业规划、技术提升的可与我联系,交个朋友~ 本人十余年JAVA从业经验,精通JAVA高可用、分布式、高并发系统架构设计。有志于做...
(骑士游历)JAVA程序设计课程设计报告