2

给定一个任意的钉子纸牌配置，计算导致“游戏结束”位置的任何一系列移动的最有效方法是什么。

例如，标准起始位置是：

..***..
..***..
*******
***O***
*******
..***..
..***..

而“结束游戏”的位置是：

..OOO..
..OOO..
OOOOOOO
OOO*OOO
OOOOOOO
..OOO..
..OOO..

Peg solitare 在这里有更详细的描述：维基百科，我们正在考虑“英语板”变体。

我很确定在一台合理的计算机上，比如一台 P4 3Ghz，可以在几秒钟内解决任何给定的起始板。

目前这是我最好的策略：

def solve:
    for every possible move:
        make the move.
        if we haven't seen a rotation or flip of this board before:
            solve()
            if solved: return
        undo the move.
4

2 回答 2

3

您链接到的维基百科文章已经提到只有 3,626,632 个可能的棋盘位置，因此任何现代计算机都可以轻松地对空间进行详尽的搜索。

你上面的算法是对的，诀窍是实现“以前没有见过这个板的旋转或翻转”，你可以使用哈希表来做到这一点。您可能不需要“撤消移动”行，因为真正的实现会将板状态作为参数传递给递归调用，因此您将使用堆栈来存储状态。

此外，不清楚您所说的“高效”是什么意思。

如果您想找到导致获胜阶段的所有动作序列，那么您需要进行详尽的搜索。

如果您想找到最短的序列，那么您可以使用分支定界算法尽早切断一些搜索树。如果您能想出一个好的静态启发式算法，那么您可以尝试 A* 或其变体之一。

于 2010-09-01T20:17:19.267 回答
0

从完成状态开始，及时倒退。每一步都是一跳，在棋盘上留下一个额外的钉子。

在每个时间点，您都可以进行多个不移动，因此您将生成移动树。遍历该树（深度优先或广度），在任何分支达到起始状态或不再有任何可能的移动时停止它。输出导致原始起始状态的路径列表。

于 2010-09-02T01:38:39.520 回答