knightcruise.java

这里面有JAVA和C的骑士问题的一些求解方法 大家可以做为参考 有什么问题可以在这里留言

import java.applet.Applet;
import java.awt.Graphics;
import java.awt.Color;
import javax.swing.JOptionPane;
import java.awt.Font;

//提供二元型数值
class Pair
{
	private int x;
	private int y;
	Pair()
	{
	}
	Pair(int a,int b)
	{
		x=a;
		y=b;
	}
	public int getX()
	{
		return x;
	}
	public int getY()
	{
		return y;
	}
}

//提供巡游结果
class GetKnightCruise
{
	//存储8*8棋盘上各位置为第几步
	private static int[][] arr=new int[8][8];
	//用来存储骑士可以到达的8个位置的偏移量
	private static Pair[] index=new Pair[8];
	//设置index的初始值
	private static void setIndex()
	{
		index[0]=new Pair(-2,1);
		index[1]=new Pair(-1,2);
		index[2]=new Pair(1,2);
		index[3]=new Pair(2,1);
		index[4]=new Pair(2,-1);
		index[5]=new Pair(1,-2);
		index[6]=new Pair(-1,-2);
		index[7]=new Pair(-2,-1);
	}
	//设置棋盘位置的处始值
	private static void setArr()
	{
		for (int i=0;i<8;i++)
		{
			for (int j=0;j<8;j++)
			{
				arr[i][j]=0;
			}
		}
	}
	//计算位置（i,j）的出口数
	private static int getExitNum(int i,int j)
	{
		int num=0;
		for(int t=0;t<8;t++)
		{
			if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
			{
				num++;
			}
		}
		return num;
	}
	//选择下一个所走的位置，beginIndex的作用是定位选择优先权的起始位置
	private static Pair getNextPositioin(int i,int j,int beginIndex)
	{
		int[] temp=new int[8];
		int min=8;
		for(int t=0;t<8;t++)
		{
			if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
			{
				temp[t]=getExitNum(i+index[t].getX(),j+index[t].getY());
				if(temp[t]!=0&&temp[t]<min)
				{
					min=temp[t];
				}
			}
		}
		for(int t=0;t<8;t++)
		{
			int h=(t+beginIndex)%8;
			if(temp[h]==min)
			{
				return new Pair(i+index[h].getX(),j+index[h].getY());
			}
		}
		return new Pair(-1,-1);
	}
	//寻找下一个唯一的出口（主要给最后一步使用，因为getNextPositioin已经不适合了）
	private static Pair getNextPositioinOfTheLastStep(int i,int j)
	{
		for(int t=0;t<8;t++)
		{
			if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
			{
				return new Pair(i+index[t].getX(),j+index[t].getY());
			}
		}
		return new Pair(-1,-1);
		
	}
	//从（i,j）开始骑士巡游
	private static void getKnightCruise(int i,int j)
	{	
		Pair tt;
		setArr();
		setIndex();
		for(int q=0;q<8;q++)
		{
			int ii=i,jj=j;
			int p=0;
			for(p=1;p<=64;p++)
			{
				arr[ii][jj]=p;
				if(p==63)
				{
					tt=getNextPositioinOfTheLastStep(ii,jj);
					ii=tt.getX();
					jj=tt.getY();
					continue;
				}
				tt=getNextPositioin(ii,jj,p);
				ii=tt.getX();
				jj=tt.getY();
				if(ii==-1||jj==-1)
				{
					break;
				}
			}
			if(p==65)
			{
				return;	
			}
		}
	}
	//得到巡游数组
	public static int[][] getResult()
	{
		int i=0,j=0;
                  getKnightCruise(i,j);
		return arr;
	}
}


public class KnightCruise extends Applet
{
	public void paint(Graphics g)
	{
		
		for(int i=1;i<=8;i++)
		{
			for(int j=1;j<=8;j++)
			{
				if((((i%2)==1)&&((j%2)==0))||(((i%2)==0)&&((j%2)==1)))
				{
					g.setColor(Color.red);
					g.fillRect(i*40,j*40,40,40);
				}
				else
				{
					g.setColor(Color.white);
					g.fillRect(i*40,j*40,40,40);
				}
			}
		}
		g.setColor(Color.blue);
		for(int i=0;i<8;i++)
		{
			for(int j=0;j<8;j++)
			{
				g.drawOval(48+i*40,48+j*40,24,24);
			}
		}
        g.setColor(Color.black);
		int[][] board=new int[8][8];
		board=GetKnightCruise.getResult();
		Font num=new Font("宋体",Font.BOLD,15);
		g.setFont(num);
		for(int i=0;i<8;i++)
		{
			for(int j=0;j<8;j++)
			{
				g.drawString(board[i][j]+"",53+i*40,65+j*40);
			}
		}
        return;
	}
}