Towers of Hanoi-like problem

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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