All solutions to the immobilizer problem (Q2341295)

The article presents a so called ``immobilizer'' problem defined as simple sorting of three playing cards on three stacks on a table, arranged face up. The challenge behind the problem is that it must run ``memoryless'', i.e. assuming that only the top card of any of three stacks is visible, the move an algorithm may make must only depend on the appearance of the stacks. The paper provides the game-theoretic formulation of the problem in the form of the immobilizer graph with the property that solutions to the original problem are exactly spanning intrees of the graph satisfying some additional constraints. This paper not only finds a solving strategy of the problem, it provides an analysis of the class of solving strategies and enumerates them.