有4栈。上的第一层叠有n号1，2，... N以随机顺序。其他三个堆块是空的。我们的目标是确定，给定的第一叠层的状态下，是否有可能将所有的元件，以在最后一叠，使它们进行排序。允许移动从第一堆栈移动所述元件，以第二或第三堆栈，并且从第二或第三到第四（1> 2，1> 3,2> 4,3> 4）。与河内塔，较大的元素可以坐在上面较小的。

There are four stacks. On the first stack there are n numbers 1, 2, ... n in random order. The other three stacks are empty. The goal is to determine, given the state of the first stack, whether is it possible to move all the elements to the last stack so that they are sorted. Allowed moves are moving the element from the first stack to the second or third stack, and from the second or third to the fourth (1>2, 1>3, 2>4, 3>4). Unlike towers of Hanoi, larger elements can sit atop smaller ones.

我应该写一个程序要做到这一点，但我不能想出一种算法。请帮助。

I'm supposed to write a program to do this, but I can't come up with an algorithm. Help please.

推荐答案

由于缺乏进一步的深入了解，我会做一个图搜索。

Lacking further insight, I would do this as a graph search.

每个游戏状态是堆栈的数组。需要注意的是平等的 第二和第三个堆是可交换的，所以下面的应 认为是相同的：

Each game state is an array of stacks. Note that for equality, the second and third stack are exchangable, so the following should be considered the same:

((1 3 5)
 (2 4)
 (7 9)
 (0))

((1 3 5)
 (7 9)
 (2 4)
 (0))

该图是向无环图。顶点是游戏状态， 和边缘移动

The graph is a directed acyclic graph. The vertices are game states, and the edges moves.

该算法是创建该曲线图从第一给定的开始 状态，但修剪不能导致目标状态的所有状态， 团结是相同的所有国家（对于这一点，你需要去 广度优先）。

The algorithm is to create this graph starting from the given first state, but prune all states that cannot lead to the goal state, and unite all states that are the same (for this, you need to go breadth-first).

国不能导致的目标状态是那些状态

States that cannot lead to the goal states are those states

可能有进一步的限制。尤其是，我不知道 是否没有一种方法来确定在从所述顺序的结果 直接在第一叠层（这将使该算法 多余的）。

There may be further restrictions. In particular, I am not sure whether there isn't a way to determine the outcome from the order in the first stack directly (which would make this algorithm superfluous).