纸牌解谜（带回溯算法）

Paolo Martinoli

4.26/5 (9投票s)

2005年9月10日

6分钟阅读

81857

2753

一个用于玩跳棋谜题并使用回溯法寻找解决方案的程序。

引言

此程序允许您玩跳棋谜题（也称为棋子跳棋谜题），与真实的棋盘相比有两个主要优点：

您永远不会丢失棋子，
程序可以替您解决谜题——或者至少它会尝试。

事实上，该程序实现了一个简单的回溯算法，以从棋盘上棋子的当前布局开始搜索解决方案。

背景

该程序的主要目的是说明递归函数、内在递归问题和回溯法的概念。它还以一种可重用的类形式为回溯法提供了一个面向对象的包装，该类包含了所有回溯逻辑。源代码包括模板类Stack<class TYPE>，这是一个简单的基于MFC的类型化栈。

使用代码

Backtrack类

Backtrack类是DFS（深度优先搜索）回溯算法的一个极其通用的实现。它主要是为了教学目的而编写的，以便将回溯逻辑从特定问题的细节中抽离出来。要使用此类，您必须从它派生自己的类，并实现以下抽象方法：

// === methods to override
public:
    virtual bool solved() const = 0;

private:
    virtual Step *firstStep() const = 0;
    virtual bool nextStep(Step *p_step) const = 0;

    virtual void doStep(const Step *pc_step) = 0;
    virtual void undoStep(const Step *pc_step) = 0;

    virtual void saveStep(const Step *pc_step, 
                                    int level) = 0;

在我们的示例中，Backtrack类由Solitaire类*实现*，该类代表游戏棋盘并跟踪游戏状态，即棋盘上棋子的当前布局。

回溯法概述

我们知道回溯法适用于可以通过执行一系列步骤来解决的问题。例如，在跳棋谜题中，一个步骤由根据游戏规则在棋盘上移动一个棋子组成。我们必须能够指定在给定游戏状态下可以进行的可能步骤（或移动）。

我们通过实现上面列出的前两个方法firstStep()和nextStep()来完成此任务。请注意，这些方法被声明为const，因为它们不需要修改游戏状态：firstStep()返回一个指向Step类对象的指针，而nextStep()修改其参数。

接下来的两个方法doStep()和undoStep()是我们更新游戏状态的地方（在我们的示例中，我们在这里更改棋子的位置）：doStep()必须执行其参数指示的步骤，而undoStep()必须将游戏回滚到先前的状态，撤销指定的步骤。

必须重写solved()方法来判断当前游戏配置是否是解决方案（返回true）还是不是（返回false）。找到解决方案后，算法将为解决方案的每一步调用saveStep()。必须重写此方法以保存解决方案的步骤。

Step类只是一个空接口。它必须由一个类（在我们的示例中是Move类）*实现*，该类包含表示游戏移动所需的所有信息。一旦所有抽象方法都被重写，我们就可以使用派生类来寻找解决方案。我们只需调用public方法solve()即可。此方法执行递归搜索。当找到解决方案时，它返回true；当遍历完整个搜索树但未找到解决方案时，它返回false，以确认没有可能的解决方案。

其他一些细节

可选地，您也可以重写此方法：

virtual void traceStep(const Step *pc_step, 
                    int level, bool undo = false);

它将在每次调用doStep()或undoStep()之前被调用，并可用于跟踪搜索路径。在我们的示例中，它用于“动画化”棋盘，在搜索过程中快速显示棋子在棋盘上的移动。

可以通过将公共属性m_abort设置为true来停止搜索。请注意，它被声明为volatile，以防您在与执行搜索的线程不同的线程中设置它。事实上，您很可能希望工作线程进行搜索，而主线程则“保持窗口活动”。

顺便说一句，我们的程序使用单个线程并执行“后台处理”。这意味着它会通过PeekMessage循环定期将执行控制权交给Windows。您可以在CSolitaireView类中的traceStep()实现中找到PeekMessage循环。通过这种方式，我们只需一个线程和简单的代码就能获得相同的结果——程序窗口在搜索过程中不会冻结。

最后谈谈Step对象的分配。在firstStep()方法中，必须创建Step类（或者更确切地说，它的具体子类Move）的新实例，我们可能会想知道是否以及何时需要删除这些对象：Backtrack类代码会负责删除它们，除非它们由saveStep()方法返回。

关注点

模板方法模式

Backtrack类代表了模板方法模式的一个示例。一个抽象类（Backtrack）只包含完成其目的所需的一部分逻辑。它的组织方式是，它的具体方法调用protected（甚至私有）抽象方法，而缺失的逻辑本应出现在那里。缺失的逻辑是在一个具体的子类中提供的，该子类重写了抽象方法。

缺点

我们知道回溯法本质上效率不高，因为它对游戏可能状态的整个树进行穷举搜索。随着问题复杂度的增加，其响应时间呈指数级增长。

在我们的示例中，有许多棋盘配置是算法无法处理的。

改进

该程序已得到改进，能够识别对称性。这样，程序就不会浪费时间两次遍历实际上等效的两个搜索路径。对称感知实现在Solitaire类的firstStep()和nextStep()方法中。

还可以更改覆盖搜索树的顺序。如果搜索花费的时间太长，可以停止它并尝试不同的搜索顺序。要更改搜索顺序，请转到菜单“Move->Set Search Parameters...”。

进一步的改进可以是在程序中加入一个“数据库”，其中包含预先解决好的棋盘以供查找。这是文献中一个众所周知的问题，如果能够编写一个比递归树遍历更快哈希表访问算法，效果会很好。

由于给定棋盘配置的解决方案是一种宝贵的资源，一旦找到，程序就会允许您将其与棋盘游戏一起保存。

在Code Project上，目前还有另一篇关于应用于谜题的回溯法的文章：“Backtrack technique to solve Chinese Slide Block Puzzle”作者是Dong Xiang。这两篇文章的区别在于：

我的代码是C++，而Dong的代码是C#。
Dong的文章涉及广度优先搜索（BFS）回溯，我将其省略了。
我抽象出了一个通用的可重用回溯类，而Dong的代码则与该特定谜题绑定。
我的程序有一个GUI可以实际玩这个谜题，而Dong的程序只是解决了一些预设的硬编码配置。

历史

2005年9月10日 - 文章提交。