All solutions to the immobilizer problem (Q2341295)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | All solutions to the immobilizer problem |
scientific article |
Statements
All solutions to the immobilizer problem (English)
0 references
23 April 2015
0 references
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.
0 references
immobilizer problem
0 references
game theory
0 references
solving strategies
0 references
solutions enumeration
0 references