回溯法
大三上学习算法时都没怎么真正去体会算法的精髓，更没想过如何将它用到应用程序中？
想到找工作时算法数据结构作为基础，会经常被考到，于是最近有开始复习算法了。
回溯递归，可以解决很多问题，比如迷宫问题，n皇后问题等
于是我通过看书学习，先实现了一个通用的回溯算法，与具体应用程序无关，回溯法核心是进行递归地找到目标位置，每次处于的位置，先判断是它是否符合要求，若符合，继续递归到下个位置，否则，回到上一个可选择的位置，BackTrack.java如下：
package 数据结构及算法.回溯法;import java.util.Iterator;public class BackTrack { Application app; public BackTrack(Application app){ this.app=app; } @SuppressWarnings("rawtypes")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); //System.out.println(pos.getRow()+" "+pos.getColumn()); if(app.done(pos)){ success=true; //System.out.println(app+"\n"); } else{ success=tryToSolve(pos); if(!success){ app.undo(pos); } } } } return success; }}package 数据结构及算法.回溯法;public class Position { private int column; private int row; public Position(){ this.row=0; this.column=0; } public Position(int row,int column){ this.row=row; this.column=column; } public int getRow(){ return this.row; } public int getColumn(){ return this.column; }}package 数据结构及算法.回溯法;import java.util.Iterator;public interface Application { boolean valid(Position pos);//判断是否有效，符合要求 void record(Position pos);//符合要求，就记录下来 boolean done(Position pos);//表示找到目标 void undo(Position pos);//从该位置下去无法找到目标，必须撤销，但可以留下撤销的痕迹，表示曾经走过 String toString();//重写，方便输出 Iterator iterator(Position pos);//可通过写个实现Iterator接口的内部类，用来存储该位置可以扩展的下面一系列的位置}