map.java

java遍历8*8棋盘源代码 运用哈密顿回路遍历

package cruise;
import java.util.*;
/*******类Map,即骑士所走的棋盘,此处是8*8*/
public class Map {
/*******Attributes*/
///////////////////////////
/*********记录棋盘状态*/
///////////////////////////
/**Path存储走过的路径,单元存储的数字n表示骑士第n步走过该格.如果某个单元为"0",则该单元没走过*/
int[][] Path = new int[8][8];
/**Tried存储从该格出发曾多少次尝试,但下一步是死路.*/
int[][] Tried = new int[8][8];
/**Exit存储每个单元格可向外走的出口数,若某Exit[i][j],证明此单元格出去是死路.*/
int Exit[][]={  {2,3,4,4,4,4,3,2},
				{3,4,6,6,6,6,4,3},
				{4,6,8,8,8,8,6,4},
				{4,6,8,8,8,8,6,4},
				{4,6,8,8,8,8,6,4},
				{4,6,8,8,8,8,6,4},
				{3,4,6,6,6,6,4,3},
				{2,3,4,4,4,4,3,2}};
/////////////////////////////
/*********记录移动状态*/
////////////////////////////
/**horizontal和vertical是某点出发8种移动的两个单下标数组*/
int horizontal[]={2,1,-1,-2,-2,-1,1,2};
int vertical[]={-1,-2,-2,-1,1,2,2,1};
/**direction标志此时是向前移还是向后移*/
boolean direction;

///////////////////////////////////////////////
/*********Methods*/
//////////////////////////////////////////////
/**PrintMap()
 * 功能:打印一个8*8二维数组,用来打印骑士走过的路径.并可在程序调试中监视各数组状态
 * 参数:二维数组
 * 返回:无*/
void PrintMap(int[][] array)
{
	int pi,pj;
	for(pi=0;pi<8;pi++){
		for(pj=0;pj<8;pj++){
			System.out.printf("%3d  ",array[pj][pi]);
		}
		System.out.printf("\n");
	}
}
/**FindWay()
 * 功能:找到当前位置下,下一步的最佳路径
 * 参数:当前位置currentX,currentY
 * 返回:最佳路径所对应的指针*/
int FindWay(int currentX, int currentY)
{
	int next;//index
	int n_th;//此单元格曾退回过n_th次
	int consequence[]= {-1,-1,-1,-1,-1,-1,-1,-1};//对可走路径由按出口数多少进行排序
	
	for(n_th=0;n_th<=Tried[currentX][currentY];n_th++)//找几个方向中出口数第n小的方向
	{
		int min = 10;
		for(next=0;next<8;next++)
		{
			for(int i=0;i<8;i++)
			{
				if(next==consequence[i])next++;//跳过已经加入consequence里的单元
			}
			int nextX=currentX+horizontal[next];
			int nextY=currentY+vertical[next];
			if(nextX<8&&nextX>=0&&nextY<8&&nextY>=0&&Path[nextX][nextY]==0&&Exit[nextX][nextY]<=min&&Exit[nextX][nextY]>=0)
			{//未出界，未走过且比前一个出口最少的单元出口数少
					min=Exit[nextX][nextY];
					consequence[n_th]= next;
			}
		}
	}

	for(int j=Tried[currentX][currentY];j>=0;j--)
	{
		if(consequence[j]!=-1)return(consequence[j]);//返回最佳路径
	}
	return(-1);//没有路径可走,死路
}
/**FindWay()
 * 功能:方法重载,找到当前位置下,上一步的位置
 * 参数:当前位置与当前步数
 * 返回:上一步对应的指针,若是死路,返回-1*/
int FindWay(int currentX, int currentY, int step)
{
	for(int forward=0;forward<8;forward++)
	{
		int forwardX=currentX+horizontal[forward];
		int forwardY=currentY+vertical[forward];
		if(forwardX<8&&forwardX>=0&&forwardY<8&&forwardY>=0
				&&Path[forwardX][forwardY]==step-1)//找到标志为step-1的单元格
			return forward;		
	}		
	return -1;//没找到前一步,不可能
}
/**UpdatExit()
 * 功能:更新走过的单元格旁边的出口数
 * 参数:当前位置
 * 返回:无*/
void UpdatExit(int currentX, int currentY)
{
	for(int next=0;next<8;next++)
	{
		int nextX=currentX+horizontal[next];
		int nextY=currentY+vertical[next];
		if(nextX<8&&nextX>=0&&nextY<8&&nextY>=0)//如果未出界
		{
			if(direction) Exit[nextX][nextY]--;//若正在前进,周围单元格出口数减1
			else {
				Exit[nextX][nextY]++;//若正在后退,周围单元格出口数加1
				Tried[nextX][nextY]=0;//不会再次以此路径到达此点,故失败历史置0
			}
		}
	}	
}
/**UpdateTried()
 * 功能:尝试失败一次后,记录失败状态
 * 参数:当前位置
 * 返回:无*/
void UpdateTried(int currentX,int currentY)
{
	Tried[currentX][currentY]++;
}

////MAIN
public static void main(String[] args) 
{
	Knight knight1 = new Knight();
	do{
		if(!knight1.Forward())knight1.Backward();//若前面是死路,后退
	}while(knight1.step<64);
	
	knight1.MapPath();//画路径
}//main

}//class Map