What are good methods for solving Conway's card-stacking puzzle?

Suppose there is a table with three marked spots, $A, B,$ and $C$, on which playing cards can be put, face up. Initially, an ace (1), a deuce (2), and a trey (3) are placed on one or more of these spots, but it is not specified where they are placed.

Two or three cards might be in the same spot, one atop the other; in this case only the top card is visible. If you see the ace in spot $A$, and the deuce in spot $B$, and you see that spot $C$ is empty, then you know that the trey is under the ace or under the deuce, but not which. If you see that spots $A$ and $B$ are empty, and that the ace is in spot $C$, then you know that the deuce and the trey are in spot $C$ under the ace, but you don't know which is on the bottom of the pile. Thus there are 60 possible arrangements for the cards, but only 33 different ways that they can appear.

The problem is to produce an algorithm which guarantees to get all three cards onto spot $A$, with the ace on top, then the deuce, and the trey on the bottom, moving only one card at a time, and using no memory.

The algorithm should have the following form: for each of the 33 possible appearances of the table, it should specify that a certain visible card should be moved to a certain position, or halt. It should guarantee to achieve success in a bounded amount of time regardless of the initial layout of the cards. (Obviously, the bound must be less than 60 moves.) It does not have to halt on success; it is enough to guarantee that the cards will will reach the target position.

It is not too hard to come up with a solution to the problem just by tinkering, and indeed I have solved the puzzle. But I haven't ever been able to think of a good approach to solving it.

What are some effective approaches to solving this problem?

[ EDIT 2013-09-27: I had the success condition wrong before. The cards are supposed to be stacked up, not spread out. ]

-
J.H. Conway told me this puzzle around 1989. He phrased it in terms of having one's memory removed, which I find unpleasant, and also seems to confuse some people. I think it is more straightforward to talk of memoryless algorithms. –  MJD Dec 10 '12 at 0:28
For what it's worth, I think this problem may be treated as finding a reset sequence (aka synchronizing word) for a given automaton. –  mhum Sep 26 '13 at 0:28
could you please show an example of one statement of the algorithm ? because it's not clear what kind of information you can use for each step of the algorithm. –  Xoff Sep 27 '13 at 15:15
You can use the positions of the visible cards. For example: “If you see the ace in spot $A$, the trey in spot $B$, and no cards in spot $C$, then move the ace onto the trey.” Or “If you see a trey and nothing else, move it one space to the right, or, if it is in spot $C$, move it to spot $A$.” –  MJD Sep 27 '13 at 15:50
@MJD: Interesting puzzle. Do you know what's been written about it, if anything, other than your post above? –  supercat Mar 31 '14 at 22:14

The best way to prove that a given algorithm is correct and bounded is to come up with a quantity $Q$, as a function of the visible layout, that decreases every time you make a move and is 0 for the correct layout.

Even if no obvious heuristic suggests itself, you can make sure you don't enter any loops by noting that there are at most two actual states that correspond to a given visible state. If we call these two states Type A and Type B, then as long as no move turns a type B state to a type A state, and the algorithm has no loops in the visible state space (i.e. obviously repetitive), it must find the solution eventually.

I'm trying to give hints and generalities here without actually solving it, since as you say it can, of course, be solved by exhaustion without too much difficulty.

-

The three-card problem may will allow one to enumerate all possibilities, but using three piles one may in fact solve the problem for an arbitrary number of cards; enumeration of all states will not be possible, but one may formulate invariants which, once established, can be maintained while the cards go through a "loop" of visible states. If one of the invariants is that a certain range of cards is sorted, and a certain through the loop is guaranteed to add at least one card through the range, then repeating the loop will eventually yield a sorted sequence. All that will be left is to define what should happen for visible states that do not appear in the loop, and show that the loop invariants will establish themselves.

For illustrative purposes, I will assume there are thirteen cards, ace through king, and the goal is to have all thirteen on the pile A, ace on top, king on the bottom, and other cards in sequence. The algorithm may be easily adapted to any other number three or greater (sorting two cards with three piles is trivial).

The key invariant is that the king will either be the only card on pile B or C, or else will be the bottom card on pile A, covered by zero or more other cards in direct numerical sequence (i.e. K-Q-J-T-9-8-etc.). If the invariant does not hold, the king may "pop up" unexpectedly and disrupt a step in the algorithm, but once that occurs the king will be visible. When the king is visible, the algorithm will have enough information to clear a spot for it and move what is expected to be a lone king to the empty pile. If the invariant still didn't hold, a cards may unexpectedly "pop up" beneath the king; that could disrupt the algorithm a second time, but moving the king to an empty pile will have established the invariant.

In describing the algorithm, most steps to say that when certain conditions apply, one should repeat an action until a condition occurs. Once the "king invariant" is established and the conditions for an action are established, making the indicated moves will not affect the stated conditions until the pile is vacant, so no memory will be required to continue the action.

1. Any time a king is visible in column C, move cards from B to A until B is vacant, then move the king there.
2. Any time a king is visible in column B, move cards from A to C until A is vacant, then move the king there.
3. Any time C shows a non-king, B doesn't show a king, and A is non-empty, move a card from C. If it's one less than the card on A, move it there; otherwise move it to B. Keep doing until C is exhausted.
4. If B doesn't show a king, C is empty, and A is non-king, move A to B until king appears, then move it to C.
5. If A is empty and no king is visible, move cards B to C until a king appears or B is exhausted; if A is exhausted, move a card from C to A. This step will not be necessary once the invariant is established, but it might be necessary prior to that.

Note that if B and c are empty and A shows an ace, then the deck is "probably" sorted. This condition may arise once, within the first ten moves, if the deck is not sorted, but every appearance after the first, or after the tenth move, will represent a sorted deck. If one could request, on the first move only, that if column B is empty a card should be moved there, one could avoid any false reports of sorted sequence.

At the end of step 1, assume the bottom of deck A has k cards in order [k may be zero], starting with the queen on the bottom. Then at the end of step 2, those cards will be on the top of C in reverse order. At the start of step 3, those cards will get moved to pile A. Once that is done, pile C will still contain the next card for pile A. Thus, at the end of step 3, pile A will contain at least k+1 correctly-sorted cards in addition to the king. Step 4 will place the correctly-sorted cards in reverse order on the top of pile B, and step 1 will move them to the bottom of deck A. The net effect will be that after the loop has run, if there were k sorted cards, there will now be at least k+1 (except in the case where all the cards were sorted).

With thirteen cards, the maximum number of moves required to establish the invariant will be 33 (assuming e.g. Q/AK/JT98765432). The ten cards from the right pile will be moved to pile A (yielding QJT98765432/AK/-), all eleven cards from the left pile will be moved to the middle (yielding -/23456789TJQAK/-), and twelve cards will be moved from the middle pile to the right pile.

With the invariant established, each pass through the "loop" will take 3n+k moves, where k is the number of cards that are sorted after the pass, and it is possible that only one card will get sorted per pass. The net result is an O(N^2) sort. Still, not too shabby for an algorithm using O(0) space!

-