The Conway Immobilizer

Three positions, “left,” “middle,” and “right,” are marked on a table. Three cards, an ace, a king, and a queen, lie face up in some or all three of the positions. If more than one card occupies a given position then only the top card is visible, and a hidden card is completely hidden; that is, if only two cards are visible then you don’t know which of them conceals the missing card.

Your goal is to have the cards stacked in the left position with the ace on top, the king in the middle, and the queen on the bottom. To do this you can move one card at a time from the top of one stack to the top of another stack (which may be empty).

The problem is that you have no short-term memory, so you must design an algorithm that tells you what to do based only on what is currently visible. You can’t recall what you’ve done in the past, and you can’t count moves. An observer will tell you when you’ve succeeded. Can you devise a policy that will meet the goal in a bounded number of steps, regardless of the initial position?

“It’s tricky to design an algorithm that makes progress, avoids cycling, and doesn’t do something stupid when it’s about to win,” wrote Dartmouth mathematician Peter Winkler in sharing this puzzle in his book Mathematical Puzzles: A Connoisseur’s Collection (2003). It’s called “The Conway Immobilizer” because it originated with legendary Princeton mathematician John H. Conway and because it’s said to have immobilized one solver in his chair for six hours.

Click for Answer