package com.work.knite1;
public class Seat {
int x;
int y;
int n;
}
package com.work.knite1;
public class Position {
int x;
int y;
Position pre;//指向前一个位置
int[] mark=new int[8];//该结点8个方向是否访问的标志位
public Position(){}
public Position(int i,int j)
{
x=i;
y=j;
pre=null;//；
for(int k=0;k<8;k++)
mark[k]=0;
}
}
package com.work.knite1;
import java.util.ArrayList;
import java.util.Vector;
public class TestKinte1 {
static int M=8;//棋盘大小
static int[][] b=new int[64][2];
static int[][] flag=new int[M][M];//标记某个位置以进栈。
static int[][] direct=new int[2][8];//标志8个方向。
static int count;
static int min;
static int last;
static int x;
static void printKnight()
{
for(int i=0;i<=63;i++)
System.out.print(b[i][0]+","+b[i][1]+" ");
System.out.println();
}
static void initChessboard()//初始化
{
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
{
//b[i][j]=0;
flag[i][j]=0;//标记某个位置以进栈。
}
//初始化八个方向,从左上角开始，顺时针
direct[0][0]=-1;direct[1][0]=-2;
direct[0][1]=-2;direct[1][1]=-1;
direct[0][2]=-2;direct[1][2]=1;
direct[0][3]=-1;direct[1][3]=2;
direct[0][4]=1;direct[1][4]=2;
direct[0][5]=2;direct[1][5]=1;
direct[0][6]=2;direct[1][6]=-1;
direct[0][7]=1;direct[1][7]=-2;
}
public static boolean isvaliation(Position p)//判断该位置是否合理
{
if(p.x>=M||p.x<0||p.y>=M||p.y<0)
return false;
return true;
}
static Seat findPosition(Position p)//从左上角进行遍历
{
//初始化
Seat s =new Seat();
s.x=0;s.y=0;s.n=8;
for(int i=0;i<8;i++)//有8个可选的方向
{
Position temp = new Position();//temp是下一个可能的位置
temp.x=p.x+direct[0][i];
temp.y=p.y+direct[1][i];
if(!isvaliation(temp)||p.mark[i]==1)//位置是否出了边界，该位置是否遍历过。
continue;
if(flag[temp.y][temp.x]==0)
{
s.x=temp.x;
s.y=temp.y;
s.n=i;
break;
}
}
return s;
}
static void clearDirect(Position p)//回溯时清除该结点的方向
{
if(p!=null)
{
for(int i=0;i<8;i++)
p.mark[i]=0;
}
}
public static void Knight(Position p,int k)
{
b[k][0]=p.x;
b[k][1]=p.y;
Position p1=new Position();
Seat s=findPosition(p);
if(!(s.x==0&&s.y==0))
{
flag[s.x][s.y]=2;
p1.x=s.x;
p1.y=s.y;
p1.mark[s.n]=1;
}else
{
clearDirect(p);
flag[p.y][p.x]=0;
}
if(k<63)
{
Knight(p1, k+1);
}
else{
printKnight();//打印路线
//cnt++;
return;
}
}
public static void main(String[] args) {
initChessboard();
Knight(new Position(0,0),0);
}
}