以下是狼，羊和卷心菜问题的描述：

一个人需要用一条船将狼，羊河卷心菜运送到一条河的对岸。限制条件如下：

• 这条船比较小，每次仅能运送一个物体，且船的运行都需要人来控制
• 当没人看管的时候，狼会吃羊，而羊会吃卷心菜。

如何将这些这三个物体安全送到河的对岸？

对这个问题感兴趣的朋友可以玩玩这个逻辑游戏，看你玩多少次能够将他们成功运送到对岸。

下面看看，如何使用Backtrack算法合理的分析和解决这个问题：

首先，我们对这个问题里面涉及到的状态图形化（State Representation），这样有助于我们理解问题和编写程序解决问题。

上图分别描述了我们的初始状态和目标状态，其中的字母和数字分别表示：

• B 表示船的位置，在左边那个栏位时，表示船在起始岸边；反之，表示船在目标岸边；
• C表示cabbage（卷心菜），W表示wolf（狼），S表示sheep（羊）。
• 数字表示在当前岸边物体的个数

其次，我们要确定能够对状态进行的操作（Operators），显而易见，不管穿在那边，都可以进行如下四种操作：

• M(W)：将狼运到对岸
• M(S): 将羊运到对岸
• M(C)：将卷心菜运到对岸
• M()：不运送任何东西，只将穿运送到对岸

然后，我们要知道某个状态是否成功，即当前状态就是目标状态，还需要一个目标测试函数（Goal test），这个问题比较简单，不需要函数来表达，简单来说判断一个状态是否成功，需要判断起始岸的狼，羊和卷心菜数量之和为0，即以下函数：

N(C @ start) ＋ N(W @ start) + N(S @ start) = 0

以上函数，N表示数量，如N(C @ start)表示在起始岸上C的数目。

最后，在真正应用回溯（backtrack）算法之前，我们还需要确定一个或多个启发函数（heuristic function），这个函数如其名，用来指导和推测整个推导过程是否朝着正确的方向执行。这个案例的启发函数可以简单描述为：让目标岸边的狼，羊，卷心菜之和最大，即为3。

这是我们能从问题中发现的最直接的推导，好像没什么用。但对于一些没有固定答案的问题来说，它却是我们判断程序运行是否结束的依据（如果你将这种问题丢给程序去运行解决的话）。

那么没有这个函数，我们如何找出更有用的启发函数让程序知道如何最快的找到最优解。这个就需要分析具体问题了，如果你认真分析过这个问题，你会得到以下隐含条件：

狼是重口味，它不管在岸的哪一边都是不会吃卷心菜的。所以，我们需要先将狼和卷心菜运送到对岸。

这实际上我们能找到的另一个heuristic function，也可以称为一个子目标（sub goal）。有了它做指导，这个问题就迎刃而解了。

有了以上分析，我们只需要从初始状态开始，依次应用上面描述过的4个操作。如果该操作违反了问题中的限制条件，则需要将状态回推到上一个状态，并应用下一个操作。直到我们找到最后的目标状态，再将所有成功状态连在一起，就是我们的解决方案了。

（To be updated：需要补上backtrack流程图）