Conway immobilizer problem is a puzzle that reads like the following:
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?
The puzzle has got its name because it's said to have immobilized one solver in his chair for six hours.
The link above gives one possible answer (marked as spoiler for those who want to solve it by themselves):
- If there’s an empty slot, move a card to the right (around the corner, if necessary) to fill it. Exception: If the position is king-blank-ace or king-ace-blank, place the ace on the king.
- If all three cards are visible, move the card to the right of the queen one space to the right (again, around the corner if necessary). Exception: If the queen is on the left, place the king on the queen.
All solutions to the Immobilizer Problem (pdf) uses graph theory to show that there are 14287056546 distinct strategies that solve the problem.
Given a strategy for Conway Immobilizer, determine if the strategy actually solves it, i.e. given any initial configuration, repeating the strategy will eventually place all cards into the winning state.
A strategy (the input) can be in any format that represents a set of pairs
current visible state -> next move for every possible
current visible state. A visible state represents what is visible on each of three slots (it can be one of A/K/Q or empty). A move consists of two values
A, B which represents a move from slot A to slot B.
The input format can be e.g. a list of pairs, a hash table, or even a function, but it should not involve any external information, e.g. you cannot encode a "move" as a function that modifies the full game state (entire stacks of cards). You can use any four distinct values for A/K/Q/empty (the visible state of each slot) and three distinct values for left/middle/right (to represent a move from a slot to another).
Standard code-golf rules apply. The shortest code in bytes wins.
Input: the solution above Output: True Input: the solution above, but the exception on 'K.A' is removed (at 'K.A', move K to the right) Output: False ('QKA' -> 'K.A' -> 'QKA') Input: if only one card is visible, move it to the right if Q and K are visible, move K on the top of Q if K and A are visible, move A on the top of K otherwise, move A to the empty slot Output: False ('..A' where Q, K, A are stacked -> 'A.K' -> '..A')