计算纸牌接龙一系列动作的最有效方法
给定任意的钉子接龙棋盘配置，计算导致“游戏结束”位置的任何一系列动作的最有效方法是什么。
例如，标准起始位置是：
..***..
..***..
*******
***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.
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***
*******
..***..
..***..
And the "end game" position is:
..OOO..
..OOO..
OOOOOOO
OOO*OOO
OOOOOOO
..OOO..
..OOO..
Peg solitare is described in more detail here: Wikipedia, we are considering the "english board" variant.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您链接到的维基百科文章已经提到，只有 3,626,632 个可能的棋盘位置，因此任何现代计算机都可以轻松地对该空间进行详尽的搜索。
你上面的算法是正确的，技巧是实现“以前没有见过这个板的旋转或翻转”，你可以使用哈希表来做到这一点。您可能不需要“撤消移动”行，因为真正的实现会将棋盘状态作为参数传递给递归调用，因此您将使用堆栈来存储状态。
另外，目前还不清楚“高效”是什么意思。
如果您想找到导致获胜阶段的所有动作序列，那么您需要进行详尽的搜索。
如果你想找到最短的序列，那么你可以使用分支定界算法来尽早切断一些搜索树。如果您能想出一个好的静态启发式方法，那么您可以尝试 A* 或其变体之一。
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.
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.
从完成的状态开始，按时间倒退走。每一步都是一次跳跃，在棋盘上留下一个额外的钉子。
在每个时间点，您都可以进行多次取消移动，因此您将生成一棵移动树。遍历该树（深度优先或广度优先），当任何分支达到起始状态或不再有任何可能的移动时，停止任何分支。输出导致原始起始状态的路径列表。
Start from the completed state, and walk backwards in time. Each move is a hop that leaves an additional peg on the board.
At every point in time, there may be multiple unmoves you can make, so you'll be generating a tree of moves. Traverse that tree (either depth-first or breadth-) stopping any branch when it reaches the starting state or no longer has any possible moves. Output the list of paths that led to the original starting state.