algorithm - 使用 X 圆盘和 Y 塔缩放迭代的按位算法来求解河内塔

Question

我喜欢这个问题中提到的算法：“这是如何工作的？河内奇怪的塔解决方案” 这是如何工作的？奇怪的河内塔解决方案

有没有办法扩展河内塔的非递归解决方案以使用 X 磁盘和 Y 塔，塔表示为堆栈？

Answer 1

具有 Y=3 塔和 X 圆盘的河内塔的迭代解决方案，可在Wikipedia上找到：

对于偶数个磁盘：

• 在钉子 A 和 B 之间进行合法移动
• 在钉子 A 和 C 之间进行合法移动
• 使钉子 B 和 C 之间的合法移动重复直到完成

对于奇数个磁盘：

• 在钉子 A 和 C 之间进行合法移动
• 在钉子 A 和 B 之间进行合法移动
• 使钉子 B 和 C 之间的合法移动重复直到完成

在每种情况下，总共进行 2^X-1 次移动。对于 Y=3，此算法的移动次数最少。

此解决方案忽略其他塔，因此它适用于任何 Y >= 3 和任何 X。

尽管三钉版本具有如上所述的简单递归解决方案，但对于具有四钉的河内塔问题（称为 Reve 谜题）的最优解，更不用说更多钉，仍然是一个悬而未决的问题。这是一个很好的例子，说明如何通过稍微放松其中一个问题约束，使一个简单的、可解决的问题变得更加困难。

引自维基百科。