呵呵,很經典的回溯法練習題,題我會解,不過國際象棋我不會,如果是馬走日字的話,我就給妳寫壹個吧。
原理很簡單,壹個棋盤看成壹個什麽二維什麽來著,忘了,豬哥離開校門很多年。就是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();
}
}