计算钉住单人纸牌中一系列动作的最有效方法 [英] Most effecient way to compute a series of moves in peg solitaire

问题描述

考虑到人形钉单人纸牌的配置，最有效的方法是计算导致最终游戏"位置的任何一系列移动.

Given an arbitary peg solitaire board configuration, what is the most effecient way to compute any series of moves that results in the "end game" position.

例如，标准起始位置为:

For example, the standard starting position is:

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

终局"位置是:

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

此处将详细介绍钉孤单:维基百科，我们正在考虑英文板"变体.

Peg solitare is described in more detail here: Wikipedia, we are considering the "english board" variant.

我非常确定，在一台合理的计算机(例如P4 3Ghz)上，只需几秒钟即可解决任何给定的起始板.

I'm pretty sure that it is possible to solve any given starting board in just a few secconds on a reasonable computer, say an P4 3Ghz.

目前，这是我的最佳策略:

Currently this is my best strategy:

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.

推荐答案

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

The wikipedia article you link to already mentions that there only 3,626,632 possible board positions, so it it easy for any modern computer to do an exhaustive search of the space.

您上面的算法是正确的，技巧是实现以前从未见过此板的旋转或翻转"，您可以使用哈希表来完成.您可能不需要撤消移动"行，因为实际的实现会将板状态作为递归调用的参数传递给您，因此您将使用堆栈来存储状态.

Your algorithm above is right, the trick is implementing the "haven't seen a rotation or flip of this board before", which you can do using a hash table. You probably don't need the "undo the move" line as a real implementation would pass the board state as an argument to the recursive call so you would use the stack for storing the state.

此外，还不清楚有效"的含义.

Also, it is not clear what you might mean by "efficient".

如果您想找到导致获胜阶段的所有移动顺序，则需要进行详尽的搜索.

If you want to find all sequences of moves that lead to a winning stage then you need to do the exhaustive search.

如果要查找最短的序列，则可以使用分支定界算法尽早删除一些搜索树.如果您可以提出一种好的静态启发式方法，则可以尝试A *或其变体之一.

If you want to find the shortest sequence then you could use a branch-and-bound algorithm to cut off some search trees early on. If you can come up with a good static heuristic then you could try A* or one of its variants.

这篇关于计算钉住单人纸牌中一系列动作的最有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！