Towers of Hanoi-like problem

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.

---

Tower of Hanoi - Four Pegs and Beyond: Use the Frame-Stewart algorithm, or represent the game state as an undirected graph and run a shortest-path finding algorithm like Dijkstra's algorithm.

---

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

• where the last stack doesn't only contain the lowest numbers in ascending order, or
• where one of the transitional stacks is not in descending order.

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).

---

I would use A* search with a heuristic based on the number of unsorted elements in any stack, with unsorted elements near the bottom of the stack being the highest penalty to the heuristic.

---

This is equivalent to a much simpler problem. Imagine two stacks. The first has the same random stack of N disks, the second is empty. Move the disks one by one from the first stack to the second, with the following rules:

• You may not put a smaller disk on a larger one.
• If the disk is the largest or smallest in play, remove it from play. If this makes one of the disks in the second stack the largest or smallest, remove it too (repeat until the largest and smallest disks in play are in the first stack).

This problem involves no choices and is O(n).

The two problems are equivalent because you must reserve one of the middle stacks (say, the second) for stacking up the smallest disks, to be kept there until the end. So you can replace that stack and the fourth stack with a single wastbasket into which you may always drop the largest or smallest disk that has been played. That leaves one stack (the third) on which there can still be conflicts.

EDIT:

Ack! Thanks to Rafał Dowgird for catching my error. I will try to fix it, but until/unless I can this method is worthless.