回溯法入门学习之一
一： 回溯法
有时我们要得到问题的解，先从其中某一种情况进行试探，在试探过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择， 然后继续向前试探，反复这样的过程直到求出问题的解。比喻:“下棋”： 每一次走棋的位置都要考虑到是否是损人利己，如果是害人害己的走法就要回撤，找下一步损人利己的走法。又如玩RPG游戏中碰到“迷宫”大家是怎样出来的?

回溯跟深度优先遍历是分不开的，我们倾向于把回溯看做深度优先遍历的延伸。我们知道，图的深度优先遍历每个节点只会被访问一次，因为我们一旦走过一个点，我们就会做相应的标记，避免重复经过同一个点。而回溯的做法是，当走过某一个点时，标记走过，并把该点压栈；当该节点出栈时，我们再把它标记为没有走过，这样就能保证另外一条路也能经过该点了。

二:"深度优先搜索+回溯"递归框架：

函数DFS（节点）{

如果（节点=目标节点） {找到目标，跳出}
遍历所有下一层节点for(int i=0;i<k;i++){
标记下一层节点i已访问;
DFS（下一层的节点i）
恢复i为未访问
}

}


三：举例

题目描述：
在一个4*5的棋盘上，马的起始位置坐标有键盘输入，求马能返回起始位置的不同走法总数并输出每一种走法（马走过的位置不能重复，马走“日”字。
输入输出样例

Sample input
1 1

Simple output
4596

分析:经典回溯。搜索过程是从起点(x,y)出发，按照深度优先的原则，从8个方向中尝试一个个可以走的点，直到返回起点,不能的话,回溯上一点,继续.

程序运行:
D:\tutu>java Main
输入马的起始坐标:
1 1
sx = 1, sy = 1
total=1

   5   8  11   2   0
  10   1   4   7   0
   0   6   9  12   3
   0   0   0   0   0
total=2

   5   8   0   2   0
  10   1   4   7   0
   0   6   9  12   3
   0  11   0   0   0
total=3

   5   8  11   2   0
   0   1   4   7  10
   0   6   9  12   3
   0   0   0   0   0
total=4

   5   8  11   2   0
  12   1   4   7  10
   0   6   9  14   3
   0  13   0   0   0
total=5

   5   8   0   2   0
   0   1   4   7   0
   0   6   9   0   3
  10   0   0   0   0
total=6

   5   8   0   2   0
   0   1   4   7   0
   9   6   0   0   3
   0   0  10   0   0
total=7
...........

total=4595

   0   0   0   0   0
   4   1  10   7   0
  11   8   5   2   0
   0   3  12   9   6
total=4596

   0   0   0   0   0
   4   1   0   0   0
   0   0   5   2   0
   6   3   0   0   0

源码: