基于模式的多栈排序算法

Question

在我(小)的业余时间里，我提出了一个小的个人项目，作为使用新技术的动力(对我来说！)，比如Python3& Node。

我想尝试为一个谜创建一个解决方案例程，类似于建筑中的河内塔，如下图所示：

​

​

难题规则

1. 8个彩色块被随机放置在3个堆栈(S1-S3)上，其容量分别为5、3、3。
2. 大小为3的第四个堆栈( S4 )为空，但用作其他堆栈之间移动的临时存储；例如，在S2中移动紫色旁边的蓝色:移动红色的S2 -> S4，移动绿色的S2 -> S4，移动蓝色的S3 -> S4，移动蓝色的S4 -> S2等等。
3. 随机生成一个由5个块组成的目标模式，这些块必须一个接一个地在堆栈之间移动(通过S4)，直到S1中出现正确的有序块为止，此时S4必须再次为空( S2，S3的最终状态并不重要)。
4. 请注意，我的插图并不完美，而且随机场景实际上更具有挑战性！但是，假设所有的堆栈都是在它们的基础上访问的，所以S1上的第一个可访问块(左)是黑色的，等等。
5. 有一些解决方案的提示可能最终被编码到算法中，例如，首先关注最后一个块，在这个例子中是紫色的。

算法：

一段时间以来，我一直在寻找一种基于模式的最合适的多堆栈“排序”算法，以避免重新发明轮子，但找不到任何似乎相关的东西，尽管我可能找错了地方。河内经典递归塔显得过于基本，而分流场和旅行推销员等算法(以及标准Bubblesort、快速排序等)看起来不太合适(如果我错了，请纠正我！)

我的问题：

有人能建议或推荐一个合适的基本算法，我可以在此基础上建立或调整以解决这个难题吗？它可能需要递归，以找到正确的路径，但我确信这种类型的多堆栈或基于模式的排序已经做过了吗？我最终想要通过最少的步骤达到最好的效率，但这是后来的事。

正如我前面提到的，我很可能最终会使用Python或JS来实现这一点，但是在这个阶段，任何想法或片段都会受到赞赏--我希望稍后自己来完成开发工作。

提前感谢！

艾伦

Answer 1

一种方法是首先将3个未使用的块移动到S4。设置发行版，使其为S1 =3个块，S2 =3个块，S3 =2个块。如果S3有1或2个未使用的块，则需要1或2个移动才能将未使用的块移动到S4。重复对S2，采取1至3移动移动1至3个未使用的块。未使用的块最后从S1中删除。

现在你有5个街区和3个堆栈。假设S1有3个块，S2有2个块。位于S1顶部的块可能需要最多的移动次数才能结束，这是S1唯一的块。例如，属于S1顶部的块位于S2的顶部。因此，将两个块从S2移动到(现在为空) S3，因此键块位于S3的底部。然后将所有3个块从S1移动到S2，然后将键块移动到S1。在那之后，问题变成了4个块和3堆大小为4，3，3的块，这应该不会太困难。一旦完成，S4中的3个块就可以移动到S2或S3。

对于3堆栈排序，多阶段合并排序是最快的，但是所有3个堆栈都需要相同的大小，所以在这里不适用。