Solitaire of independence

Abstract 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 S ”. Such a process can be defined for any finite subset S 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 $$\mathbb {Z}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>Z</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> , and S 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 $$\mathbb {Z}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>Z</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> ) 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.