最新消息:网站改版咯

骑士走棋盘 算法分析

C语言 Yovae 2462浏览

骑士走棋盘问题也叫骑士游历问题或骑士旅游问题
骑士走棋盘说明:骑士旅游(Knight tour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出
已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完[所有的位置?

 

 

 

 

 

 

 

 

 

骑士游历,算法源码:

/*
 * 骑士走棋盘问题
 * coding:Yovae www.yovae.com
 * 算法描述:假设骑士所在当前位置八个方向x,y坐标分别为{-2,-1,1,2,2,1,-1,-2},{1,2,2,1,-1,-2,-2,-1}
 *          遍历选择八个方向中下一个可走方向,选择下一个方向中可走步数最少的方向继续走。
 *          简单的说,先将最难的位置走完,接下来的路
 *          就宽广了,骑士所要走的下一步,为下一步再选择时,所能走的步数最少的一步。
*/
#include <stdio.h>

int pan[8][8]={0};

int travel(int pan[8][8],int x,int y)
{
	int i,j,m,curX,curY,tempi,tempj,xx[8]={-2,-1,1,2,2,1,-1,-2},yy[8]={1,2,2,1,-1,-2,-2,-1},next[8]={0},min,minI,count,endX,endY;
	curX=x;
	curY=y;
	pan[curX][curY]=1;

    for(m=2;m<=64;m++)
	{
	      for(i=0;i<8;i++)
		  {
			  count=-1;
			  tempi=curX+xx[i];
			  tempj=curY+yy[i];
			  if(tempi<0||tempi>7||tempj<0||tempj>7||pan[tempi][tempj]!=0)
			  {
				  continue;
			  }
			  else
			  {
				  endX=tempi;
				  endY=tempj;
				  for(j=0;j<8;j++)
				  {
					   if(tempi+xx[j]<0||tempi+xx[j]>7||tempj+yy[j]<0||tempj+yy[j]>7||pan[tempi+xx[j]][tempj+yy[j]]!=0)
					   {
				           continue;
					   }
					   else
					   {
						   next[i]++;
					   }
				  }
			  }
		  }
          
		  minI=-1,min=8;
		  for(i=0;i<8;i++)
		  {
			  if(next[i]==0)
			  {
				  continue;
			  }
			  else if(min>next[i])
			  {
				  min=next[i];
				  minI=i;
			  }
			  next[i]=0;
		  }
		  if(minI==-1&&m!=64)
		  {
			  return 0;
		  }
		  else if(minI==-1&&m==64)
		  {
			  pan[endX][endY]=m;
			  return 1;
		  }
		  else
		  {
		  curX+=xx[minI];
		  curY+=yy[minI];
		  pan[curX][curY]=m;
		  }
	}
	return 1;


}
void display(int pan[8][8])
{
	    int i,j;
		for(i=0;i<8;i++)
		{
		for(j=0;j<8;j++)
		{
			printf("%3d",pan[i][j]);
		}
		printf("\n");
		}
}
int main()
{
	int x,y;
	display(pan);
	printf("Enter start (x,y):");
	scanf("%d%d",&x,&y);
    if(travel(pan,x,y))
	display(pan);
	else
	printf("不能走完!");
	return 0;
}
/**
 * @author 叶有为   E-mail:yovae@qq.com
 * @version 创建时间:2011-5-26 下午02:14:20
 * @Website:www.yovae.com
 * 
 */
import java.util.*;

public class Knight {
	public static void main(String args[])
	{
		int k[][]=new int[8][8];
		System.out.println("Enter the start poisition (x,y):");
		Scanner in=new Scanner(System.in);
		int x,y;
		x=in.nextInt();
		y=in.nextInt();
		if(travel(k,x,y)==1)
		{
			System.out.println("游历成功!");
			display(k);
		}
		else
		{
		   System.out.println("游历失败!");
		   display(k);
		}
		
	}
	
	public static void display(int k[][])
	{
		for(int i=0;i<8;i++)
		{
			for(int j=0;j<8;j++)
			{
				System.out.printf("%3d",k[i][j]);
			}
			System.out.println();
		}
	}
	
	public static int travel(int k[][],int x,int y)
	{
		int curX,curY,endX = 0,endY = 0,m,tempX,tempY;
		curX=x;
		curY=y;
		k[curX][curY]=1;
		int nextX[]={-2,-1,1,2,2,1,-1,-2};
		int nextY[]={1,2,2,1,-1,-2,-2,-1};
		int way[]=new int[]{0,0,0,0,0,0,0,0};
		for(m=2;m<=64;m++)
		{
			for(int i=0;i<8;i++)
			{
				tempX=curX+nextX[i];
				tempY=curY+nextY[i];
				
				if(tempX<0||tempX>7||tempY<0||tempY>7||k[tempX][tempY]!=0)
				{
					continue;
				}
				else
				{
					endX=tempX;
					endY=tempY;
					for(int j=0;j<8;j++)
					{
						if(tempX+nextX[j]<0||tempX+nextX[j]>7||tempY+nextY[j]<0||tempY+nextY[j]>7||k[tempX+nextX[j]][tempY+nextY[j]]!=0)
						{
							continue;
						}
						else
						{
							way[i]++;		
						}		
					}
					
					
				}
			}
		
			int i,min,minP;
			for(i=0,min=9,minP=-1;i<8;i++)
			{
				if(way[i]==0)
				{
					continue;
				}
				else if(min>=way[i])
				{
					min=way[i];
					minP=i;
						
				}
				way[i]=0;
			}
			if(minP==-1)
			{
				if(m==64)
				{
				  k[endX][endY]=m;
				  return 1;
				}
				else
				{
					return 0;
				}
			}
			else
			{
			curX+=nextX[minP];
			curY+=nextY[minP];
			k[curX][curY]=m;
			}		
		}
		return 1;
		
	}

}

转载请注明:Yovae Studio » 骑士走棋盘 算法分析