关于回溯法

回溯的基本思想是：从一个给定的起始位置，我们希望到达一个目的位置。我们重复地进行选择（可能是猜测）下一个位置应当是什么。如果一个给定的选择是有效的，即新的位置可能位于通向目的位置的途径中，则前进到这个新的位置，然后继续。如果一个给定的选择通向了死胡同 ，则回到前面的位置，进行其他的选择。回溯就是通过一系列位置选择到达目的位置，并且在不能到达目的位置时反向退回的策略。

回溯类的通用接口如下：
import java.util.*;

public interface Application{
//如果位置pos为通向目标位置的路径上，返回true，否则返回false
boolean valid(Position pos);

//标记位置pos，这个位置pos可能在目标路径上
void record(Position pos);

//若pos是目标位置，返回true，否则，返回false
boolean done(Position pos);

//标记位置pos，此位置不在目标路径上
void undo(Position pos);

//返回路径的字符串
  String toString();
 
  //枚举从当前位置开始，所有可能的下一步位置
  Iterator iterator(Position pos);

典型的回溯的代码：
public boolean tryToSolve(Position pos){
boolean success=false;
Iterator itr=app.iterator(pos);
while(!success&&itr.hasNext()){
   pos=(Position)itr.next();
   if(app.valid(pos)){
       app.record(pos);
       if(app.done(pos))
          success=true;
       else{
          success=tryToSolve(pos);
          if(!success)
             app.undo(pos);
      }
   }
}
}
return success;
}

注意：从pos位置开始的移动选择，有三种可能性：
1） 其中的一个选择是目的位置。那么while循环结束，返回true，说明成功结束。
2） 其中的一个选择是有效选择，但不是目的位置。那么再次调用tryToSolve方法，从这个有效选择开始。
3）没有一个选择是有效的。那么while循环结束，返回false，说明从当前位置无法到达目标位置。
tryToSolve方法的参数表示一个有效的、记录了的位置。