Solitaire of independence

Abstract

<p>In this paper, we study a reversible process (more precisely, a groupoid/group action) resembling the classical 15-puzzle, where the legal moves are to “move the unique hole inside a translate of a shape <em>S</em>”. Such a process can be defined for any finite subset <em>S</em> of a group, and we refer to such a process as simply “solitaire”. We develop a general theory of solitaire, and then concentrate on the simplest possible example, solitaire for the plane Z2, and <em>S</em> the triangle shape (equivalently, any three-element set in general position). In this case, we give a polynomial time algorithm that puts any finite subset of the plane in normal form using solitaire moves, and show that the solitaire orbit of a line of consecutive ones—the line orbit—is completely characterised by the notion of a so-called fill matrix. We show that the diameter of the line orbit, as a graph with edges the solitaire moves, is cubic. We show that analogous results hold for the square shape, but indicate some shapes (still on the group Z2) where this is less immediate. We then explain in detail the connection of the solitaire to TEP and more generally permutive subshifts. Namely, the solitaire is a closure property of various sets of subsets of the group that can be associated to such a subshift, such as the independence, spanning and filling sets.</p>