怎样用数据结构的栈和java语言实现骑士游历问题，即让一个国际象棋的马不重复的走完棋盘上的所有格子？

Question

我知道需要定义八个方向的，但是，关键是如果骑士走到一个格子里，结果这个格子走不通了，而此时并没有结束，然后该怎么办啊？最后还需要用栈把路径记录下来，哎，都想了很多天了，还是想不出来该怎么办。。。

Answer 1

猪哥回答：
呵呵，很经典的回溯法练习题，题我会解，不过国际象棋我不会，如果是马走日字的话，我就给你写一个吧。
原理很简单，一个棋盘看成一个什么二维什么来着，忘了，猪哥离开校门很多年。就是X轴、Y轴，棋盘左下角做原点，因为走日字，假定骑士起始坐标为(X,Y)，那么他的移动规则是(X-1,Y-2)或(X-1,Y+2)或(X-2,Y-1)或(X-2,Y+1)或(X+1,Y+2)或(X+1,Y-2)或(X+2,Y+1)或(X+2,Y-1)这8种移动规则，也不知道你看懂了没，下面我开始写代码。。。。

我事情比较多，先不急。。代码我慢慢写。
写了个简单的例子，List也是栈实现的一种方式，你先看看吧，不知道对你有没有帮助，当然你最好用3*4、4*5这样的小数字调试，大棋盘程序执行的时间很长，非常长。
import java.util.ArrayList;
import java.util.List;

/**
* 骑士周游demo,没有做防呆处理
* 棋盘模拟图，A假定为骑士起始位置
* 3
* 2
* 1
* 0 A
* 0 1 2 3
* @author 猪哥甲
*
*/
public class DemoKnight
{
private static int NX = 3;//棋盘横向大小
private static int NY = 4;//棋盘纵向大小
private static int[] dx = { 2, 1, -1, -2, -2, -1, 1, 2 };
private static int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };
private int sx = 0;//骑士起始横坐标
private int sy = 0;//骑士起始纵坐标
private List points = new ArrayList();//用来有解的路线
private List steps = new ArrayList();//用来记录骑士走过的路线

public static void main(String[] args)
{
DemoKnight dkt = new DemoKnight();
dkt.sx = 0;
dkt.sy = 0;
List list = new ArrayList();
dkt.steps.add(dkt.getPointStr(dkt.sx, dkt.sy));
dkt.KnightTrav(dkt.sx, dkt.sy);
int size = dkt.points.size();
System.out.println("终于走完了。。。共找到"+size+"种解决方案");
for(int i=0;i<size;i++){
List list2 = (List) dkt.points.get(i);
for(int j=0;j<list2.size();j++){
System.out.print(list2.get(j)+"-->");
}
System.out.println();
}
}
public boolean KnightTrav(int x, int y)
{
String str = null;
boolean flag = false;
//8种方向，每种方向假定有一个解法，8次循环
for(int tx=0,ty=0,count=0;count<8;count++){
tx = x + dx[count];
ty = y + dy[count];
str = this.getPointStr(tx, ty);

if((tx>=0&&tx<NX)&&(ty>=0&&ty<NY)&&!this.steps.contains(str)){
flag = true;
this.steps.add(str);
int size = this.steps.size();
if(!KnightTrav(tx, ty)){
System.out.println("一条路走到尽头,共走了"+size+"步");
}
if(size==NX*NY){
points.add(new ArrayList(this.steps));
}
this.steps.remove(size-1);
}
}
return flag;
}

private String getPointStr(int x,int y){
StringBuffer sb = new StringBuffer("{");
sb.append(x);
sb.append(",");
sb.append(y);
sb.append("}");
return sb.toString();
}
}